Smoothing Techniques › Summary

This chapter covered the full family of smoothing techniques that make n-gram language models practical:

• The core problem: MLE assigns zero probability to any n-gram not seen in training, collapsing sentence probabilities to zero. Data sparsity is severe: the number of possible n-grams grows exponentially with order and vocabulary size, vastly outpacing any training corpus.
• Laplace (add-one) smoothing: Adds 1 to every count before normalizing. Simple and intuitive, but poor in practice because it over-redistributes probability mass. The fixed additive adjustment does not scale with count magnitude.
• Add-k smoothing: Generalizes Laplace with a tunable parameter $k < 1$. Better than Laplace but still uses a single discount for all counts and treats all unseen bigrams identically.
• Good-Turing estimation: Uses the frequency-of-frequency distribution to estimate adjusted counts. The formula $c^* = (c+1) N_{c+1} / N_c$ is principled and consistent, but unreliable for large counts where $N_c$ values are sparse.
• Interpolation and backoff: Combine multiple n-gram orders. Jelinek-Mercer interpolation mixes all orders with learned weights; Katz backoff uses the highest reliable order and backs off to lower ones when n-gram counts are zero.
• Absolute discounting: Subtracts a fixed discount $d \approx N_1/(N_1 + 2N_2)$ from every non-zero count and redistributes the saved mass through a lower-order model. Approximates Good-Turing with a single constant that works well empirically.
• Kneser-Ney smoothing: Replaces the lower-order MLE unigram distribution with a continuation count distribution, which measures how often a word appears in diverse preceding contexts. Words tightly bound to specific phrases (like "Francisco" after "San") get low continuation probability, while versatile words (like "the") get high continuation probability. This correctly captures the relevant information for backing off.
• Modified Kneser-Ney: Uses three separate discount values $d_1, d_2, d_{3+}$ for counts of 1, 2, and 3+, consistently outperforming single-discount Kneser-Ney. This is the version used in practical toolkits like KenLM.

The progression from Laplace to Kneser-Ney is a story of increasingly precise answers to the question: "What information in the training data is most informative for estimating probabilities of unseen events?" Laplace uses almost none of it. Good-Turing uses the frequency-of-frequency structure. Kneser-Ney uses the distributional diversity of each word's contexts. Each step improves on the previous method by using more of the structure of natural language.

In the next chapter, we'll formalize the perplexity metric used throughout this chapter to compare models, derive its relationship to cross-entropy and bits-per-character, and discuss why it's both a useful and sometimes misleading evaluation criterion.