Smoothing Techniques for N-gram Language Models: From Laplace to Kneser-Ney

N-gram language models have a fatal flaw: they assign zero probability to any sequence containing an n-gram not seen during training. A single unseen word combination causes the entire sentence probability to collapse to zero, making the model useless for real-world text. Smoothing techniques solve this problem by redistributing probability mass from observed n-grams to unseen ones, ensuring every possible sequence receives some non-zero probability.

This chapter explores the evolution of smoothing methods, from simple add-one smoothing to the sophisticated Kneser-Ney algorithm that powered speech recognition and machine translation systems for decades.

Consider a bigram model trained on a small corpus. You calculate probabilities by counting how often word pairs appear:

where:

• $P(w_i | w_{i-1})$: probability of word $w_i$ given the preceding word $w_{i-1}$
• $C(w_{i-1}, w_i)$: count of the bigram (how often the word pair appears together)
• $C(w_{i-1})$: count of the preceding word (how often it appears as context)

The problem emerges immediately. If your training corpus contains "the cat sat on the mat" but never "the cat ate the fish," then $P(\text{ate} | \text{cat}) = 0$. When computing the probability of a new sentence using the chain rule, a single zero multiplies everything to zero:

This is catastrophic. The sentence is perfectly grammatical, yet our model claims it's impossible.

The simplest solution is to pretend every n-gram occurred at least once. Add one to all counts before computing probabilities:

where:

• $P_{\text{Laplace}}(w_i | w_{i-1})$: the Laplace-smoothed probability of word $w_i$ given the preceding word $w_{i-1}$
• $C(w_{i-1}, w_i)$: count of the bigram (how often the word pair appears together)
• $C(w_{i-1})$: count of the context word (how often $w_{i-1}$ appears)
• $V$: vocabulary size (total number of unique words)

We add 1 to the numerator to give the specific bigram a "pseudocount." We add $V$ to the denominator because we're adding 1 to each of the $V$ possible words that could follow $w_{i-1}$. This ensures the probability distribution still sums to 1.

Let's trace through the math. Suppose "the cat" appears 5 times in our corpus, "the" appears 100 times, and our vocabulary has 10,000 words.

Without smoothing:

With Laplace smoothing:

The probability dropped by nearly two orders of magnitude. This is the fundamental problem with Laplace smoothing: it steals too much probability mass from observed events to give to unseen ones.

Consider a tiny corpus with vocabulary $V = \{a, b, c\}$ and these bigram counts:

The unigram counts are: $C(a) = 4$, $C(b) = 3$, $C(c) = 1$.

For MLE probabilities:

For Laplace-smoothed probabilities (with $V = 3$):

And for the unseen bigram (a, a):

Notice how the probabilities for observed bigrams decreased significantly to make room for the unseen one.

A natural improvement is to add a smaller constant $k < 1$ instead of 1:

where:

• $P_{\text{add-}k}(w_i | w_{i-1})$: the smoothed probability of word $w_i$ given the preceding word $w_{i-1}$
• $C(w_{i-1}, w_i)$: count of the bigram (how often the word pair appears together)
• $C(w_{i-1})$: count of the context word (how often $w_{i-1}$ appears)
• $k$: the smoothing constant, a value between 0 and 1 (typically 0.001 to 0.5)
• $V$: vocabulary size (total number of unique words)

The key insight is that we add $k$ to the numerator for the specific bigram, but we add $kV$ to the denominator because we're adding $k$ to each of the $V$ possible words that could follow $w_{i-1}$. This preserves the probability distribution property that all conditional probabilities given $w_{i-1}$ sum to 1.

With $k = 0.1$ and our earlier example:

This is still far from the original 0.05, but it's less aggressive than Laplace smoothing.

The optimal value of $k$ depends on your corpus and vocabulary size. You can tune it by:

1. Holding out a development set
2. Computing perplexity for different values of $k$
3. Selecting the $k$ that minimizes perplexity

Typical values range from 0.001 to 0.5. Smaller corpora often need larger $k$ values, while larger corpora can use smaller ones.

First, let's examine the basic statistics of our corpus:

Our small corpus yields a vocabulary of 12 unique tokens and 30 bigram instances. The most frequent bigram is ("the", "cat") appearing twice, which makes sense given our cat-and-dog themed sentences. This manageable size lets us trace through the smoothing calculations by hand if needed.

Let's implement add-k smoothing and see how different values of $k$ affect probability estimates:

We'll compare probabilities for an observed bigram ("the", "cat") and an unseen bigram ("the", "elephant"):

The MLE probability for P(cat|the) would be 2/10 = 0.2. With k=1.0 (Laplace), this drops to about 0.136, losing nearly a third of the probability mass. As k decreases to 0.001, the probability climbs back to 0.196, much closer to the MLE.

For the unseen bigram "the elephant," we see the flip side: larger k values give it more probability (0.045 with k=1.0), while smaller values give it less (0.0001 with k=0.001). This is the core trade-off in smoothing: how much probability to steal from observed events to cover unseen ones.

The plot reveals the fundamental trade-off. As $k$ increases, the blue curve (observed bigram) falls while the red curve (unseen bigram) rises. The gray dotted line shows the MLE estimate we're trying to preserve for observed events. Choosing $k$ means finding the right balance: small enough to keep observed probabilities reasonable, large enough to give unseen events meaningful coverage.

Add-k smoothing has an arbitrary feel to it. Why add 0.1 rather than 0.05 or 0.2? Good-Turing smoothing takes a fundamentally different approach: instead of picking a constant, it uses the statistical structure of the data itself to determine how much probability mass should go to unseen events.

The core idea is elegant. If we collected more data, some n-grams that currently appear zero times would appear once. Some that appear once would appear twice. Good-Turing asks: can we use the current distribution of counts to predict this future behavior?

The answer is yes. Consider n-grams that appear exactly once in our corpus (called singletons or hapax legomena). These are the n-grams that barely made it into our observations. If we had slightly less data, many of them would have count zero. Conversely, if we had slightly more data, many currently unseen n-grams would become singletons.

This suggests that the number of singletons tells us something about unseen n-grams. More precisely: the probability mass that should go to unseen events is proportional to the number of singletons.

Good-Turing formalizes this intuition by replacing the observed count $c$ with an adjusted count $c^*$:

where:

• $c$: the original observed count for an n-gram
• $c^*$: the adjusted (discounted) count that replaces $c$
• $N_c$: the number of distinct n-grams that appear exactly $c$ times in the corpus
• $N_{c+1}$: the number of distinct n-grams that appear exactly $c+1$ times

The formula works by looking one step ahead in the count distribution. The ratio $\frac{N_{c+1}}{N_c}$ tells us how the frequency of frequencies changes as counts increase. If there are relatively few n-grams with count $c+1$ compared to those with count $c$, the ratio is small, which means count $c$ is probably an overestimate that should be discounted heavily.

For unseen n-grams (count 0), the adjusted count becomes:

where:

• $N_1$: the number of singletons (n-grams appearing exactly once)
• $N_0$: the number of possible n-grams that were never observed

This formula estimates how much "count" each unseen n-gram deserves by distributing the singleton count across all unseen events.

The total probability mass reserved for all unseen events is:

where:

• $P_0$: the total probability mass allocated to all unseen n-grams combined
• $N_1$: the number of singletons
• $N$: the total number of n-gram tokens in the corpus

This elegant result says: the fraction of probability mass for unseen events equals the fraction of tokens that are singletons. If 10% of your corpus consists of words that appear only once, then roughly 10% of probability mass should go to unseen events.

Suppose we have a corpus with these frequency counts:

For bigrams that appear exactly once:

This means a bigram seen once should be treated as if it appeared only 0.446 times. The "missing" 0.554 goes to unseen bigrams.

For unseen bigrams:

Now we can examine the frequency of frequencies distribution and compute adjusted counts:

Our corpus shows a typical pattern: many bigrams appear only once (singletons), fewer appear twice, and so on. The adjusted count for singletons (c=1) drops significantly because Good-Turing uses the ratio of doubletons to singletons. When this ratio is less than 0.5, singletons get discounted heavily.

The distribution follows the expected pattern: most bigrams are rare (appearing only once or twice), while a few appear frequently. This Zipfian distribution is why Good-Turing works: the steep decline from $N_1$ to $N_2$ to $N_3$ provides the ratios needed to estimate appropriate discounts.

Good-Turing works well for small counts but becomes unreliable for larger counts where $N_c$ values become sparse or zero. In practice, it's often combined with other techniques.

Instead of modifying counts, we can use information from lower-order n-grams when higher-order ones are unreliable. Two strategies exist:

Backoff: Use the lower-order model only when the higher-order count is zero. If we've never seen the trigram "the cat ate," back off to the bigram "cat ate."

Interpolation: Always combine evidence from multiple n-gram orders using weighted averaging.

Linear interpolation mixes unigram, bigram, and trigram probabilities:

where:

• $P_{\text{interp}}(w_3 | w_1, w_2)$: the interpolated probability of word $w_3$ given the two preceding words $w_1$ and $w_2$
• $\lambda_1, \lambda_2, \lambda_3$: interpolation weights that sum to 1 ($\lambda_1 + \lambda_2 + \lambda_3 = 1$)
• $P(w_3)$: unigram probability (how likely $w_3$ is regardless of context)
• $P(w_3 | w_2)$: bigram probability (how likely $w_3$ is given only the immediately preceding word)
• $P(w_3 | w_1, w_2)$: trigram probability (how likely $w_3$ is given both preceding words)

The formula computes a weighted average of three different probability estimates. The unigram term provides a baseline that's always non-zero for known words. The bigram term adds local context. The trigram term captures the full available context. By combining all three, interpolation ensures non-zero probabilities even when higher-order n-grams are missing.

The weights $\lambda$ are typically learned from held-out data using the EM algorithm or grid search.

A simpler approach that works surprisingly well for large-scale systems is "stupid backoff." It doesn't produce true probabilities but scores that work well for ranking:

where:

• $S(w_i | w_{i-n+1}^{i-1})$: score for word $w_i$ given the preceding $n-1$ words
• $w_{i-n+1}^{i-1}$: shorthand notation for the sequence of words from position $i-n+1$ to $i-1$ (the context)
• $w_{i-n+1}^i$: the full n-gram including both context and the target word $w_i$
• $C(w_{i-n+1}^i)$: count of the full n-gram in the training corpus
• $C(w_{i-n+1}^{i-1})$: count of the context (the $n-1$ words preceding $w_i$)
• $\alpha$: backoff weight (typically 0.4), applied as a penalty when backing off to lower-order n-grams
• $w_{i-n+2}^{i-1}$: the shorter context used when backing off (drops the oldest word)

The formula is recursive: if the full n-gram has been observed, use the standard relative frequency estimate. If not, multiply by $\alpha$ and recursively compute the score using a shorter context. Each backoff step incurs the $\alpha$ penalty, so scores decrease the more we back off.

Google used this for their web-scale language models because it's fast and the scores work well for ranking despite not being proper probabilities.

The weight distribution matters. When we favor trigrams ($\lambda_3 = 0.6$), the probability is higher because the trigram "<s> the cat" appears in our corpus. When we favor unigrams ($\lambda_1 = 0.5$), we rely more on how often "cat" appears overall, which dilutes the context-specific information.

Interpolation provides a smooth fallback mechanism. Even when the trigram count is zero, the bigram and unigram components contribute to a non-zero probability.

The smoothing methods we've seen so far share a common limitation: they treat the backoff distribution as a simple unigram model based on word frequency. But word frequency alone can be misleading. Kneser-Ney smoothing addresses this with two innovations that, together, create the most effective n-gram smoothing method ever developed.

To understand why Kneser-Ney matters, consider the phrase "San Francisco." In any corpus about California, the word "Francisco" appears frequently. A standard unigram model would assign it high probability.

But here's the catch: "Francisco" almost always follows "San." It rarely appears in other contexts. If we're backing off from an unseen trigram like "visited beautiful Francisco," a frequency-based unigram model would say "Francisco" is likely. Yet intuitively, we know "Francisco" is an unlikely word to appear after "beautiful" because it almost never starts a new context on its own.

This observation leads to Kneser-Ney's key insight: when backing off, we shouldn't ask "how often does this word appear?" but rather "in how many different contexts does this word appear?"

The first innovation is straightforward. Instead of using Good-Turing's complex count adjustments, Kneser-Ney subtracts a fixed discount $d$ from every observed count:

where:

• $P_{\text{abs}}(w_i | w_{i-1})$: the absolute discounting probability of word $w_i$ given context $w_{i-1}$
• $C(w_{i-1}, w_i)$: count of the bigram in the training corpus
• $C(w_{i-1})$: count of the context word
• $d$: the fixed discount value subtracted from each count (typically 0.75)
• $\max(\cdot, 0)$: ensures the discounted count never goes negative
• $\lambda(w_{i-1})$: an interpolation weight that depends on the context (defined below)
• $P_{\text{lower}}(w_i)$: a lower-order probability estimate (e.g., unigram probability)

The formula has two terms:

1. Discounted probability: The observed count minus $d$, divided by the context count. The $\max$ ensures we never go negative.
2. Backoff contribution: An interpolation weight $\lambda$ times a lower-order probability.

The discount $d$ is typically 0.75, a value derived from theoretical analysis of Good-Turing estimates. By subtracting a fixed amount rather than a percentage, absolute discounting treats all observed n-grams more uniformly. An n-gram seen 5 times loses 0.75 (15%), while one seen 2 times loses 0.75 (37.5%). This makes sense: rare observations are less reliable and should be discounted more aggressively in relative terms.

The second innovation is where Kneser-Ney truly shines. For the backoff distribution $P_{\text{lower}}$, it doesn't use raw word frequency. Instead, it uses continuation probability: the proportion of unique contexts in which a word appears.

where:

• $P_{\text{continuation}}(w)$: the continuation probability of word $w$
• $|\{w_{i-1} : C(w_{i-1}, w) > 0\}|$: the number of unique words that precede $w$ in the corpus (i.e., how many different contexts $w$ appears in)
• $|\{(w_{i-1}, w_i) : C(w_{i-1}, w_i) > 0\}|$: the total number of unique bigram types in the corpus
• $C(w_{i-1}, w)$: count of the bigram $(w_{i-1}, w)$

The vertical bars $|\cdot|$ denote set cardinality (the number of elements in the set). The numerator counts distinct preceding words, not total occurrences.

Let's unpack the intuition:

• Numerator: Count how many unique words precede $w$. For "Francisco," this might be just 1 (only "San" precedes it). For "the," it might be hundreds.
• Denominator: The total number of unique bigram types in the corpus, serving as a normalizing constant.

Returning to our example: "Francisco" has high frequency but low continuation count (appears after few unique words). "The" has high frequency and high continuation count (appears after many unique words). When backing off, "the" deserves higher probability than "Francisco" because it's a more versatile word that genuinely appears in diverse contexts.

The complete Kneser-Ney formula for the highest-order n-gram combines both innovations:

where:

• $P_{\text{KN}}(w_i | w_{i-n+1}^{i-1})$: the Kneser-Ney smoothed probability of word $w_i$ given the preceding $n-1$ words
• $w_{i-n+1}^{i-1}$: shorthand for the context sequence $(w_{i-n+1}, w_{i-n+2}, \ldots, w_{i-1})$, the preceding $n-1$ words
• $w_{i-n+1}^i$: the full n-gram including the target word, $(w_{i-n+1}, \ldots, w_{i-1}, w_i)$
• $C(w_{i-n+1}^i)$: count of the full n-gram in the training corpus
• $C(w_{i-n+1}^{i-1})$: count of the context (how often the $n-1$ word sequence appears)
• $d$: discount value (typically 0.75)
• $\lambda(w_{i-n+1}^{i-1})$: interpolation weight for this context (defined below)
• $P_{\text{KN}}(w_i | w_{i-n+2}^{i-1})$: the recursive lower-order Kneser-Ney probability using a shorter context

The interpolation weight $\lambda$ ensures probability mass is conserved. It equals the total amount discounted from all observed continuations:

where:

• $\lambda(w_{i-n+1}^{i-1})$: the interpolation weight for context $w_{i-n+1}^{i-1}$
• $d$: the discount value (typically 0.75)
• $C(w_{i-n+1}^{i-1})$: total count of the context sequence
• $|\{w : C(w_{i-n+1}^{i-1}, w) > 0\}|$: the number of unique words that follow this context in the training corpus

This formula says: take the discount $d$, multiply by the number of unique words that follow this context, and divide by the total context count. The result is exactly the probability mass we "stole" from observed n-grams, which we now redistribute through the backoff distribution.

For lower-order distributions (used in the recursive backoff), raw counts are replaced with continuation counts. This is what makes the "San Francisco" example work correctly: "Francisco" has low continuation count, so it receives low probability in the backoff distribution despite its high raw frequency.

Let's examine the continuation counts and compute Kneser-Ney probabilities for several test bigrams:

The continuation counts reveal which words are versatile. Words like "the" and "cat" appear after multiple different words, giving them higher continuation probability. The word "" (end of sentence) also has high continuation count because every sentence ends with it.

The scatter plot illustrates Kneser-Ney's key insight. Words near or above the diagonal line are "versatile," appearing in many different contexts relative to their frequency. Words below the line are context-dependent, appearing frequently but in limited contexts. In a larger corpus, "Francisco" would appear far below the diagonal (high frequency, low continuation count), while common function words like "the" would appear on or above it.

Kneser-Ney assigns non-zero probability to the unseen bigram "the elephant" through the continuation probability term, while keeping observed bigrams at reasonable levels. The discount of 0.75 is subtracted from each observed count, and the freed probability mass flows to the continuation distribution.

Modified Kneser-Ney improves on the original by using three different discount values based on the count:

where:

• $d(c)$: the discount to apply to n-grams with count $c$
• $d_1$: discount for singletons (n-grams appearing exactly once)
• $d_2$: discount for doubletons (n-grams appearing exactly twice)
• $d_3$: discount for n-grams appearing three or more times

These discount values are estimated from the training data using the frequency of frequencies:

where:

• $Y = \frac{N_1}{N_1 + 2N_2}$: a normalization factor based on singleton and doubleton counts
• $N_1$: number of n-grams appearing exactly once (singletons)
• $N_2$: number of n-grams appearing exactly twice (doubletons)
• $N_3$: number of n-grams appearing exactly three times
• $N_4$: number of n-grams appearing exactly four times

The formulas derive from Good-Turing theory. Each discount $d_c$ is computed as $c - (c+1) \cdot Y \cdot \frac{N_{c+1}}{N_c}$, which adjusts the base count by a factor that depends on how the frequency of frequencies changes. The $Y$ factor normalizes for the overall shape of the distribution.

The intuition is that n-grams seen once are more likely to be noise than those seen twice, which are more likely to be noise than those seen three or more times. The discounts typically increase with count ($d_1 < d_2 < d_3$), but since lower counts are smaller to begin with, the relative impact is greater for rare n-grams. Subtracting 0.7 from a count of 1 removes 70% of the probability mass, while subtracting 1.3 from a count of 10 removes only 13%.

Computing the discount parameters from our corpus statistics:

The Y factor normalizes based on the ratio of singletons to doubletons. With our small corpus, the discount values are at their boundary conditions. On larger corpora, typical values are around $d_1 \approx 0.7$, $d_2 \approx 1.0$, and $d_3 \approx 1.3$. The progression makes intuitive sense: we discount singletons more aggressively because they're more likely to be noise, while n-grams seen three or more times are more reliable and get smaller relative discounts.

Now let's put all these methods side by side and compare how they handle the same probability estimation task. We'll compute probabilities for words following "the," including both observed and unseen words.

The chart reveals the trade-offs clearly. MLE gives the highest probabilities to observed words but zeros for unseen ones. Add-1 smoothing flattens everything too much. Add-0.01 and Kneser-Ney strike a better balance, keeping observed words relatively high while providing coverage for unseen words.

The exact probability values are shown in the table below:

The numbers confirm our observations from the chart. For observed words like "cat" and "dog," MLE gives the highest probability, but Add-1 drops it dramatically. Kneser-Ney maintains probabilities closer to MLE for observed words while still providing coverage for unseen ones like "elephant" and "zebra." This balance is why Kneser-Ney became the standard for production language models.

Smoothing techniques revolutionized n-gram language modeling but are not without constraints. Understanding both their limitations and historical impact provides context for why neural language models eventually superseded them.

Smoothing techniques, despite their sophistication, have inherent limitations:

• Fixed context window: All n-gram smoothing methods are bounded by the Markov assumption. No amount of smoothing helps when the relevant context is beyond the n-gram window.
• Vocabulary dependence: Performance degrades with vocabulary size. As $V$ grows, the number of possible unseen n-grams explodes.
• Domain sensitivity: Smoothing parameters tuned on one domain may perform poorly on another. A model trained on news text with optimal smoothing for that domain may still struggle with social media text.
• No semantic awareness: Smoothing treats "the cat ate" and "the cat flew" identically if both are unseen. It cannot use semantic knowledge that cats are more likely to eat than fly.

Despite these limitations, smoothing techniques were foundational to practical NLP:

• Speech recognition: Kneser-Ney smoothing powered speech recognition systems for decades, enabling reliable transcription even for novel word combinations.
• Machine translation: Statistical MT systems relied heavily on smoothed language models to score translation candidates.
• Spell correction: Smoothed models help distinguish between plausible and implausible word sequences for context-aware spelling correction.
• Established evaluation practices: The development of smoothing techniques led to rigorous evaluation methods like perplexity comparison on held-out data.

The techniques in this chapter represent the pinnacle of count-based language modeling. They squeezed remarkable performance from simple statistics. But they also revealed the ceiling: no matter how clever the smoothing, n-gram models cannot capture long-range dependencies or semantic similarity. This limitation motivated the shift to neural language models, which learn continuous representations that naturally generalize to unseen word combinations.

Smoothing techniques solve the zero probability problem in n-gram language models by redistributing probability mass from observed to unseen events.

Key takeaways:

• Laplace (add-one) smoothing is simple but steals too much probability from observed events
• Add-k smoothing improves by using smaller constants, with $k$ tuned on held-out data
• Good-Turing smoothing uses frequency of frequencies to estimate probability mass for unseen events
• Interpolation combines evidence from multiple n-gram orders using learned weights
• Kneser-Ney smoothing uses absolute discounting and continuation probability, making it the gold standard for n-gram models
• Modified Kneser-Ney refines discounting with count-dependent values

The choice of smoothing method matters significantly. On large corpora, Kneser-Ney typically outperforms simpler methods by 10-20% in perplexity. For small corpora or quick experiments, add-k smoothing provides a reasonable baseline with minimal implementation effort.

These techniques represent the culmination of decades of statistical NLP research. While neural language models have largely superseded n-gram models for most applications, understanding smoothing provides essential intuition about probability estimation, the bias-variance trade-off, and the importance of handling unseen events, concepts that remain central to modern NLP.

When implementing smoothing techniques, these parameters have the most impact on model performance:

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about smoothing techniques for n-gram language models.