Kneser-Ney smoothing for bigrams

Fill the gap: "I can't see without my reading ___." Every English speaker says "glasses". Now suppose a Bigram model has never seen the pair (reading, glasses), or has seen it so rarely that it must lean on a lower-order estimate. With classic Backoff or Absolute discounting, that lower-order estimate is the Unigram probability P(w), and in a corpus full of news about "Hong Kong" the word Kong is very frequent.

Make it concrete with the toy corpus used throughout this part: C(Hong Kong) = 30 and one each of reading glasses, sun glasses, safety glasses and my glasses. Count the second word of each of the 34 bigram tokens. Kong appears 30 times and glasses 4 times, so the maximum-likelihood unigram gives P(Kong) = 30 / 34 ≈ 0.882 and P(glasses) = 4 / 34 ≈ 0.118. Absolute discounting with d = 0.75 keeps 1 − 0.75 = 0.25 for the one observed bigram after "reading" and spreads the freed 0.75 by the unigram:

That gives P_AD(Kong | reading) = 0.75 × 0.882 ≈ 0.662 and P_AD(glasses | reading) = 0.25 + 0.75 × 0.118 ≈ 0.338. Kong, a word that has only ever followed Hong, gets about twice the probability of the word that actually fits. (The slides state the problem in words; these numbers are ours, computed from the slide 88 corpus.)

The failure is in the question, not the arithmetic. When the model backs off, it is in a situation it has not seen: this history has not been followed by this word before. The useful question there is not "how likely is w?" but "how likely is w to show up as a novel continuation, after a context it has never followed?" Jurafsky and Martin phrase it exactly that way, and the answer to the second question is the Continuation probability, the lower-order distribution of Kneser-Ney smoothing. Raw frequency is a poor proxy for it because frequency can be concentrated: thirty tokens of Kong all come from one fixed phrase, which tells us nothing about Kong turning up somewhere new. This is the same Sparsity problem as before, now hitting the fallback instead of the main estimate.

Look at the words immediately to the left of each target. Kong has exactly one left neighbour, Hong. glasses has four: reading, sun, safety and my. Kong appears 30 times, but every one of those tokens is the same context repeated, so it earns credit for only one. That number of distinct left neighbours is the Continuation count:

To turn it into a probability, divide by the total number of bigram types, |{(u, w′) : C(uw′) > 0}|. The reasoning is that every bigram type was a novel continuation the first time it appeared, so the set of bigram types is the full record of "a word showed up in a new context", and each word's share of that record is its continuation probability. Jurafsky and Martin also write the denominator as the sum of every word's continuation count (Eq. C.6). The two are the same number, because each bigram type contributes one to exactly one word's count; in the toy corpus both equal 5.

This is a different kind of Relative frequency: the unit being counted is a context, not a token. As Jurafsky and Martin put it, a frequent word occurring in only one context will have a low continuation probability, and SRILM's manual describes its lower-order Kneser-Ney estimate as proportional to the number of unique words that precede it in the training data. The same machinery handles any vocabulary: the words "Francisco" (almost always after San) and "York" (after New) look just like Kong.

Take P_KN(glasses | reading) in Kneser-Ney smoothing. The bigram "reading glasses" was seen once. The first term keeps what that count earned after paying the discount, (1 − 0.75) / 1 = 0.25. The second term adds a share of the freed mass, chosen by how widely glasses is used as a continuation. Written in general:

The denominator is the count of $w_{i-1}$ as a history, $\sum_{v} C(w_{i-1} v)$, which Jurafsky and Martin write explicitly in Eq. C.1 and C.8. The second term scales the Continuation probability by the Backoff weight (lambda) λ of the history, the mass the discount freed. Everything else is inherited: the Discounting step is exactly absolute discounting, and the structure is that of Linear interpolation with one difference that matters a lot, the lower order is P_cont instead of the Maximum likelihood estimation unigram.

The model is called interpolated because the second term is added for every word, even for bigrams that were seen. A backoff version of Kneser-Ney uses the continuation term only when $C(w_{i-1} w_i) = 0$ and rescales it accordingly. Both exist in practice: SRILM builds either, and its -interpolate flag selects the interpolated form. Kneser and Ney introduced the method in 1995, and Chen and Goodman's large comparison found that a Kneser-Ney variant consistently outperforms all the other smoothing algorithms they evaluated.

History "reading" has one token and one continuation type. Discounting that single bigram removes 0.75 / 1 = 0.75 of the probability mass, so the continuation term must hand out exactly 0.75: λ(reading) = 0.75. History "Hong" has 30 tokens and still one type, so discounting frees only 0.75 / 30 = 0.025. The Backoff weight (lambda) is not chosen; it is whatever the discount removed.

Read it as two factors. d / C(h) is how much one discount costs in probability units for this history, and the set size N1+(h •) is how many times the discount was paid, once per distinct word that follows h. The product is the total mass removed, and the proof that the distribution is still a proper one is three lines long.

The d = 0.75 used throughout is the same discount Part 07 measured: the Church and Gale held-out experiment held-out table shows counts of 2 to 9 shrinking by about 0.75, and d = n1 / (n1 + 2 n2) estimates it from counts of counts. Kneser-Ney inherits that discount unchanged; what it changes is where the freed mass goes.

Here is the full computation on the slide corpus. Every Kneser-Ney smoothing question, by hand or in code, follows the same order: continuation probabilities first, then the weight of the history, then each word's discounted term and continuation term, and finally a check that the probabilities sum to 1.

Notice where glasses gets its probability. The bigram "reading glasses" contributes only 0.25; the other 0.6 arrives through the continuation term, because glasses is a word that turns up after many different words. With a single observation of the history, the model trusts the history little (λ is large) and the continuation distribution does most of the work.

Put the two models side by side. After "reading", frequency-unigram Backoff gave Kong about 0.662 and glasses about 0.338; Kneser-Ney smoothing gives Kong 0.15 and glasses 0.85. The ranking flips. But does Kneser-Ney now treat Kong unfairly where Kong belongs? Check the history Hong, which the slides start and leave unfinished.

C(Hong) = 30 with one continuation type, so λ(Hong) = 0.75 / 30 × 1 = 0.025. Then P_KN(Kong | Hong) = 29.25 / 30 + 0.025 × 0.2 = 0.975 + 0.005 = 0.98 and P_KN(glasses | Hong) = 0 + 0.025 × 0.8 = 0.02, which sum to 1. Kong keeps almost all the mass after Hong. Kneser-Ney did not punish Kong; it only removed Kong's unearned advantage in contexts it was never seen in.

The two histories show the full logic. Where the history is strong evidence, λ is tiny and the bigram dominates. Where the history is thin, λ is large and the continuation distribution decides, and there diversity beats frequency. The slogan to remember is that backoff should model continuation diversity, not token frequency.

From the toy to real toolkits

Real systems use Modified Kneser-Ney, which replaces the single d with three discounts, D1, D2 and D3+, for n-grams seen once, twice, and three or more times (JM C.2; Part 09 derives them). It is the default in KenLM, whose documentation says it estimates unpruned language models with modified Kneser-Ney smoothing, and in SRILM through -kndiscount (with -ukndiscount for the original single-discount version). Heafield and colleagues built an unpruned modified Kneser-Ney model on 126 billion tokens on one machine with 140 GB of RAM in 2.8 days, and it gained 0.8 BLEU in the WMT 2013 translation task.