Scaling Hidden M arkov Language Models (2020)

Abstract: The hidden Markov model (HMM) is a fundamental tool for sequence modeling that cleanly separates the hidden state from the emission structure. However, this separation makes it difficult to fit HMMs to large datasets in modern NLP, and they have fallen out of use due to very poor performance compared to fully observed models. This work revisits the challenge of scaling HMMs to language modeling datasets, taking ideas from recent approaches to neural modeling. We propose methods for scaling HMMs to massive state spaces while maintaining efficient exact inference, a compact parameterization, and effective regularization. Experiments show that this approach leads to models that are much more accurate than previous HMMs and n-gram-based methods, making progress towards the performance of state-of-the-art NN models.

## introduction hidden markov models (hmms) are a fundamental latent-variable model for sequential data, with a rich history in nlp. they have been used extensively in tasks such as tagging @xcite , alignment @xcite , and even, in a few cases, language modeling @xcite . compared to other sequence models, hmms are appealing since they fully separate the process of generating hidden states from observations, while allowing for exact posterior inference. state-of-the-art systems in nlp have moved away from utilizing latent hidden states and toward deterministic deep neural models. we take several lessons from the success of neural models for nlp tasks: (a) model size is critical for accuracy, e.g. code available at github.com/harvardnlp/hmm-lm large lstms @xcite show marked improvements in performance; (b) the right parameterization is critically important for representation learning, e.g. a feedforward model @xcite can have the same distributional assumptions as an n-gram model while performing significantly better; (c) dropout is key to achieving strong performance @xcite . we revisit hmms for language modeling as an alternative to modern neural models, while considering key empirical lessons from these approaches. towards that goal, we introduce three techniques: a modeling constraint that allows us to use a large number of hidden states while maintaining efficient exact inference, a neural parameterization that improves generalization while remaining faithful to the probabilistic structure of the hmm, and a variant of dropout that both improves accuracy and halves the computational overhead during training. experiments employ hmms on two language modeling datasets. our approach allows us to train an hmm with tens of thousands of states while maintaining efficiency and significantly outperforming past hmms as well as n-gram models. ## related work in order to improve the performance of hmms on language modeling, several recent papers have combined hmms with neural networks. @xcite develop an approach to relax hmms, but their models either perform poorly or alter the probabilistic structure to resemble an rnn. @xcite utilize model combination with an rnn to connect both approaches in a small state-space model. our method instead focuses on scaling pure hmms to a large number of states. prior work has also considered neural parameterizations of hmms. @xcite demonstrate improvements in pos induction with a neural parameterization of an hmm. they consider small state spaces, as the goal is tag induction rather than language modeling. 1 most similar to this work are the large hmm models of @xcite . they introduce a sparsity constraint in order to train a 30k state nonneural hmm for character-level language modeling; however, their constraint precludes application to large vocabularies. we overcome this limitation and train models with neural parameterizations on word-level language modeling. finally, another approach for scaling state spaces is to grow from small to big via a split-merge process @xcite . in particular, @xcite learn an hmm for language modeling via this process. as fixed-size state spaces are amenable to batching on modern hardware, we leave split-merge procedures for future work. ## background: hmms we are interested in learning a distribution over observed tokens @xmath0, . . . , x t , with each token x t an element of the finite vocabulary x . hidden markov models (hmms) specify a joint distribution over observed tokens x and discrete latent states @xmath1, . . . , z t , with each z t from the finite set z. for notational convenience, we define the starting state z 0 = . this yields the joint distribution, we refer to the transition and emission matrices as the distributional parameters of the hmm. specifically, let @xmath2, 1] |z|×|z| be the transition probabilities and @xmath3, 1] |z|×|x | the emission probabilities, we distinguish between two types of model parameterizations: scalar and neural, where the model parameters are given by θ. a scalar parameterization sets the model parameters equal to the distributional parameters, so that θ = {a, o}, resulting in o(|z| foot_2 + |z||x |) model parameters. a neural parameterization instead generates the distributional parameters from a neural network (with parameters θ), decoupling the size of θ from a, o. this decoupling gives us the ability to choose between compact or overparameterized θ (relative to a, o). as we scale to large state spaces, we take advantage of compact neural parameterizations. in order to fit an hmm to data x, we must marginalize over the latent states to obtain the likelihood p(x) = z p(x, z). this sum can be computed in time o(t |z| 2 ) via the forward algorithm, which becomes prohibitive if the number of latent states |z| is large. we can then optimize the likelihood with gradient ascent (or alternative variants of expectation maximization). hmms and rnns although the forward algorithm resembles that of the forward pass in a recurrent neural network (rnn) @xcite , there are key representational differences. rnns do not decouple the latent dynamics from the observed. this often leads to improved accuracy, but precludes posterior inference which is useful for interpretability. a further benefit of hmms over rnns is that their associative structure allows for parallel inference via the prefix-sum algorithm @xcite . 2 finally, hmms bottleneck information from every timestep through a discrete hidden state. nlp has a long history of utilizing discrete representations, and discrete representations may yield interesting results. for example, recent work has found that discrete latent variables work well in low-resource regimes @xcite . ## scaling hmms we propose three extensions to scale hmms for better language modeling performance: blocked emissions, which allow for very large models; neural parameterization, which makes it easy for states to share model parameters; and state dropout, which encourages broader state usage. blocked emissions our main goal is to apply a hmm with a large number of hidden states to learn the underlying dynamics of language data. however, the o(t |z| 2 ) complexity of marginal inference practically limits the number of hmm states. we can get around this limit by making an assumption on the hmm emission matrix o. as noted by @xcite , restricting the number of states that can produce each word can improve inference complexity. we utilize a slightly stronger assumption on the model: a) states are partitioned into m equal sized groups each of which emit the same subset of words, and b) each word is only admitted by one group of @xmath4. we implement this group structure through a set of blocked emissions, each corresponding to one of the m state groups, since there are only k states with nonzero probability of occurring at every timestep, we only need to consider transitioning from the |z xt | = k previous states to the next |z x t+1 | = k states, resulting in o(k 2 ) operations per timestep. this gives a serial complexity of o(t k 2 ). our parameterization uses an embedding for each state in z (e @xmath5. from these we can create representations for leaving and entering a state, as well as emitting a word: with all in r |z|×h . the hmm distributional parameters are then computed as, foot_4 note that parameter computation is independent of inference and can be cached completely as the emission and transition matrices, a and o, at testtime. for the training algorithm, shown in algorithm 1, we compute a and o once per batch while rnns and similar models recompute emissions every token. ## experimental setup emission blocks the model requires partitioning token types into blocks x m . while there are many partitioning methods, a natural choice is brown clusters @xcite which are also based on hmms. brown clusters are obtained by assigning every token type in x a state in an hmm, then merging states until a desired number of partitions m is reached. we construct the brown clusters on the training portions of the datasets and assume the vocabulary remains identical at test time (with oov words mapped to unk). we include more background on brown clusters in the appendix. ## results figure 3 examines the effect of state size: we find that performance continuously improves significantly as we grow to 2 16 states, justifying the large state space. the marginal improvement does lower as the number of states increases, implying that the current approach may have limitations in scaling to even larger state spaces. ## conclusion this work demonstrates methods for effectively scaling hmms to large state spaces on parallel hardware, and shows that this approach results in accuracy gains compared to other hmm models. in order to scale, we introduce three techniques: a blocked emission constraint, a neural parameterization, and state dropout, which lead to an hmm that outperforms n-gram models and prior hmms. once scaled up to take advantage of modern hardware, very large hmms demonstrate meaningful improvements over smaller hmms. hmms are a useful class of probabilistic models with different inductive biases, performance characteristics, and conditional independence structure than rnns. future work includes using these approaches to induce model structure, develop accurate models with better interpretability, and to apply these approaches in lower data regimes. stephan vogel, hermann ney, and christoph tillmann. 1996. hmm-based word alignment in statistical translation. in proceedings of the 16th conference on computational linguistics -volume 2, coling '96, page 836-841, usa. association for computational linguistics. sam wiseman, stuart m. shieber, and alexander m. rush. 2018. learning neural templates for text generation. corr, abs/1808.10122. wojciech zaremba, ilya sutskever, and oriol vinyals. 2014. recurrent neural network regularization. corr, abs/1409.2329.