Less is More: Significance-Based N-gram Selection for Smaller, Better Language Models

Robert C. Moore, Chris QuirkEMNLP 2009

Abstract

Traditional N-gram language models face a significant challenge: as the order of the model increases to capture more context, the number of parameters grows exponentially, leading to "model bloat." Conventional pruning techniques typically trade off model size for predictive accuracy. This paper presents a significance-based N-gram selection method that uses statistical significance tests to prune unnecessary N-grams. The resulting models are not only substantially smaller but also achieve lower perplexity than their unpruned counterparts, ultimately outperforming industry-standard Kneser-Ney smoothing.

Introduction

In Natural Language Processing (NLP), N-gram models remain fundamental for tasks like speech recognition and machine translation. With the availability of massive training corpora, researchers have naturally moved toward higher-order models (e.g., 5-grams to 7-grams). However, these models often become impractically large for memory-constrained environments. Traditional pruning methods, which delete rare N-grams, usually result in a performance penalty: as the model size decreases, its perplexity increases. This research explores a way to reduce model size while simultaneously improving performance by treating pruning as a form of noise reduction.

Significance-Based N-gram Selection

The core innovation is a selection criterion based on the Maximum Likelihood Set (MLS). Rather than relying solely on a single Maximum Likelihood Estimate, the MLS defines a range of plausible probabilities for a given N-gram based on observed counts.

A high-order N-gram is only retained in the model if the "backoff" estimate—the prediction provided by a simpler, lower-order model—falls outside this plausible range. If the simpler model's estimate is statistically consistent with the observed data for the complex N-gram, the complex N-gram is rejected as noise. This approach ensures that the model only stores parameters that provide statistically significant information beyond what is already captured by shorter contexts.

To maintain mathematical consistency after pruning, the authors utilize an iterative backoff weighting algorithm. This search algorithm combines "false position" and "bisection" methods to recalculate weights, ensuring the total probability mass remains correctly distributed.

Experimental Setup

The methods were evaluated using the English portion of the WMT-06 Europarl corpus, consisting of approximately 27.5 million words. The researchers compared their significance-based selection against seven smoothing methods, including Katz backoff and Modified Kneser-Ney (KN). Performance was measured using perplexity on standard development and test sets.

Key Results and Insights

Breaking the Linear Growth of Model Size

One of the most significant findings is the impact on model scaling. In standard models like Kneser-Ney, the number of parameters grows almost linearly with the N-gram order. In contrast, significance-based selection causes the model size to level off.

Figure 1: Model size (millions of parameters) vs. N-gram length. Significance-based selection prevents the exponential growth seen in standard models.

As shown in Figure 1, while a standard 10-gram model would be prohibitively large, the significance-based 10-gram model remains roughly the same size as a 5-gram model. The statistical test automatically rejects the vast majority of higher-order sequences that do not generalize beyond the training data.

Superior Perplexity-Size Trade-offs

Significance-based selection acts as a noise filter, removing "accidental" patterns in the training data. This leads to actual improvements in predictive quality. For Katz backoff and absolute discounting, the method reduced perplexity by 3.3% to 9.3% while simultaneously shrinking the model.

Figure 2: Perplexity vs. Model Parameters. The proposed methods (new-opt and new-fix) achieve a better trade-off than the standard Modified Kneser-Ney (KN-mod-fix).

Figure 2 illustrates that the new smoothing methods, when combined with significance-based selection, achieve a lower perplexity for any given model size compared to the best-pruned Kneser-Ney models. Specifically, the best configuration achieved up to an 8% reduction in perplexity over a similarly sized KN model.

Conclusion and Future Work

This research demonstrates that for N-gram models, "less is more." By applying statistical significance to parameter selection, models can be made both smaller and more accurate. Future work includes scaling these experiments to "trillion-word" corpora and exploring the combination of significance-based selection with word clustering to achieve even more dramatic efficiency gains.

Summary updated

BibTeX
@inproceedings{moore2009less,
  author = {Robert C. Moore and Chris Quirk},
  title = {{Less is More: Significance-Based N-gram Selection for Smaller, Better Language Models}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
}
Figure