Smoothing and Backoff

This builds on N-Gram Language Models, which set up the model — factor a sequence by the chain rule, truncate the history with the Markov assumption, estimate each conditional by counting, and score with perplexity. That model works until the test set contains a word sequence the training corpus never included; then the count is zero, the probability is zero, and perplexity is undefined. This lesson is about that failure and its repair.

Generalization and the zero problem

An n-gram model is a mirror of its training corpus. That has two consequences. Higher $n$ models the training text more and more faithfully — sample from a $4$-gram trained on Shakespeare and you get fragments that are nearly verbatim Shakespeare, because with $V=29,066$ word types there are $V^2\approx 8.4\times 10^8$ possible bigrams and his entire corpus is only $N=884,647$ words, so most n-grams that do occur occur exactly once and have only one continuation. The model has memorized rather than generalized.

The flip side is fragility across genres. An n-gram grammar trained on Shakespeare generates nothing resembling the Wall Street Journal, and vice versa. A model only works on text like its training data, which is why matching the genre and dialect of the training corpus to the intended task matters.

But the deeper problem is sparsity: any finite corpus is missing perfectly good word sequences that simply never appeared. Consider the bigram denied the in a news corpus, with the continuations actually seen:

denied the allegations   5denied the speculation    2denied the rumors         1denied the report         1

If the test set contains denied the offer or denied the loan, the model estimates $P(\text{offer}\mid \text{denied the})=0$ — a zero. These zeros are harmful for two reasons. They understate the probability of everything that could legitimately occur, hurting any downstream task. And worse, a single zero anywhere in the test set makes the whole test-set probability zero, so perplexity is undefined — you cannot divide by zero. A usable model cannot assign zero probability to unseen but possible events.

Unknown words

A related gap is words never seen at all — out-of-vocabulary (OOV) words. In a closed vocabulary task (say, a speech recognizer with a fixed pronunciation dictionary) this cannot arise. Otherwise we build an open vocabulary by adding a pseudo-word <UNK>: fix a vocabulary in advance (or keep only words above a frequency threshold), replace every other word in the training data with <UNK>, and then estimate <UNK>'s probability from its counts like any ordinary word. Because a model can lower its perplexity by shrinking the vocabulary and loading probability onto <UNK>, perplexities are only comparable across models with identical vocabularies.

Smoothing

Smoothing (or discounting) is the family of fixes for the zero problem: shave a little probability mass off the events the model has seen and redistribute it to the events it has not, so nothing gets exactly zero.¹ The name comes from the picture — flattening a spiky count distribution so the sharp zeros fill in.

Laplace (add-one) smoothing

The simplest scheme adds one to every count before normalizing. For unigrams, the MLE $P(w_i)=c_i/N$ becomes, after adding $1$ to each of the $|V|$ word counts and adjusting the denominator by $|V|$ so the probabilities still sum to one,

For bigrams, the prefix count $C(w_{i-1})$ in the denominator must likewise be augmented by $|V|$, because every one of the $|V|$ possible following words has gained a phantom count:

It helps to see the effect through the adjusted count $c^{\ast }$ — the smoothed count that, divided by the original denominator, reproduces the smoothed probability. For add-one bigrams,

On the Berkeley corpus this adjustment is drastic. The count $C(\text{want to})$ falls from $608$ to an adjusted $238$, and $P(\text{to}\mid \text{want})$ drops from $0.66$ to $0.26$ — a discount of $d_c=c^{\ast }/c\approx 0.39$. Because $|V|=1446$ zero cells each gain a phantom count, add-one moves far too much mass onto the zeros. It is a useful baseline and a real method for text classification, but too blunt for serious language modeling.

Add-k smoothing

A gentler variant adds a fraction $k$ (say $0.5$, $0.05$, $0.01$) instead of a full $1$:

Choosing $k$ is itself a tuning problem, done on the development set. Add-k is better than add-one for some tasks, but still generates poorly-shaped counts and awkward discounts for language modeling. Better methods use a different idea.

Backoff and interpolation

The idea behind the better methods: when a high-order n-gram has no evidence, fall back on a lower-order one that does. If a trigram $w_{i-2}{w}_{i-1}{w}_i$ was never seen, its bigram $w_{i-1}{w}_i$ or even its unigram $w_i$ probably was. Two ways to use this hierarchy:²

• Backoff. Use the trigram if its count is nonzero; otherwise back off to the bigram; otherwise to the unigram. Only the highest order with evidence is consulted.
• Interpolation. Always mix all orders, weighting each by a $\lambda$. For the trigram case,

The $\lambda$s sum to one so the result is a proper distribution; they are set to maximize the likelihood of a held-out corpus. In the more refined version each $\lambda$ is itself conditioned on the context, so a context with plenty of trigram evidence leans harder on the trigram term. For backoff to stay a valid distribution, the higher orders must be discounted to free up mass for the lower orders — otherwise the borrowed probability pushes the total above one. Backoff with discounting is Katz backoff.

Kneser-Ney, in one idea

The best-performing classical smoother is interpolated Kneser-Ney.³ It starts from absolute discounting: subtract a fixed constant $d$ (empirically near $0.75$) from every nonzero count, which — as Church and Gale found by comparing a corpus to a held-out copy — closely matches how counts actually shrink from one sample to the next, then interpolate with a lower-order term.

Kneser-Ney's own contribution is the lower-order term. A standard unigram estimates how frequent $w$ is, but frequency is the wrong quantity for a fallback. The word Kong is frequent, yet only ever appears after Hong; glasses is less frequent but appears in many contexts. As a novel continuation for an unseen bigram, glasses is the better bet. So Kneser-Ney replaces raw frequency with a continuation probability: how many distinct contexts a word completes.

The numerator counts the distinct words $v$ that precede $w$; the denominator counts all distinct bigram types. Kong, seen in only one context, gets a low continuation probability despite its high raw frequency. Combining absolute discounting on the higher order with continuation probability on the lower gives the interpolated Kneser-Ney bigram estimate:

with $\lambda (w_{i-1})$ a normalizing weight that redistributes exactly the mass the discount $d$ removed. The recursion bottoms out at the unigram, interpolated with the uniform distribution $1/|V|$. The production variant, modified Kneser-Ney, uses three separate discounts for counts of one, two, and three-or-more.

Why $d\approx 0.75$: the Church-Gale held-out experiment

The absolute discount is measured, not tuned. Church and Gale built a bigram model from $22$ million words of AP newswire and then looked up, for every bigram that occurred $c$ times in that corpus, how often the same bigram occurred in a second, independent $22$-million-word sample.³ The held-out count is what the training count should have been if the corpus were unbiased, and it is almost exactly the training count minus a constant near $0.75$.

Read across from $c=2$ onward: the held-out average sits about $0.75$ below the training count in every column ($2-1.25=0.75$, $3-2.24=0.76$, $4-3.23=0.77$, $\dots$). The high counts are barely touched — subtracting $0.75$ from a count of $9$ changes little — while the small counts, the ones we trust least, are pulled down hardest in relative terms. That single measured constant is the discount $d$ absolute discounting subtracts.

The normalizing weight $\lambda (w_{i-1})$ is not arbitrary either. It must give the lower-order term exactly the mass the discount removed from the higher order. Each of the distinct words that can follow $w_{i-1}$ contributed one discount of $d$, so the total mass freed is $d$ times the number of such continuation types, all divided by the prefix count $C(w_{i-1})$:

The first factor is the normalized discount; the second counts how many times the discount was applied — the number of word types seen after $w_{i-1}$. Multiply them and $\lambda (w_{i-1})$ is precisely the probability mass to redistribute, so $P_{\text{KN}}$ still sums to one over the vocabulary.

A full Kneser-Ney computation

For a worked example, take the same three-sentence corpus from the bigram example, without the sentence markers for brevity:

I am SamSam I amI do not like green eggs and ham

Set the discount to $d=0.75$ and estimate $P_{\text{KN}}(\text{am}\mid \text{I})$. Two ingredients are needed: the discounted higher-order term, and the continuation-probability lower-order term.

Higher-order term. The word I occurs three times ($C(\text{I})=3$), and the bigram I am occurs twice ($C(\text{I am})=2$). Absolute discounting shaves $0.75$ off that count:

Continuation probability of am. Ask in how many distinct contexts am appears as the second word of a bigram. Scanning the corpus, am is preceded only by I — twice, once in each of the first two sentences — and by no other word, so it completes exactly one distinct bigram type: $\{v:C(v\text{am})>0\}=\{\text{I}\}$, size $1$. The denominator is the number of distinct bigram types in the corpus. Listing them — I am, am Sam, Sam I, I do, do not, not like, like green, green eggs, eggs and, and ham — gives $10$ distinct types (note I am appears twice but counts once as a type):

The weight. After I we see two distinct word types (am and do), so the discount was applied twice:

Combine. The Kneser-Ney estimate mixes the two:

Compare the plain MLE, $P(\text{am}\mid \text{I})=2/3=0.667$. Kneser-Ney has pulled the estimate down from $0.667$ to $0.467$, moving the freed $0.2$ of mass onto all the words that could plausibly follow I — weighted by how broadly each word appears as a continuation, not by raw frequency. The figure traces the two streams into the final estimate.

Stupid backoff and web-scale n-grams

Kneser-Ney is the best classical smoother, but the counts it smooths can come from very large corpora. Google's Web 1 Trillion 5-gram release holds n-grams up to length five drawn from over $10^{12}$ words of English web text; its Google Books n-grams add hundreds of billions more tokens across many languages.⁴ At that scale two things change: the model is too big to hold naively, and the normalization Kneser-Ney requires stops being worth its cost.

Storing a huge model

A trillion-word model cannot keep its n-grams as plain strings and its probabilities as $8$-byte floats — the table would not fit in memory. Production toolkits make three compromises.⁴

• Hashing. Each word is stored not as a string but as a $64$-bit hash number, with the string forms kept on disk. The n-grams themselves live in reverse tries, a prefix tree read from the last word back, which shares structure across n-grams with common suffixes.
• Quantization. A probability is stored in only $4$ to $8$ bits rather than a full float. The precision lost is negligible against the size saved.
• Pruning. Drop the n-grams that carry little information — for instance, keep only those with a count above a threshold (Google's release used a count of $40$), or prune by an entropy criterion that discards the n-grams whose removal least perturbs the model. Approximate structures like Bloom filters shrink the model further at the cost of occasional false positives.

Toolkits like KenLM combine a backoff weight and a probability into a single stored value and build the tables with a few merge-sort passes over the corpus, so that even web-scale Kneser-Ney models are buildable. But at that size a much cruder scheme often suffices.

The stupid-backoff rule

Stupid backoff gives up on being a true probability distribution altogether.⁵ It does no discounting: if the full-order n-gram has a nonzero count, use its relative frequency directly; otherwise fall back to the next-lower order, multiplied by a fixed, context-independent weight $\lambda$. Because the result is not normalized, it is written $S$ rather than $P$:

The recursion bottoms out at the unigram, scored by its own relative frequency $S(w)=C(w)/N$. Brants et al. found $\lambda =0.4$ works well. Contrast this with Katz backoff earlier in this lesson: Katz discounts the higher orders to free up exactly the right mass for the lower ones, keeping the total a valid distribution. Stupid backoff skips all of that — it just scales the lower order by a constant and never renormalizes.

Dropping normalization is what saves the cost. Renormalizing a backoff model means, for every context, summing over the vocabulary to redistribute the discounted mass — prohibitive when the model has billions of contexts. Stupid backoff skips that sum entirely. The scores $S$ no longer sum to one, so they cannot be compared as probabilities across contexts, but for ranking candidate continuations — which is what a downstream system such as machine translation actually needs — a monotonic score is enough. With a large enough corpus the volume of evidence outweighs the crudeness of the estimate, and stupid backoff comes within reach of full Kneser-Ney at a fraction of the engineering.

Beyond n-grams: neural and self-attention language models

Every smoothing scheme in this lesson responds to sparsity the same way: back off to a shorter context. That is a workaround, not a solution. The n-gram treats cat and dog as unrelated atoms, so a bigram model that has seen the cat sat learns nothing about the dog sat. The models that displaced the n-gram all address this one weakness, and all originate in named, public work that postdates the counting-and-smoothing view above.

Distributed representations (Bengio et al., 2003)

The neural probabilistic language model of Bengio, Ducharme, Vincent, and Jauvin (JMLR, 2003) keeps the n-gram's prediction task verbatim — estimate $P(w_t\mid w_{t-n+1:t-1})$ from a fixed window — but changes how the context is represented. Each word is mapped to a learned dense vector, its embedding, and the network predicts the next word from the concatenated embeddings of the context rather than from the raw word identities. Words that behave alike are pushed to nearby vectors during training, so evidence shares across them. Having seen the cat gets fed, the model raises its estimate of fed after the dog gets as well, because cat and dog sit close in embedding space. Bengio et al. framed this as breaking the curse of dimensionality: an n-gram must store a separate parameter for each of the exponentially many word combinations, while the neural model shares a small set of embedding dimensions across all of them.⁶ Smoothing stitches together backoff levels after the fact; the neural model never manufactures the zeros in the first place, because similarity, not exact match, drives its estimate.

Recurrent and self-attention models (Mikolov 2010; Vaswani et al., 2017)

Bengio's model still truncates history to a fixed window, inheriting the n-gram's Markov assumption. Two later architectures removed even that limit. The recurrent neural network language model (Mikolov et al., Interspeech 2010) carries a hidden state forward token by token, in principle conditioning each prediction on the entire preceding sentence rather than a window of $n-1$ words. The transformer (Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser, and Polosukhin, NeurIPS 2017) replaced recurrence with self-attention: at each position the model computes a weighted sum over the representations of all earlier positions, the weights learned per pair of positions, so any prior word can directly influence the current prediction regardless of distance. Self-attention parallelizes across positions in a way recurrence cannot, which is what made training on billions of tokens practical and put the transformer under every large language model that followed.

The n-gram vocabulary is fully preserved in these models. They still assign a probability to the next word, still factor a sequence by the chain rule, still report perplexity, and still contend with rare and unseen words — the very problems set up in this lesson. What changed is only the estimator: from counting and backing off to a learned function that shares statistical strength across similar contexts. On the Penn Treebank and larger benchmarks, neural models cut perplexity far below the best Kneser-Ney n-gram, at the cost of far heavier training. For a small task on a small corpus, a smoothed n-gram is still the right tool and often the faster one; the tradeoff is accuracy against complexity, not one paradigm rendering the other wrong.

Where n-grams lead

The n-gram's prediction task — assign a probability to the next word given a context — is verbatim the task a neural language model solves; the difference is only in how the conditional is estimated. The n-gram counts and smooths; the neural model learns a distributed representation of the context and computes the conditional with a network, which sidesteps sparsity by sharing statistical strength across similar contexts instead of stitching together backoff levels. The vocabulary set up here — sequence probability, the Markov approximation, maximum likelihood, perplexity, the zero problem — is the vocabulary those models inherit. We pick the thread up with vector semantics, which learns to represent a word's meaning as a vector, and then with neural language models, which use those vectors to predict the next word.