Chapter 1.2 β€” Statistical and Count-Based Language Models

Contents

  1. The simplest possible answer: count and divide
  2. The Markov assumption: why n-grams exist at all
  3. The sparsity problem
  4. Smoothing: giving probability to things you've never seen
  5. Kneser-Ney smoothing and why it won
  6. Why this approach hit a ceiling
  7. Interview angle
  8. Self-check questions
  9. Sources

1. The simplest possible answer: count and divide

Chapter 1.1 established that a language model's whole job is estimating \(P(x_i \mid x_1, \ldots, x_{i-1})\) β€” the probability of the next token given everything before it. The most direct way to estimate a conditional probability from data is also the oldest: count how often it happened, and divide by how often the condition occurred.

$$P(x_i \mid x_1, \ldots, x_{i-1}) \approx \frac{\text{count}(x_1, \ldots, x_{i-1}, x_i)}{\text{count}(x_1, \ldots, x_{i-1})}$$

This is maximum likelihood estimation, and it is exactly what it sounds like: go through a large corpus, tally every sequence of tokens you see, and turn those tallies into probabilities. It requires no gradient descent, no architecture, no training loop in the modern sense β€” just a lookup table. For decades, this was language modeling.

2. The Markov assumption: why n-grams exist at all

There's an obvious problem with the formula above: as \(i\) grows, the context \(x_1, \ldots, x_{i-1}\) becomes a longer and longer specific string, and the chance you've ever seen that exact string before in a finite corpus drops to zero almost immediately. A count-based table can't estimate a probability for a context it has never observed.

The fix that made count-based modeling tractable is the Markov assumption: instead of conditioning on the entire history, condition only on the last \(n-1\) tokens.

$$P(x_i \mid x_1, \ldots, x_{i-1}) \approx P(x_i \mid x_{i-n+1}, \ldots, x_{i-1})$$

This is where the term "n-gram model" comes from. A bigram model (\(n=2\)) predicts the next word from just the previous word. A trigram model (\(n=3\)) uses the previous two. This is a real and consequential trade-off, worth naming explicitly, because the same trade-off reappears in every architecture in this book under different names: the further back a model can "see," the better it can in principle predict, but the harder the estimation problem becomes, because there are exponentially more possible contexts as \(n\) grows (with a vocabulary of size \(|V|\), the number of distinct contexts of length \(n-1\) is \(\#\text{contexts} = |V|^{\,n-1}\)). N-gram models made this trade-off by brute-force truncation. RNNs would later make it by carrying a fixed-size hidden state instead of truncating outright. Transformers would make it by attending over a bounded window directly. The engineering question β€” how much context can a model realistically condition on, and how β€” is the throughline of this entire book, and n-grams are where it starts.

3. The sparsity problem

Truncating context to the last \(n-1\) words helps, but it doesn't eliminate the core difficulty, it just shrinks it. Even trigrams over a modest vocabulary produce an astronomical number of possible three-word combinations, and natural language is Zipfian: a small number of words and phrases are extremely common, and a very long tail of words and phrases are individually rare but collectively make up a large share of real text. This means that no matter how large your training corpus is, you will constantly encounter n-grams at inference time that never appeared in training, or appeared only once or twice β€” nowhere near enough to estimate a reliable probability.

This is the sparsity problem, and it's not a minor implementation detail; it's the central obstacle that count-based language modeling spent decades trying to work around. If your model assigns probability exactly zero to any n-gram it never saw during training, then the moment a real sentence contains one unseen trigram, the whole sequence's probability collapses to zero and the model's cross-entropy loss (Chapter 1.1) becomes infinite. A language model that can be broken by a single novel three-word combination is not usable in the real world, so something had to give.

4. Smoothing: giving probability to things you've never seen

The fix is smoothing: systematically taking a little probability mass away from things you did observe and redistributing it to things you didn't, so nothing ever gets assigned exactly zero. The simplest version, Laplace (add-one) smoothing, just pretends every possible n-gram was seen one extra time. It works, technically, but it's crude β€” it spreads probability mass far too evenly across the enormous space of unseen n-grams, most of which are still linguistically implausible even if they weren't in the training data.

Better approaches use backoff and interpolation β€” two related but distinct strategies for combining estimates of different specificity, worth telling apart precisely. Interpolation always blends the trigram, bigram, and unigram estimates together in a weighted mixture, regardless of whether the trigram itself was ever actually observed. Backoff, formalized by Katz as Katz backoff, takes a stricter view: use the specific trigram estimate whenever the trigram was actually seen (discounted slightly to reserve some probability mass), and only fall back to the bigram estimate when the trigram wasn't observed at all, falling back further to the unigram if the bigram wasn't observed either. The discounting inside Katz backoff is itself a named smoothing technique worth knowing: Good-Turing discounting estimates how much probability mass to reserve for unseen events by looking at how many distinct events were observed exactly once, exactly twice, and so on β€” the rate at which brand-new events keep appearing as you see more data turns out to be informative about how much of the true distribution's mass still belongs to things you haven't seen yet. Formally, an event observed \(r\) times has its count re-estimated as

$$r^{*} = (r+1)\,\frac{N_{r+1}}{N_r}$$

where \(N_r\) is the number of n-grams observed exactly \(r\) times. The idea uniting all of these approaches β€” trust the most specific context you have enough data to trust, and gracefully degrade to less specific, more reliably estimated contexts otherwise β€” long predates n-grams and reappears constantly in statistics, but n-gram language modeling is where it was engineered most thoroughly.

5. Kneser-Ney smoothing and why it won

Among the many smoothing techniques developed through the 1990s, Kneser-Ney smoothing (and its later refinement, modified Kneser-Ney, formalized by Chen and Goodman) became the de facto standard, and it's worth understanding why, because the reasoning is a genuinely clever statistical insight rather than just an engineering hack.

Simple backoff schemes fall back to lower-order statistics using raw frequency: if you need a unigram estimate for a word, use how often that word appears overall. Kneser-Ney's insight is that raw unigram frequency is the wrong thing to fall back on. Consider the word "Francisco." It might be very frequent in a corpus β€” but almost entirely because it follows "San." Its raw frequency overstates how useful it is as a general fallback prediction, because it doesn't actually occur in many different contexts; it occurs in one specific context, a lot. Kneser-Ney smoothing instead estimates the lower-order distribution based on continuation probability: not how often a word appears, but how many distinct contexts it appears after:

$$P_{\text{cont}}(w) = \frac{|\{v : c(v, w) > 0\}|}{\sum_{w'} |\{v : c(v, w') > 0\}|}$$

A word that shows up after many different preceding words is a genuinely good general-purpose guess when you lack specific context; a word that only ever follows one specific other word is not, no matter how frequent it looks in raw counts.

This distinction β€” between raw frequency and diversity of context β€” is what let Kneser-Ney outperform other smoothing methods so consistently that it remained the strongest standard n-gram smoothing technique for roughly two decades, well into the era when neural methods started to compete with count-based models on the same benchmarks.

6. Why this approach hit a ceiling

Even with the best smoothing available, n-gram models had a ceiling that no amount of engineering could raise, for two related reasons.

First, the Markov truncation is a real information loss, not just an implementation convenience. Long-range dependencies β€” a pronoun referring back to a noun introduced ten words earlier, a verb whose correct tense depends on a subject far to the left, a topic established a paragraph ago that should influence the next word β€” are invisible to a model that can only see the last \(n-1\) tokens. Increasing \(n\) doesn't really solve this, because sparsity gets catastrophically worse as \(n\) grows; in practice n-gram models rarely went beyond \(n=5\) even with huge corpora and aggressive smoothing.

Second, and more fundamentally, count-based models treat every distinct word string as an entirely separate entity. There is no mechanism by which learning something about "the cat sat on the mat" tells the model anything about "the dog sat on the rug," even though those sentences are almost interchangeable in meaning and grammatical structure. Words are, from the table's point of view, just distinct symbols to be counted β€” the model has no notion that "cat" and "dog" are similar in any way that should transfer statistical strength between them. This is exactly the gap that neural language models were built to close, by replacing symbolic word identities with learned vector representations that place similar words near each other in a continuous space β€” the subject of Chapter 1.3, and the single biggest conceptual leap between this chapter and the next.

7. Interview angle

Interviewers rarely ask you to build an n-gram model from scratch, but this chapter comes up constantly as a way to test whether you understand why neural approaches were necessary, not just that they exist:

  • "Why can't you just scale up n-gram models instead of using neural networks?" β€” a strong answer names both failure modes explicitly: the sparsity/Markov-truncation ceiling on context length, and the lack of any generalization between similar-but-distinct words or phrases.
  • "What is the Kneser-Ney insight, in one sentence?" β€” the expected answer is about continuation probability (diversity of contexts a word follows), not raw frequency, and being able to state that crisply signals real understanding rather than memorized trivia.
  • "How would you handle a word your model has never seen at inference time?" β€” this is really asking whether you understand smoothing and, more broadly, out-of-vocabulary handling, a concern that resurfaces almost unchanged in the tokenization chapter.

8. Self-check questions

  1. Write the maximum-likelihood estimate for a trigram probability in terms of corpus counts, and explain why this estimate becomes unreliable as context length grows.
  2. What specific problem does the Markov assumption solve, and what does it cost you in return?
  3. Explain the sparsity problem in your own words, and why assigning probability zero to an unseen n-gram is unacceptable for a working language model.
  4. What is the difference between backoff and interpolation as smoothing strategies?
  5. Explain why Kneser-Ney smoothing's use of "continuation probability" is a better fallback estimate than raw unigram frequency. Use the "Francisco" example or one of your own.
  6. Name the two structural reasons n-gram models hit a ceiling that smoothing alone couldn't fix, and explain how each one specifically motivates the shift to neural language models in the next chapter.

9. Sources

  • Kneser, R., & Ney, H. (1995). Improved backing-off for M-gram language modeling. ICASSP 1995, vol. 1, pp. 181–184. RWTH Aachen PDF
  • Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 359–394.

Self-check quiz

Test your understanding of this chapter with a short quiz β€” a mix of concept questions and quick calculations.

What does the Markov assumption used by n-gram models do?

Explanation: Instead of conditioning on the entire history x_1...x_{i-1}, the Markov assumption conditions only on the last nβˆ’1 tokens β€” this is where n-gram models get their name.

What is the "sparsity problem" in n-gram language modeling?

Explanation: Natural language is Zipfian, so no matter how large the corpus, you'll keep hitting n-grams at inference time that never appeared in training β€” assigning them probability zero would send cross-entropy to infinity.

What is the key insight behind Kneser-Ney smoothing's improvement over simple backoff?

Explanation: The "Francisco" example: it's frequent only because it follows "San" β€” raw frequency overstates its value as a general fallback. Kneser-Ney instead rewards words that show up after many different contexts.

What is the deeper structural limitation of count-based n-gram models that no amount of smoothing can fix?

Explanation: Count tables have no notion that "cat" and "dog" are similar β€” learning about one sentence transfers nothing to a near-synonymous one. Closing this gap is exactly what neural word representations (Chapter 1.3) were built for.

In a training corpus, the sequence "the cat sat on" appears 8 times, and the prefix "the cat sat" appears 40 times. Using maximum-likelihood estimation, what is $P(\text{on} \mid \text{the cat sat})$?

Explanation: MLE probability = count("the cat sat on") / count("the cat sat") = 8 / 40 = 0.2.

For an n-gram model with $n = 5$ (a 5-gram model), on how many previous tokens does it condition its prediction?

Explanation: An n-gram model conditions on the last nβˆ’1 tokens, so with n=5 that's 5βˆ’1 = 4 previous tokens.

Using Laplace (add-one) smoothing, a word $w$ appears 3 times in a training corpus of 100 total tokens, and the vocabulary size is 1000. What is the smoothed probability estimate $P_{\text{Laplace}}(w) = \dfrac{\text{count}(w) + 1}{\text{total} + V}$? (Round to 4 decimal places.)

Explanation: (3 + 1) / (100 + 1000) = 4 / 1100 β‰ˆ 0.0036.

The bigram "of the" appears 450 times in a corpus, and the word "of" appears 9,000 times overall. What is the maximum-likelihood estimate of $P(\text{the} \mid \text{of})$?

Explanation: 450 / 9000 = 0.05.

What does Good-Turing discounting use to estimate how much probability mass to reserve for events never yet observed?

Explanation: Good-Turing looks at how many distinct events were observed exactly once, exactly twice, and so on β€” how often brand-new events keep showing up as data accumulates turns out to be informative about how much of the true distribution's mass still belongs to unseen events.

Using Good-Turing re-estimation $r^{*} = (r+1) \frac{N_{r+1}}{N_r}$, an n-gram was observed $r = 2$ times. There are $N_2 = 50$ n-grams observed exactly twice, and $N_3 = 20$ n-grams observed exactly three times. What is the re-estimated count $r^{*}$?

Explanation: $r^{*} = (2+1) \times (20/50) = 3 \times 0.4 = 1.2$ β€” Good-Turing discounts the raw count of 2 down to an effective count of 1.2.