Study on interaction between entropy pruning and kneser-ney smoothing

Ciprian Chelba, Thorsten Brants, Will Neveitt, Peng XuInterspeech 2010

TL;DR

This paper investigates a critical but overlooked interaction between language model pruning and smoothing techniques, revealing that popular Kneser-Ney smoothing performs poorly under aggressive pruning, leading to significant accuracy degradation. The authors demonstrate that traditional Katz smoothing is more robust, offering a crucial insight for building efficient and accurate speech recognition systems.

What Problem Does This Paper Address?

Building effective language models (LMs) for applications like voice search requires balancing model size and accuracy. Large LMs, trained on massive datasets, capture complex linguistic patterns but are computationally expensive. To make them practical, techniques like "pruning" are used to reduce their size by removing less important information (e.g., infrequent n-grams). Simultaneously, "smoothing" techniques are essential to assign non-zero probabilities to unseen word sequences.

While Kneser-Ney smoothing is widely adopted for its superior performance on unpruned models, this paper highlights a critical problem: when combined with aggressive pruning (reducing the model to a tiny fraction of its original size), Kneser-Ney smoothing leads to a severe drop in performance. This is counter-intuitive, as one would expect a robust smoothing technique to withstand pruning. The paper aims to understand why this interaction occurs and to identify more suitable alternatives for pruned LMs.

Methods

The core of the paper is an empirical study comparing different pruning and smoothing techniques.

  • Pruning: The authors primarily focus on Stolcke pruning, an entropy-based method that iteratively removes n-grams based on their contribution to the model's entropy. They also briefly discuss Seymore-Rosenfeld pruning, which uses relative frequencies of contexts instead of probabilities derived from lower-order estimates.
  • Smoothing: They compare several smoothing techniques, with a particular focus on:
  • Katz (Good-Turing) smoothing: A traditional method that estimates probabilities for unseen events based on the frequency of events seen once.
  • Kneser-Ney smoothing: A more modern approach that uses "left-diversity" counts (how many different contexts an n-gram appears in) to improve back-off estimates. This includes standard Kneser-Ney and its interpolated variants.
  • Evaluation: The primary metric for evaluating the pruned models is perplexity (PPL), a measure of how well a probability model predicts a sample. They also refer to word error rate (WER) in the context of their larger voice search system.

The authors investigate the interaction by pruning models to very small sizes (e.g., 0.1% of original size) and observing the resulting perplexity. They also analyze the theoretical reasons behind the observed performance degradation.

Datasets

The paper uses two main experimental setups:

  • Small-scale experiments: For detailed analysis of pruning and smoothing interactions, they use Broadcast News data.
  • Training data: 128M words
    • Test data: 692k words
    • Vocabulary: 143k words, filtered to include only n-grams with counts > 1.
  • Large-scale experiments: For practical relevance to voice search, they train models on a much larger dataset:
  • Training data: 230B words (using only correct queries, not those requiring spelling correction).
  • Vocabulary size: 1M words.
  • Out-of-vocabulary (OoV) rate: 0.57% on test data.

Key Insights and Ideas

  • Kneser-Ney's Achilles' Heel: The most striking finding is that Kneser-Ney smoothing, despite its popularity and effectiveness on unpruned models, degrades dramatically under aggressive entropy pruning. This is a significant departure from traditional methods like Katz smoothing.
  • Two Sources of Mismatch: The paper identifies two main reasons for Kneser-Ney's poor performance with pruning:
  • Inaccurate Context Estimates: When pruning removes many higher-order n-grams, the model must "back-off" to lower-order estimates. Kneser-Ney's reliance on diversity counts for these lower-order estimates can lead to significantly different values compared to maximum likelihood estimates, creating a mismatch with the pruned model's structure.
  • Reliance on Pruned Estimates: After pruning, test data predictions are more likely to use these lower-order, potentially inaccurate, diversity-based estimates, further exacerbating the problem.
  • Katz Smoothing's Resilience: In contrast, Katz smoothing proves much more robust to aggressive pruning, maintaining better perplexity scores.
  • Seymore-Rosenfeld Pruning Helps, But Doesn't Solve: Using Seymore-Rosenfeld pruning (which uses relative frequencies for context estimates) improves Kneser-Ney's performance compared to Stolcke pruning, but it doesn't fully close the gap with Katz smoothing. This suggests the issue is not solely with context estimation but also with how Kneser-Ney uses diversity counts for back-off.
  • Practical Implications for Voice Search: The authors' large-scale experiments confirm these findings, showing that the choice of smoothing significantly impacts WER in real-world voice search systems when aggressive pruning is applied.

Key Results

  • Perplexity Degradation: Aggressively pruning Kneser-Ney models to 0.1% of their original size resulted in a relative perplexity increase of approximately 100-150% for 3-gram and 4-gram models, respectively (Tables 2 & 3). In contrast, Katz smoothing saw increases of around 50-65%.
  • Word Error Rate (WER) Impact: In their large-scale voice search setup, pruning Kneser-Ney and Katz models to 0.1% of their original size impacted WER significantly, with an approximate 10% relative degradation for Kneser-Ney compared to Katz.
  • Pruning Size Matters: Figure 1 visually demonstrates that Kneser-Ney models degrade much faster than Katz models as the pruned LM size decreases.

Limitations and Future Work

  • Limitations:
    • The paper primarily focuses on Stolcke pruning and its interaction with smoothing. While Seymore-Rosenfeld is discussed, the experimental depth is less.
  • The paper acknowledges that while WER and PPL correlate well, WER is the ultimate measure of success, and full WER results for the large-scale experiments are not detailed in the paper itself (though the impact is stated).
  • Future Work:
    • The authors suggest exploring mechanisms to address the remaining difference between Katz and Kneser-Ney smoothing after pruning. They reference a potential solution from another paper ([4]) that involves combining left-diversity counts with raw counts in a weighted manner, where the weighting depends on the pruning level.
  • Further investigation into alternative pruning strategies or modifications to Kneser-Ney smoothing that are more robust to aggressive pruning is implied.

Summary updated

BibTeX
@inproceedings{chelba2010study,
  author = {Ciprian Chelba and Thorsten Brants and Will Neveitt and Peng Xu},
  title = {{Study on interaction between entropy pruning and kneser-ney smoothing}},
  booktitle = {Interspeech},
  year = {2010},
}
Figure