Recursive and modified Kneser-Ney

Start from the bigram formula of Part 08: a discounted bigram term plus λ(h) times a lower-order distribution. Now lift it one level. For a trigram model and the history "her reading", the probability of the next word is the discounted trigram term plus λ(her reading) times P_KN(w | reading). That bigram probability is itself a Kneser-Ney estimate, so it in turn is a discounted bigram term plus λ(reading) times the unigram level. One formula, applied to shorter and shorter histories, covers every order.

The slide leaves λ undefined for the general form, but it is forced by the same argument as in part 08. The Absolute discounting step removes d from every n-gram type that follows the history h, and the backoff weight must hand exactly that mass to the shorter history:

Because λ(h) equals the removed mass, each level sums to 1 on its own, provided the level below is a proper distribution. The proof is the three-line argument from Part 08, applied once per level. This is Linear interpolation with weights that are computed rather than tuned, and it is what Chen and Goodman found works best: Heafield and colleagues summarize their result as the recursion p(w_n | w_1^(n−1)) = u(w_n | w_1^(n−1)) + b(w_1^(n−1)) p(w_n | w_2^(n−1)), where u is the discounted term and b the backoff weight. The SRILM manual writes the same thing as p(a_z) = g(a_z) + bow(a_) p(_z) and adds that each n-gram order uses a different discounting constant.

The recursion writes c_KN everywhere, and the whole method depends on what that count means at each level. Take a small corpus of seven sentences, with no boundary tokens to keep the arithmetic short:

The bigram "reading glasses" occurs 3 times: twice after "her" and once after "his". At the bigram level of a trigram model, though, Kneser-Ney does not use that raw count. It uses the number of distinct words seen immediately to its left, which is 2 ({her, his}). The two copies of "her reading glasses" count once. The same rule applies one level further down: "glasses" occurs 4 times but follows only 2 distinct words ({reading, sun}), and "kong" occurs 3 times but always after "hong", so its count is 1.

The Continuation count is the number of unique single-word contexts, which for a bigram reads:

The denominators switch too. At the bigram level the history "reading" has Σ_v c_KN(reading v) = 2, not C(reading) = 3, because every term in the sum is a continuation count. At the unigram level, dividing c_KN(w) by Σ_w c_KN(w) gives back the Continuation probability of Part 08 (before discounting), so the bigram model there was simply the two-level case of this recursion. SRILM's manual puts the rule in one sentence: the modified probability for a lower-order n-gram is proportional to the number of unique words that precede it.

The last row of the table shows why the boundary edge case matters. "she" begins every sentence it is in, so nothing ever precedes it and its continuation count is 0. In a real model with Sentence boundary tokens, every sentence starts with <s>, and nothing can precede <s> either. If n-grams starting with <s> used continuation counts, they would all collapse to zero. Both KenLM and SRILM therefore keep raw counts for n-grams that start with <s>: Heafield defines the adjusted count as a(w) = c(w) when the order is the highest or w_1 = <s>, and SRILM says only the highest-order n-grams and n-grams that start with <s> keep their regular counts. The slide omits this exception.

Part 08 ended with P_KN(Hong | reading) = 0, because Hong never appeared as a second word: a word that never appears after anything has continuation probability 0, so no history can ever predict it. The recursion has to end somewhere, and Kneser-Ney ends it in a way that removes this last zero. The Unigram level is itself discounted and interpolated, with the uniform distribution over the vocabulary:

Every word, seen or not, now receives at least λ(ε)/V at the unigram level, which ends the Zero-probability problem for good. That includes the unknown word: <UNK> token is treated as an ordinary vocabulary entry whose count is 0, so the first term vanishes and its probability is exactly λ(ε)/V. Heafield and colleagues describe the same design in KenLM: recursion terminates when unigrams are interpolated with the uniform distribution, and the unknown word has count zero, so its probability is b(ε)/|vocabulary|.

Try history "wore her" with target "she" in the simulator. No level has ever seen "she" after anything, yet the probability is about 0.016, all of it trickling down from the uniform floor through three λ weights. Then push d up: every λ grows, the top level trusts its own counts less, and the floor rises.

Look again at the held-out experiment behind d = 0.75. Church and Gale counted bigrams in 22 million words of AP newswire and checked how often each appeared in another 22 million. Bigrams seen twice appeared on average 1.25 times (they shrink by 0.75), those seen three times 2.24 times (by 0.76), and those seen four times 3.23 times (by 0.77). But bigrams seen once appeared only 0.448 times, a shrink of 0.55. One discount cannot fit both.

The Church and Gale numbers show that a single d is a compromise: it over-discounts singletons and slightly under-discounts the rest. Jurafsky and Martin already hint at the fix, suggesting perhaps keeping a separate second discount value of 0.5 for the bigrams with counts of 1. Chen and Goodman made it systematic. Modified Kneser-Ney uses D1 for n-grams seen once, D2 for those seen twice and D3+ for three or more (the slide writes d1, d2, d3+), and Jurafsky and Martin call it the best-performing version of Kneser-Ney smoothing.

Estimating the three discounts

The discounts are not guessed. They come in closed form from the counts of counts of each order: n_k is the number of distinct n-grams of that order seen exactly k times. The original single-discount Kneser-Ney already used this idea, with d = n1 / (n1 + 2 n2) from Ney et al. (JM Eq. C.2, SRILM -ukndiscount). Modified Kneser-Ney keeps that quantity as Y and derives three discounts from it:

The reserved mass changes with it

The structure stays the same: discount, then interpolate. What changes is the mass a history reserves for the lower order. Instead of d times the number of continuation types, each type contributes the discount of its own bucket, where N_k(h•) is the number of words seen exactly k times after h:

Suppose you need a 5-gram language model for a translation or speech system. You do not implement the recursion yourself. You run one of two toolkits, and both build interpolated modified Kneser-Ney:

lmplz -o 5 <corpus.txt >model.arpa
ngram-count -order 5 -text corpus.txt -kndiscount -interpolate -lm model.arpa

The discounts are hyperparameters, but rarely hand-tuned ones. Both toolkits estimate them in closed form from the counts of counts of the training data, a separate set per order. They can also be tuned on a development set by minimizing perplexity, which is what the slide means by smoothing parameters tuned on held-out data. KenLM's documentation states that it estimates unpruned language models with modified Kneser-Ney smoothing, and its --discount_fallback option supplies 0.5, 1.0 and 1.5 for singletons, doubletons and higher counts when the counts of counts are unusable, for instance on tiny or deduplicated data.

Kneser-Ney shines at high orders. In a 5-gram model most 5-word contexts are seen once or never, so most predictions lean on the lower levels, and that is where continuation counts make the difference. This is the sparsity problem in its sharpest form. Chen and Goodman's study showed the advantages of modified interpolated Kneser-Ney, which became the standard n-gram baseline around the turn of the century. Goodman later reported that a combination of techniques including interpolated Kneser-Ney gave a 38% to 50% perplexity reduction against a Katz trigram, and an 8.9% word error rate reduction. At scale, Heafield and colleagues estimated an unpruned model on 126 billion tokens in 2.8 days on one machine with 140 GB of RAM, gaining 0.8 BLEU, and on 302 million tokens KenLM used 7.7% of SRILM's RAM and 14.0% of its wall time.

With a vocabulary of V = 50,000, a trigram model has V³ = 1.25 × 10^14 possible trigrams. Bengio and colleagues put it more starkly: modelling 10 consecutive words with V = 100,000 means 10^50 − 1 free parameters. And even a perfectly smoothed N-gram model that has read "the cat is walking in the bedroom" learns nothing about "a dog was running in a room", because none of its n-grams match.

These are the two walls. First, n-gram parameters grow exponentially in n, so longer contexts are almost never observed and smoothing has to do more and more of the work. Second, n-grams generalize only through exact matches: cat and dog are just different strings, so evidence about one never transfers to the other. Kneser-Ney makes the best of counts, but it cannot fix either problem, because both come from treating words as atomic symbols.

A Neural language model maps each word into a continuous vector space where similar words, and similar contexts, get similar vectors. A sentence about a cat then raises the probability of the same sentence about a dog, and the number of parameters grows only linearly with V and n. Bengio et al. reported test perplexity about 24% lower on Brown and about 8% lower on AP News than the best n-gram model on each corpus: a class-based model on Brown and modified Kneser-Ney backoff on AP News. Mixing the neural model with a trigram always helped further. Lecture 04 develops this idea of words as vectors: word embeddings. Transformer language models, later in the course, are the descendants of this idea.