Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 N1/nN_1/n has bias at most 1/n1/n.
  • 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 nn tokens. Write NrN_r for the number of types seen exactly rr times, so that ∑rrNr=n\sum_rrN_r=n. Two empirical laws govern these counts in natural language:

  • Zipf's law: the rr-th most frequent type has relative frequency f(r)≈C/rαf(r)\approx C/r^{\alpha}, with α\alpha close to 11 for words in many languages.
  • Heaps' law: the number of distinct types grows as V(n)≈KnβV(n)\approx Kn^{\beta} with 0<β<10<\beta<1, typically 0.40.4–0.60.6 for words. New types never stop arriving.

Under exact Zipf with α=1\alpha=1 and VV types, f(r)=1/(rHV)f(r)=1/(rH_V), where Hr=∑i≤r1/i≈ln⁡r+0.577H_r=\sum_{i\le r}1/i\approx\ln r+0.577 is the harmonic number. The top rr types therefore cover a fraction Hr/HVH_r/H_V of all tokens: a logarithmic, painfully slow climb.

Predict before you look

Under exact Zipf (α=1\alpha=1) with V=100,000V=100{,}000 word types, what percentage of all tokens do the 100 most frequent types cover?

Show the answer

43 %

H100/H100,000≈(ln⁡100+0.577)/(ln⁡105+0.577)=5.19/12.09≈0.43H_{100}/H_{100{,}000}\approx(\ln100+0.577)/(\ln10^5+0.577)=5.19/12.09\approx0.43. The top 10,00010{,}000 types cover only 9.79/12.09≈81%9.79/12.09\approx81\%, so the remaining 90,00090{,}000 types share 19% of the tokens, each with probability below 10−510^{-5}. 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 nn tokens be drawn i.i.d. from an unknown distribution pp over a countable alphabet, and let the missing mass M0=∑x unseenpxM_0=\sum_{x\text{ unseen}}p_x 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 M^0=N1/n\hat M_0=N_1/n: the fraction of the sample made of types seen exactly once. More generally, types seen rr times get the adjusted count r∗=(r+1)Nr+1/Nrr^*=(r+1)N_{r+1}/N_r.

DerivationProof
  1. E[M0]=∑xpx(1−px)n,E[N1]n=∑xpx(1−px)n−1\E[M_0]=\sum_xp_x(1-p_x)^n,\qquad\frac{\E[N_1]}n=\sum_xp_x(1-p_x)^{n-1}

    Type xx is unseen with probability (1−px)n(1-p_x)^n and seen exactly once with probability npx(1−px)n−1np_x(1-p_x)^{n-1}. By linearity of expectation:

  2. E[N1]n−E[M0]=∑xpx(1−px)n−1[1−(1−px)]=∑xpx2(1−px)n−1 ≥ 0\frac{\E[N_1]}n-\E[M_0]=\sum_xp_x(1-p_x)^{n-1}\big[1-(1-p_x)\big]=\sum_xp_x^2(1-p_x)^{n-1}\ \ge\ 0

    Subtract term by term:

  3. ∑xpx⋅px(1−px)n−1 ≤ 1n∑xpx=1n■\sum_xp_x\cdot p_x(1-p_x)^{n-1}\ \le\ \frac1n\sum_xp_x=\frac1n\qquad\blacksquare

    On [0,1][0,1] the function p(1−p)n−1p(1-p)^{n-1} peaks at p=1/np=1/n, where it equals 1n(1−1n)n−1≤1n\tfrac1n(1-\tfrac1n)^{n-1}\le\tfrac1n. So each term is at most px/np_x/n, and the probabilities sum to one:

  4. E[Mr]=(nr)∑xpxr+1(1−px)n−r ≈ r+1n E[Nr+1]\E[M_r]=\binom nr\sum_xp_x^{r+1}(1-p_x)^{n-r}\ \approx\ \frac{r+1}{n}\,\E[N_{r+1}]

    The same computation for types seen rr times links their total mass MrM_r to Nr+1N_{r+1}, which is where the adjusted count r∗r^* comes from:

The bias bound holds for every distribution, however many types it has. Concentration holds too: McAllester and Schapire (2000) showed that ∣M0−N1/n∣=O(log⁡(1/δ)/n)\abs{M_0-N_1/n}=\order{\sqrt{\log(1/\delta)/n}} with probability at least 1−δ1-\delta. In practice NrN_r is noisy and often zero for large rr, so Simple Good–Turing (Gale & Sampson, 1995) fits a line to log⁡Nr\log N_r against log⁡r\log r before computing r∗r^*, 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 c≥2c\ge2 times in the first half occur on average about c−0.75c-0.75 times in the second: counts shrink by a roughly constant amount. Absolute discounting subtracts a fixed D∈(0,1]D\in(0,1] 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 N1+(v ∙)N_{1+}(v\,\bullet) the number of distinct words seen after vv and N1+(∙ w)N_{1+}(\bullet\,w) the number of distinct words seen before ww:

PKN(w∣v)=max⁡(c(v,w)−D,0)c(v)+λ(v) Pcont(w),λ(v)=D N1+(v ∙)c(v),Pcont(w)=N1+(∙ w)N1+(∙ ∙).P_{\mathrm{KN}}(w\mid v)=\frac{\max\big(c(v,w)-D,0\big)}{c(v)}+\lambda(v)\,P_{\text{cont}}(w),\qquad\lambda(v)=\frac{D\,N_{1+}(v\,\bullet)}{c(v)},\qquad P_{\text{cont}}(w)=\frac{N_{1+}(\bullet\,w)}{N_{1+}(\bullet\,\bullet)}.
DerivationIt normalizes, and continuation counts preserve the unigram marginals
  1. ∑wmax⁡(c(v,w)−D,0)c(v)=c(v)−D N1+(v ∙)c(v)=1−λ(v)⟹∑wPKN(w∣v)=1\sum_w\frac{\max(c(v,w)-D,0)}{c(v)}=\frac{c(v)-D\,N_{1+}(v\,\bullet)}{c(v)}=1-\lambda(v)\quad\Longrightarrow\quad\sum_wP_{\mathrm{KN}}(w\mid v)=1

    Every observed count is at least 1≥D1\ge D, so discounting removes exactly DD from each of the N1+(v ∙)N_{1+}(v\,\bullet) observed successors of vv, and λ(v)\lambda(v) is precisely that removed mass:

  2. ∑vp^(v) PKN(w∣v)=c(w)N⟺c(w)−D N1+(∙ w)+D Plow(w)∑vN1+(v ∙)=c(w)\sum_v\hat p(v)\,P_{\mathrm{KN}}(w\mid v)=\frac{c(w)}N\quad\Longleftrightarrow\quad c(w)-D\,N_{1+}(\bullet\,w)+D\,P_{\text{low}}(w)\sum_vN_{1+}(v\,\bullet)=c(w)

    Why continuation counts? Require the smoothed bigram model, averaged over histories with their empirical frequencies p^(v)=c(v)/N\hat p(v)=c(v)/N, to reproduce the empirical unigram frequency of every word, and solve for the unknown lower-order distribution PlowP_{\text{low}}:

  3. Plow(w)=N1+(∙ w)N1+(∙ ∙)=Pcont(w)P_{\text{low}}(w)=\frac{N_{1+}(\bullet\,w)}{N_{1+}(\bullet\,\bullet)}=P_{\text{cont}}(w)

    Since ∑vN1+(v ∙)=N1+(∙ ∙)\sum_vN_{1+}(v\,\bullet)=N_{1+}(\bullet\,\bullet), the number of distinct bigram types, the solution is unique and is exactly the continuation probability:

Check your understanding

A history vv occurred c(v)=10c(v)=10 times, followed by three distinct words with counts 66, 33 and 11. With discount D=0.75D=0.75, what fraction of vv's probability mass does interpolated Kneser–Ney give to the continuation distribution?

  1. 7.5%7.5\%
  2. 22.5%22.5\%
  3. 30%30\%
  4. 75%75\%
Show the answer

B. 22.5%22.5\%

λ(v)=D N1+(v ∙)/c(v)=0.75×3/10=0.225\lambda(v)=D\,N_{1+}(v\,\bullet)/c(v)=0.75\times3/10=0.225. The three observed successors keep (5.25+2.25+0.25)/10=77.5%(5.25+2.25+0.25)/10=77.5\%, 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 D1,D2,D3+D_1,D_2,D_{3+} for counts 11, 22 and ≥3\ge3, estimated from the count-of-counts nrn_r: with Y=n1/(n1+2n2)Y=n_1/(n_1+2n_2), Dr=r−(r+1)Y nr+1/nrD_r=r-(r+1)Y\,n_{r+1}/n_r. 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 0.60.6–1.31.3 bits per character. Brown et al. (1992) derived an upper bound of 1.751.75 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 ℓ\ell bits on text averaging LL characters per token achieves ℓ/L\ell/L 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 0.40.4; 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 N1/nN_1/n, with bias in [0,1/n][0,1/n] for every distribution, and adjusts counts to r∗=(r+1)Nr+1/Nrr^*=(r+1)N_{r+1}/N_r.
  • 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.

Question 1

In a sample of n=1,000n=1{,}000 word tokens, N1=300N_1=300 types occur exactly once. What is the Good–Turing estimate of the probability that the next token is a type never seen before?

  1. 0.30.3
  2. 0.00030.0003
  3. 0.70.7
  4. It cannot be estimated without knowing the vocabulary size
Show the answer

A. 0.30.3

M^0=N1/n=300/1000=0.3\hat M_0=N_1/n=300/1000=0.3. The estimate needs no vocabulary size, and its bias is at most 1/n=0.0011/n=0.001 for any distribution.

Question 2

Why does interpolated Kneser–Ney set λ(v)=D N1+(v ∙)/c(v)\lambda(v)=D\,N_{1+}(v\,\bullet)/c(v)?

  1. It is tuned on held-out data
  2. It equals the probability that vv is followed by an unseen word under maximum likelihood
  3. It is exactly the mass removed by discounting each of vv's observed successors, so the distribution sums to one
  4. It makes PKNP_{\mathrm{KN}} equal to the continuation probability
Show the answer

C. It is exactly the mass removed by discounting each of vv's observed successors, so the distribution sums to one

Discounting removes DD from each of the N1+(v ∙)N_{1+}(v\,\bullet) observed successors, a total of D N1+(v ∙)/c(v)D\,N_{1+}(v\,\bullet)/c(v) in probability, and λ(v)\lambda(v) redistributes exactly that amount.

Question 3

Which requirement singles out Kneser–Ney's continuation probability as the lower-order distribution?

  1. It maximizes the likelihood of the training bigrams
  2. It is the uniform distribution over the vocabulary
  3. It minimizes the number of parameters
  4. 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 ∑vp^(v)PKN(w∣v)=c(w)/N\sum_v\hat p(v)P_{\mathrm{KN}}(w\mid v)=c(w)/N and solving gives Plow(w)=N1+(∙ w)/N1+(∙ ∙)P_{\text{low}}(w)=N_{1+}(\bullet\,w)/N_{1+}(\bullet\,\bullet) uniquely: a word's lower-order probability is proportional to the number of distinct words it follows.

Question 4

A language model reaches 0.90.9 bits per character on a large sample of English text. What does this establish about the entropy rate of that text?

  1. The entropy rate is at most about 0.90.9 bits per character, since every model's expected log-loss upper-bounds it
  2. The entropy rate is exactly 0.90.9 bits per character
  3. The entropy rate is at least 0.90.9 bits per character
  4. Nothing, because entropy rates are defined only for character-level models
Show the answer

A. The entropy rate is at most about 0.90.9 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.