N-gram Models & Smoothing
Counting, perplexity and the zero-probability problem.
Train a trigram model on a billion words, and a sizable share of the trigrams in tomorrow's text will still be ones it has never seen. How much probability should a model reserve for events it has never observed? I. J. Good, building on wartime work with Alan Turing, answered in 1953 with an estimate that needs only the number of things seen exactly once. Kneser and Ney turned the same insight into the best count-based language models ever built. This lesson proves why both work.
What you’ll learn
- Quantify sparsity with Zipf's and Heaps' laws, and compute how much of a text the most frequent types cover.
- Derive the Good–Turing estimates and prove that the missing-mass estimate has bias at most .
- Derive interpolated Kneser–Ney, prove that it normalizes and that its continuation counts preserve unigram marginals, and state its Pitman–Yor interpretation.
- Relate perplexity to the entropy rate through the Shannon–McMillan–Breiman theorem.
Sparsity, quantified
Take a sample of tokens. Write for the number of types seen exactly times, so that . Two empirical laws govern these counts in natural language:
- Zipf's law: the -th most frequent type has relative frequency , with close to for words in many languages.
- Heaps' law: the number of distinct types grows as with , typically – for words. New types never stop arriving.
Under exact Zipf with and types, , where is the harmonic number. The top types therefore cover a fraction of all tokens: a logarithmic, painfully slow climb.
Under exact Zipf () with word types, what percentage of all tokens do the 100 most frequent types cover?
Show the answer
43 %
. The top types cover only , so the remaining types share 19% of the tokens, each with probability below . For word pairs and triples the tail is far heavier.
Maximum likelihood gives every unseen event probability zero, and by these laws unseen events are a large part of any new text. The question is no longer whether to reserve mass for them but how much, and the counts of rare events turn out to answer it.
Good–Turing: estimating the unseen
Let tokens be drawn i.i.d. from an unknown distribution over a countable alphabet, and let the missing mass be the total probability of the types that did not occur. It is a random variable, and it cannot be computed from the sample, since the unseen types are unknown. Good (1953), crediting Turing, proposed the estimate : the fraction of the sample made of types seen exactly once. More generally, types seen times get the adjusted count .
Type is unseen with probability and seen exactly once with probability . By linearity of expectation:
Subtract term by term:
On the function peaks at , where it equals . So each term is at most , and the probabilities sum to one:
The same computation for types seen times links their total mass to , which is where the adjusted count comes from:
The bias bound holds for every distribution, however many types it has. Concentration holds too: McAllester and Schapire (2000) showed that with probability at least . In practice is noisy and often zero for large , so Simple Good–Turing (Gale & Sampson, 1995) fits a line to against before computing , and Katz backoff uses Good–Turing discounts for small counts only.
Kneser–Ney, derived
Church and Gale (1991) split a large corpus in half and found that bigrams seen times in the first half occur on average about times in the second: counts shrink by a roughly constant amount. Absolute discounting subtracts a fixed from every nonzero count and hands the freed mass to a lower-order distribution. Kneser and Ney (1995) also changed which lower-order distribution. For bigrams, with the number of distinct words seen after and the number of distinct words seen before :
Every observed count is at least , so discounting removes exactly from each of the observed successors of , and is precisely that removed mass:
Why continuation counts? Require the smoothed bigram model, averaged over histories with their empirical frequencies , to reproduce the empirical unigram frequency of every word, and solve for the unknown lower-order distribution :
Since , the number of distinct bigram types, the solution is unique and is exactly the continuation probability:
A history occurred times, followed by three distinct words with counts , and . With discount , what fraction of 's probability mass does interpolated Kneser–Ney give to the continuation distribution?
Show the answer
B.
. The three observed successors keep , and the rest is spread over all words in proportion to their continuation counts, including some mass back on the three observed ones.
Higher orders recurse: the top order uses discounted counts, and each lower order uses discounted continuation counts of the shortened context. Chen and Goodman's modified Kneser–Ney uses three discounts for counts , and , estimated from the count-of-counts : with , . In their extensive comparison across corpora and sizes, interpolated modified Kneser–Ney beat every other count-based method.
Perplexity, entropy rate and the limits of counting
Shannon (1951) had people guess text letter by letter and estimated the entropy of English at roughly – bits per character. Brown et al. (1992) derived an upper bound of bits per character from a word-trigram model trained on hundreds of millions of words. Because the bound is per symbol, comparisons across tokenizations go through a common unit: a model with per-token log-loss bits on text averaging characters per token achieves bits per character.
Counting kept scaling. Brants et al. (2007) trained 5-gram models on up to two trillion tokens with "stupid backoff", an unnormalized score that backs off with a fixed factor of ; with enough data it approached Kneser–Ney's quality. Infini-gram (Liu et al., 2024) indexes trillions of tokens with suffix arrays, so counts of arbitrarily long contexts can be looked up and the model backs off to the longest context ever seen. Such count indexes now serve to study language models' training data, for memorization and benchmark contamination.
Key takeaways
- Zipf's law makes coverage grow only logarithmically with the number of types, and Heaps' law keeps new types arriving: unseen events are a large share of any new text.
- Good–Turing estimates the missing mass by , with bias in for every distribution, and adjusts counts to .
- Interpolated Kneser–Ney subtracts a fixed discount and redistributes exactly the removed mass; its continuation probability is the unique lower-order model that preserves unigram marginals, and it approximates a hierarchical Pitman–Yor model.
- By Shannon–McMillan–Breiman and Gibbs' inequality, any model's log-perplexity per symbol upper-bounds the entropy rate; compare models across tokenizations in bits per character.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In a sample of word tokens, types occur exactly once. What is the Good–Turing estimate of the probability that the next token is a type never seen before?
- It cannot be estimated without knowing the vocabulary size
Show the answer
A.
. The estimate needs no vocabulary size, and its bias is at most for any distribution.
Why does interpolated Kneser–Ney set ?
- It is tuned on held-out data
- It equals the probability that is followed by an unseen word under maximum likelihood
- It is exactly the mass removed by discounting each of 's observed successors, so the distribution sums to one
- It makes equal to the continuation probability
Show the answer
C. It is exactly the mass removed by discounting each of 's observed successors, so the distribution sums to one
Discounting removes from each of the observed successors, a total of in probability, and redistributes exactly that amount.
Which requirement singles out Kneser–Ney's continuation probability as the lower-order distribution?
- It maximizes the likelihood of the training bigrams
- It is the uniform distribution over the vocabulary
- It minimizes the number of parameters
- The smoothed bigram model, averaged over histories, must reproduce the empirical unigram frequencies
Show the answer
D. The smoothed bigram model, averaged over histories, must reproduce the empirical unigram frequencies
Imposing and solving gives uniquely: a word's lower-order probability is proportional to the number of distinct words it follows.
A language model reaches bits per character on a large sample of English text. What does this establish about the entropy rate of that text?
- The entropy rate is at most about bits per character, since every model's expected log-loss upper-bounds it
- The entropy rate is exactly bits per character
- The entropy rate is at least bits per character
- Nothing, because entropy rates are defined only for character-level models
Show the answer
A. The entropy rate is at most about bits per character, since every model's expected log-loss upper-bounds it
Cross-entropy equals entropy plus a non-negative KL term, so any model's (expected, large-sample) log-loss bounds the entropy rate from above. Equality would require the model to match the source exactly.
Further reading
- I. J. Good, "The population frequencies of species and the estimation of population parameters," Biometrika 40, 237–264 (1953).
- R. Kneser & H. Ney, "Improved backing-off for M-gram language modeling," ICASSP (1995).
- S. F. Chen & J. Goodman, "An empirical study of smoothing techniques for language modeling," Computer Speech & Language 13, 359–394 (1999).
- Y. W. Teh, "A hierarchical Bayesian language model based on Pitman–Yor processes," COLING/ACL (2006).
- D. Jurafsky & J. H. Martin, Speech and Language Processing (3rd ed. draft), chapter on n-gram language models.