Saul and Pereira, EMNLP 1997

Aggregate and mixed-order Markov modles for statistical language processing

This paper can be found at [1]

Citation

Lawrence Saul and Fernando Pereira. Aggregate and mixed-order Markov models for statistical language processing. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, pages 81–89, Providence, Rhode Island, USA, August 1997.

Summary

The authors wanted to train a language model that used fewer parameters than an n-gram model, but still performed well. They developed aggregate and mixed-order markov models. While similar in some ways (mainly their Markovian properties), the new methods give fewer words 0 probability. It did perform worse than the n-gram models, but it used fewer parameters.

Aggregate Markov Models

They set $P(w_{2}|w_{1})=\sum _{i=1}^{C}P(w_{2}|c)P(c|w_{1})$ for some number of classes $C$. While this has the Markovian property, it is not a hidden markov model; it doesn't conform to some of the restrictions of an HMM. The idea is that classes will be developed from data that prove useful to calculate probabilities. They train using the EM algorithm: the E-step finds the probability of $w_{1}$ being in category $c$ given words $w_{1},w_{2}$: $P(c|w_{1}w_{2})={\dfrac {P(w_{2}|c)P(c|w_{1})}{\sum _{c'}P(w_{2}|c')P(c'|w1)}}$. The M-step calculates the model's parameters by counting. In general, the more classes, the lower the perplexity on test data. This makes sense. If there are $V$ classes (for the number of items in the vocabulary), then it would be a true bigram model. If there were one class, it would be a regular unigram model.

Mixed-order Markov Models

The size of n-grams increase with the square of $n$. As a replacement, the authors devised a "skip-k" transition matrix $M(w_{t-k},w_{t})$ that predicts the current word based on the word k-words in the past. A mixed-order markov model uses many different skip-k transition probabilities. If we used $m$ of the special bigram models, the probability from this model would be: $P(w_{t}|w_{t-1},\ldots ,w_{t-m})=\sum _{k=1}^{m}\lambda _{k}(w_{t-k})M_{k}(w_{t-k},w_{t})\prod _{j=1}^{k-1}\{1-\lambda _{j}(w_{t-j})\}$

Future Work

Aggregate Markov models can kinda be viewed as approximations of a full bigram model. In this way, the method is similar to SVD decomposition, which might be related. The classic question of generative vs discriminative models comes up. The authors argue that their generative model is fine because they train the mixture of generative models such that they model reality. Theirs models also train in a fraction of the time spent training Rosenfeld's models.

Related Work

• Rosenfeld, Computer Speech and Language 1996 worked on language models, but from a discriminative stance.
• Other combinations of language models include work done by Huang et al, Computer Speech and Language 1993 and Ney, et al, Computer Speech and Language 1994
• Jelinek et al, Advances in Speech Signal Processing 1992