Aggregate and mixed-order Markov models for statistical language processing

Lawrence K. Saul, Fernando Pereira

Abstract This paper explores language models that bridge the gap between standard n-gram orders. We introduce Aggregate Markov Models, which utilize probabilistic class assignments, and Mixed-order Markov Models, which combine predictions from non-adjacent words. Trained via Expectation-Maximization (EM), these models serve as effective intermediaries in smoothing procedures, significantly reducing the perplexity of unseen word combinations in large-scale corpora.

Introduction

Statistical language processing has long relied on n-gram models, which predict the next word in a sequence based on the preceding $n-1$ words. However, these models suffer from severe data sparsity; as $n$ increases, the number of possible combinations grows exponentially, far outstripping available training data. Traditional "backoff" methods jump from higher-order models (like trigrams) to lower-order ones (like bigrams) when encountering unseen sequences, often losing significant contextual information. This work introduces "intermediate" models that act as stepping stones, providing a more refined transition during smoothing.

Methodology

The authors propose two primary architectures, both optimized using the Expectation-Maximization (EM) algorithm:

  1. Aggregate Markov Models: These are "soft" class-based bigram models. Unlike traditional hard clustering where each word belongs to exactly one category, these models employ a probabilistic mapping: $P(w_2|w_1) = \sum_c P(w_2|c)P(c|w_1)$. This allows words to inhabit multiple semantic or syntactic roles simultaneously.
  2. Mixed-order Markov Models: These models extend the bigram concept by considering "skip-$k$" dependencies. Instead of relying solely on the immediately preceding word, they incorporate predictions based on words further back in the sequence, using context-dependent mixing coefficients to determine which preceding word is most predictive.
Figure 2: Training and test perplexity of an aggregate Markov model as a function of EM iterations.

Experimental Results

The models were evaluated on the ARPA North American Business News (NAB) corpus, comprising approximately 78 million training words and a 60,000-word vocabulary. The aggregate model successfully discovered meaningful word groupings, forming classes around days of the week, numbers, and financial terminology.

Figure 6: Examples of word classes discovered by the aggregate Markov model, showing semantic and syntactic clusters.

Key findings include:

  • Perplexity Reduction: Integrating a mixed-order model into the smoothing process reduced the perplexity of unseen word combinations by 51% compared to the standard Katz backoff baseline. Total test set perplexity saw a 16% improvement.
  • Computational Efficiency: The EM-based training is remarkably efficient. While contemporary Maximum Entropy models required hundreds of CPU days, the proposed models were trained in under 12 CPU hours.
  • Soft vs. Hard Clustering: The "soft" assignments in aggregate models proved superior to hard clustering, as they better capture the inherent ambiguity and multi-functional nature of common words.

Conclusion

By introducing aggregate and mixed-order models as intermediaries between standard n-gram orders, the authors demonstrate a practical and efficient way to mitigate the sparsity problem in language modeling. These models provide a smoother "backoff" path, leading to significantly better generalization on unseen data without the prohibitive computational costs of more complex alternatives.

Summary updated

Abstract

We consider the use of language models whose size and accuracy are intermediate between different order n-gram models. Two types of models are studied in particular. Aggregate Markov models are classbased bigram models in which the mapping from words to classes is probabilistic. Mixed-order Markov models combine bigram models whose predictions are conditioned on different words. Both types of models are trained by ExpectationMaximization (EM) algorithms for maximum likelihood estimation. We examine smoothing procedures in which these models are interposed between different order n-grams. This is found to significantly reduce the perplexity of unseen word combinations.
BibTeX
@inproceedings{saul1997aggregate,
  author = {Lawrence K. Saul and Fernando Pereira},
  title = {{Aggregate and mixed-order Markov models for statistical language processing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {1997},
  url = {https://openreview.net/forum?id=B14W0-Md-r},
}
Figure