Smoothing Techniques › Smoothing Techniques for N-gram Language Models

In the previous chapter on N-gram Language Models, we built a system for estimating the probability of a word given its history. We used maximum likelihood estimation (MLE): count how many times a particular n-gram occurs in training data, divide by the count of the context. Clean and intuitive. But there is a fundamental problem lurking in this approach, one that appears the moment you apply your model to any text it hasn't seen before.

The problem is zero probabilities. If your training corpus never contains the trigram "the crimson aardvark," MLE assigns it a probability of exactly zero. That's fine in isolation, but recall the chain rule: the probability of a sentence is the product of its word-level conditional probabilities. One zero anywhere in that product collapses the entire sentence probability to zero. The model claims that "the crimson aardvark ate the mango" is impossible, not just unlikely. For a language model, this is catastrophic: virtually any naturally occurring sentence will contain at least one n-gram your training data didn't cover.

This is the data sparsity problem, and smoothing is how we solve it. Smoothing is a family of techniques that redistribute probability mass away from seen n-grams to cover unseen ones. The core idea is deceptively simple: instead of assigning zero probability to unseen events, give them a small positive probability by "borrowing" a little mass from the events you have seen. The challenge is doing this redistribution in a way that is both principled and accurate, so that the resulting probability distribution still matches observed language.

Over the decades, researchers developed a rich progression of smoothing methods, each addressing shortcomings in the ones before it. This chapter walks through the full arc: starting with the naive Laplace approach, moving through Good-Turing estimation and its frequency-of-frequency insights, then exploring interpolation and backoff strategies for combining evidence from different n-gram orders, and finally arriving at Kneser-Ney smoothing, which remains one of the best-performing methods for n-gram models even today. Along the way, we'll understand what each method does, why it does it, and what failure mode it was designed to address.