Interpolation, backoff and absolute discounting

Suppose you need the probability of food after want chinese. The Unigram estimate is P(food) = 0.01, the Bigram estimate is P(food | chinese) = 0.52, and the Trigram want chinese food never occurred in training, so its maximum likelihood estimate is 0. A pure trigram model would declare the sentence impossible. Instead, take a weighted average of the three with weights λ = (0.1, 0.3, 0.6): 0.1 × 0.01 + 0.3 × 0.52 + 0.6 × 0 = 0.001 + 0.156 + 0 = 0.157. The zero is gone, and the estimate is driven by the evidence that does exist.

That is linear interpolation. The trigram is the sharpest predictor when it has data, but Sparsity means it very often has none, which is exactly the Zero-probability problem of part 06. Lower orders are blunter but almost always have counts. Mixing them lets each order contribute what it is good at. SLP3 writes the trigram version as follows.

The constraint that the λs sum to 1 is not decoration. Each component is itself a probability distribution over the vocabulary, so summing the mixture over every possible next word gives λ1 · 1 + λ2 · 1 + λ3 · 1 = Σλ = 1. With weights summing to more than 1 the model would invent probability mass, and with less it would leak some. A weighted average of distributions is a distribution, and that is all the constraint guarantees.

Weights that depend on the context

A single fixed λ vector treats every context alike, which wastes information. If the bigram want chinese has been seen thousands of times, the trigrams built on it are well estimated and deserve more weight; if it has been seen twice, they do not. SLP3 therefore lets each λ be a function of the two preceding words, which is context-dependent interpolation. In its words, if we have particularly accurate counts for a particular bigram, we assume that the counts of the trigrams based on this bigram will be more trustworthy.

The idea is old. Jelinek and Mercer introduced interpolated estimation in 1980, which is why it is also called Jelinek-Mercer smoothing or deleted interpolation. Chen and Goodman's large empirical study found that interpolated models, which always combine the higher and lower orders, typically work better than backoff models, because low counts of 1 or 2 are poorly estimated and benefit from being blended even when they are not zero (Goodman 2001). Jurafsky's own slide states the verdict in three words: interpolation works better.

Where do the numbers 0.1, 0.3, 0.6 come from? Try them out. Take three tokens from a development set and write down, for each, the unigram, bigram and trigram estimates that the training counts give.

Now score the same three tokens under three candidate weight vectors. For each, mix the components, multiply the token probabilities, take the base-2 log, and turn that into Perplexity with PP = 2^(−log2 L / 3).

The first vector gives a held-out perplexity of 3.92, the second 8.22, and the third, which is the pure maximum likelihood trigram, gives probability 0 to the first token and therefore infinite perplexity. You pick the first. That is the whole procedure, done properly: the λs are hyperparameters, values that are not counts and are not learned from the counts. SLP3 says so in a footnote, contrasting them with regular counts that are learned from the training data. The recipe has two stages. First fit every n-gram probability on the training set and freeze it. Then search over λ to maximize the likelihood of a separate held-out corpus, which is the same as minimizing its perplexity. The same holds for k in add-k and for the discount d later in this part.

Why not tune on the training data itself? Because on training data the maximum likelihood trigram already fits best: every training trigram has a nonzero count, so the likelihood keeps rising as λ3 grows and peaks at λ3 = 1. That is exactly the third row of the table, which collapses on any new text. Held-out data contains the unseen n-grams that the lower orders exist to cover, so only it can reward them. And the Test set is off limits, because once you tune on it the reported perplexity is no longer an honest estimate of performance on unseen text.

Score floor after quietly on the, in a corpus of N = 10,000 tokens. The four-gram quietly on the floor has count 0, so drop the oldest context word. The trigram on the floor also has count 0, even though on the itself was seen 20 times, so drop another word. The bigram the floor has count 3 and the has count 60, so its Relative frequency is 3 / 60 = 0.05. Each step down cost a factor of 0.4, so the score is S = 0.4 × 0.4 × 0.05 = 0.008.

This is Backoff: use the highest order whose full n-gram count is above 0, and otherwise drop one context word and try again. Unlike interpolation it uses exactly one order per word. Notice what triggered each step. The context on the was perfectly familiar; it was the n-gram on the floor that was missing. Backoff fires on a zero n-gram count, not on an unseen context.

The specific recipe: stupid backoff

The factor 0.4 is the signature of Stupid backoff, introduced by Brants, Popat, Xu, Och and Dean at EMNLP-CoNLL 2007 for Google's translation system. Their equation 5 defines a score, and their equation 6 ends the recursion at the unigram level.

If the bigram the floor had also been unseen and floor occurred 5 times, the recursion would reach the base case: S = 0.4³ × 5 / 10,000 = 0.064 × 0.0005 = 0.000032. The authors write S instead of P to emphasize that these are not probabilities but scores, and the reason is easy to see. In the context on the, the relative frequencies of the continuations that were seen already sum to 1. Every unseen continuation then adds 0.4 × S(w | the) on top. For floor alone that is 0.4 × 0.05 = 0.02, so the total over the vocabulary is at least 1.02, and every other unseen word pushes it higher.

A proper backoff model fixes this in two ways at once. Katz backoff (Katz 1987) first discounts the seen n-grams, replacing the relative frequency with a smaller P*, which frees some probability mass in each context. Then it gives the lower order a context-dependent normalizing weight α(context) chosen so that the freed mass is spread over exactly the unseen words. SLP3 (Jan 2023 edition, section 3.5) is explicit that without discounting the total probability would be greater than 1; the current draft adds that stupid backoff gives up the idea of trying to make the language model a true probability distribution. Discounting is therefore not optional for backoff, and it is the subject of the rest of this part.

Why did Google accept a model that is not a distribution? A translation decoder only compares candidate outputs, so it needs relative scores, not normalized probabilities. Stupid backoff needs no discount estimation and no α per context, so it is cheap to compute with MapReduce over training data that reached 2 trillion tokens and a model of about 300 billion n-grams. At small data sizes it was about 1 BLEU point behind Kneser-Ney, and the gap narrowed as data grew until the two were close. The authors' footnote explains the name: it originated at a time when they thought such a simple scheme could not possibly be good; their view changed, but the name stuck.

Look at what add-one smoothing did to the Berkeley Restaurant Project corpus. The bigram want to occurred 608 times. After adding one to every cell and renormalizing, its reconstituted count is 238, and P(to | want) falls from 0.66 to 0.26.

One of the most frequent, most reliable bigrams in the table lost more than half its probability. The discount ratio d_c, reconstituted count over original count, is 0.39 for want to and 0.10 for chinese food. The mass went to the roughly 1446² possible bigram cells, most of which are zeros. SLP3 sums it up: too much probability mass is moved to all the zeros. Making the added amount smaller does not cure it. Add-k with k = 0.05 moves less mass, but SLP3 reports that it still does not work well for language modeling, generating counts with poor variances and often inappropriate discounts (Gale and Church 1994).

Read the problem the other way round. Any Smoothing method that gives mass to unseen events must take it from seen events, which is why SLP3 says these methods are called smoothing or Discounting. The question is not whether to discount but how much, and from which counts. A good discount barely touches large counts, whose estimates are already reliable, and mostly adjusts small counts, where most of the uncertainty lives. And the amount should be measured, on data the model did not train on, not guessed. The next concept does exactly that measurement.

Slide 75's last point, smoothing that respects how language uses context, is a preview: the discount here fixes how much mass moves, and Kneser-Ney smoothing in the next part fixes where it goes.

Take every bigram that appeared exactly 4 times in the first 22 million words of AP newswire, and count how often each appears in the next 22 million words. The average is 3.23, not 4. The bigrams did not change; the first count was partly luck.

This is the experiment of Church and Gale (1991), reported in SLP3 (Jan 2023 edition, section 3.7.1, Fig. 3.9). Repeat it for every training count from 0 to 9 and subtract the held-out average from the training count.

For every count from 2 to 9 the gap is nearly constant, between 0.74 and 0.79. Training counts systematically overestimate future counts, and by a fixed amount rather than by a fixed percentage. SLP3 concludes that, except for the held-out counts for 0 and 1, all the other bigram counts could be estimated pretty well by just subtracting 0.75. This held-out data plays exactly the role of the Development set in the second concept: it measures a quantity the training counts cannot reveal about themselves.

The two exceptions are informative. The count-0 row, 0.0000270, is the mass that maximum likelihood wrongly sets to zero. It is a tiny average, but it is averaged over an enormous number of unseen pairs, so in total it adds up to real probability that a discount must supply. The count-1 row is the outlier: singletons reappear 0.448 times, a gap of about 0.55, so a single discount of 0.75 would overcharge them. That is why SLP3 suggests a separate discount of 0.5 for count 1, and why Modified Kneser-Ney uses separate discounts for counts 1, 2 and 3+.

The context chinese was seen 10 times, followed by food 6 times, restaurant 3 times and cuisine once. Subtract d = 0.75 from each count: food keeps 5.25 / 10 = 0.525, restaurant keeps 2.25 / 10 = 0.225, cuisine keeps 0.25 / 10 = 0.025. Together they keep 0.775. The missing 3 × 0.75 / 10 = 0.225 is a pot of freed probability, and it is handed out to every word in proportion to its unigram probability.

That is interpolated absolute discounting, the direct use of the Church and Gale finding. Its bigram form subtracts a fixed d from every nonzero count and interpolates with the unigram distribution.

Each part of the formula has a job. The first term is the discounted relative frequency: big counts barely move, small counts move a lot, as the previous concept demanded. The max(·, 0) keeps unseen bigrams at zero in this term instead of letting them go negative. The weight λ(w_{i-1}) is the Backoff weight (lambda), and it is not a free parameter: it is exactly the mass the first term removed, so the two terms together sum to 1.

Choosing d

The discount d is the one Hyperparameter left, and there are two standard ways to set it. The first is to read it off the table: SLP3 says setting all the d values to 0.75 would work very well, or perhaps keeping a separate second discount of 0.5 for the bigrams with counts of 1. Jurafsky's slide puts it as save ourselves some time and just subtract 0.75. The second is a closed-form estimate from Ney, Essen and Kneser (1994), which uses only the count of counts of the training data.

For example, with n1 = 6000 bigram types seen once and n2 = 1500 seen twice, d = 6000 / (6000 + 3000) = 6000 / 9000 ≈ 0.667. The estimate needs no held-out data, and its value lands close to the 0.75 that Church and Gale measured directly. In practice, KenLM estimates modified Kneser-Ney with separate discounts for counts 1, 2 and 3+, while BerkeleyLM ships plain absolute discounting in which every discount is 0.75.

The next part keeps this exact structure, a discounted higher-order term plus a λ times a lower-order distribution, and changes only the lower-order distribution. Kneser-Ney smoothing replaces the unigram P(w_i) with a continuation probability, which asks how many different contexts a word appears in rather than how often it appears.