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:
- 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.
- 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.
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.
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