Smoothing Techniques › Kneser-Ney Smoothing

We now arrive at Kneser-Ney smoothing (Kneser and Ney, 1995), which is widely considered the best-performing standard smoothing method for n-gram language models. Kneser-Ney builds directly on absolute discounting but introduces a brilliant new idea for the lower-order distribution, one that addresses a fundamental flaw in all previous methods.

In absolute discounting (and Katz backoff), when we back off to a lower-order model, we use the ordinary unigram frequency as the lower-order distribution. A word that appears 10,000 times gets a higher lower-order probability than a word that appears 500 times. This seems natural: more frequent words should be more probable.

But this is wrong in a subtle way that has significant consequences. Consider the word "Francisco." It appears very frequently in many English corpora, but almost exclusively in the context "San Francisco." As a unigram, "Francisco" has high frequency. As a standalone word not following "San," it appears very rarely indeed. If our trigram probability for some context "...San Francisco" is unavailable and we back off to the unigram probability of "Francisco," we're dramatically overestimating how likely "Francisco" is to appear in that novel context.

The correct lower-order probability should reflect not how often a word appears total, but how often it appears in diverse contexts. A word like "Francisco" that's highly constrained to specific contexts should have a low lower-order probability. A word like "the" that appears after a huge variety of words should have a high lower-order probability. The unigram frequency conflates these two things, because a word can accumulate high frequency either by appearing often across many contexts or by appearing very often in just one or two fixed phrases.

This is not a corner case. Many high-frequency words in English are tightly bound to specific contexts: "Francisco" follows "San," "Vegas" follows "Las," "Kong" follows "Hong," "Turing" follows "Alan" in technical text. Using raw unigram frequency as the lower-order distribution systematically overestimates such words when they appear in novel contexts.

Kneser and Ney formalize this intuition with the continuation probability: the probability that a word $w$ completes a new, previously unseen bigram. This is estimated as the number of distinct preceding words that $w$ has appeared with, divided by the total number of distinct bigrams:

$$P_{\text{KN}}(w) = \frac{\bigl|\{v : C(v, w) > 0\}\bigr|}{\bigl|\{(u, v) : C(u, v) > 0\}\bigr|}$$

where:

• $\bigl|\{v : C(v, w) > 0\}\bigr|$: the number of distinct words $v$ that precede $w$ in the training corpus (the "continuation count" of $w$)
• $\bigl|\{(u, v) : C(u, v) > 0\}\bigr|$: the total number of distinct bigrams in the training corpus (is a normalizing constant)

For "Francisco," the continuation count is small: only "San" precedes it in typical text (and perhaps "Vice" in phrases like "Vice Francisco" in a translated corpus), so the continuation count is essentially 1. The KN unigram probability for "Francisco" is therefore very small.

For "the," the continuation count is enormous: "the" follows virtually every kind of word, so it has appeared as the second word in many thousands of distinct bigrams. The KN unigram probability for "the" is very high, correctly reflecting that it can complete almost any context.

For "on," the situation is intermediate: "on" follows many words (sat on, walked on, focused on, based on, ...) and has a moderate continuation count that accurately reflects its versatility as a word that can appear in many different positions.

This directly captures the property we want: the lower-order probability of a word should measure its tendency to appear in new, diverse contexts, not just its raw frequency.

Kneser-Ney smoothing for bigrams combines the discounted bigram term (using the same absolute discount $d$ from the previous section) with the continuation probability as the lower-order distribution:

$$P_{\text{KN}}(w_i \mid w_{i-1}) = \frac{\max\bigl(C(w_{i-1}, w_i) - d,\ 0\bigr)}{C(w_{i-1})} + \lambda(w_{i-1}) \cdot P_{\text{KN}}(w_i)$$

where:

• $d$: the discount parameter (typically 0.75, estimated as $N_1 / (N_1 + 2N_2)$ from the training bigram counts)
• $\lambda(w_{i-1}) = \dfrac{d \cdot \bigl|\{w : C(w_{i-1}, w) > 0\}\bigr|}{C(w_{i-1})}$: the interpolation weight (probability mass freed up by discounting)
• $P_{\text{KN}}(w_i)$: the Kneser-Ney continuation probability for $w_i$, as defined above

The structure is identical to absolute discounting, with one difference: $P_{\text{lower}}$ is replaced by $P_{\text{KN}}$, the continuation probability, instead of the MLE unigram probability.

For higher-order models (trigrams, etc.), the recursion continues at each level using continuation counts rather than raw counts. For a trigram model:

$$P_{\text{KN}}(w_i \mid w_{i-2}, w_{i-1}) = \frac{\max\bigl(C(w_{i-2}, w_{i-1}, w_i) - d,\ 0\bigr)}{C(w_{i-2}, w_{i-1})} + \lambda(w_{i-2}, w_{i-1}) \cdot P_{\text{KN}}(w_i \mid w_{i-1})$$

where:

• $C(w_{i-2}, w_{i-1}, w_i)$: the raw trigram count
• $C(w_{i-2}, w_{i-1})$: the raw bigram count of the context
• $\lambda(w_{i-2}, w_{i-1})$: the interpolation weight at the trigram level, defined analogously to the bigram case
• $P_{\text{KN}}(w_i \mid w_{i-1})$: the Kneser-Ney bigram probability (using continuation counts at the bigram level)

At the bigram level within the trigram recursion, the "count" for $C(w_{i-1}, w_i)$ is replaced by the number of distinct words that precede the bigram $w_{i-1} w_i$, rather than the raw bigram count. This generalization ensures that at every level of the recursion, the distribution reflects diversity of contexts rather than raw frequency. The key property that makes Kneser-Ney so powerful is this consistent application of continuation counts at all lower-order levels.

Modified Kneser-Ney (Chen and Goodman, 1998) extends the basic Kneser-Ney by using different discount values for different count magnitudes, rather than a single discount $d$. The key observation is that n-grams seen exactly once are much more uncertain than n-grams seen 10 times, and both deserve different treatment than n-grams seen 100 times. A single discount parameter can't capture all three behaviors simultaneously.

The modified probability formula becomes:

$$P_{\text{MKN}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) - D\bigl(C(w_{i-1}, w_i)\bigr)}{C(w_{i-1})} + \lambda(w_{i-1}) \cdot P_{\text{MKN}}(w_i)$$

where $D(c)$ is the count-dependent discount function:

$$D(c) = \begin{cases} 0 & \text{if } c = 0 \\ d_1 & \text{if } c = 1 \\ d_2 & \text{if } c = 2 \\ d_{3+} & \text{if } c \geq 3 \end{cases}$$

The three discount values $d_1, d_2, d_{3+}$ are estimated from the data using frequency-of-frequency counts. The estimation procedure introduces an auxiliary quantity $Y$ and then computes each discount:

$$\begin{aligned} Y &= \frac{N_1}{N_1 + 2N_2} \\[4pt] d_1 &= 1 - 2Y \frac{N_2}{N_1} \\[4pt] d_2 &= 2 - 3Y \frac{N_3}{N_2} \\[4pt] d_{3+} &= 3 - 4Y \frac{N_4}{N_3} \end{aligned}$$

where:

• $Y$: auxiliary normalization factor derived from singleton and doubleton counts
• $N_1, N_2, N_3, N_4$: frequency-of-frequency counts (number of distinct bigrams with count 1, 2, 3, 4 respectively)
• $d_1, d_2, d_{3+}$: the discounts for n-grams seen once, twice, or three-or-more times

The intuition behind these formulas is that they are derived from the Good-Turing framework, setting each discount to approximately minimize the expected squared error between the discounted counts and the "true" expected counts implied by Good-Turing. Because singletons are the most uncertain (by definition, we've only seen them once), they receive the largest absolute discount. Doubletons are more stable, and n-grams seen three or more times are treated as reliable enough to discount less aggressively.

In practice, $d_1$ typically comes out around 0.5-0.6, $d_2$ around 0.7-0.8, and $d_{3+}$ around 0.8-0.9. This graduated discounting scheme more accurately matches the Good-Turing ideal than a single discount value.

Chen and Goodman showed that modified Kneser-Ney consistently outperforms the original single-discount version across a variety of corpora and n-gram orders. Modified Kneser-Ney is the version used in most practical implementations today, including the popular KenLM toolkit, which is one of the most widely used n-gram language model implementations in NLP and speech recognition.