N-gram Models and the Curse of Sparsity

In the last post we established that language modeling boils down to one thing: estimating $P(w_t \mid w_1, \ldots, w_{t-1})$, the probability of the next token given everything before it. And we built a toy bigram model that did this by counting pairs of words.

So here's the question. Why only pairs? Why not triples, or quadruples, or the entire history? The answer is one of the most important ideas in pre-neural NLP, and it comes down to a simple fact about counting: you run out of data.

The Markov Assumption

The full conditional $P(w_t \mid w_1, \ldots, w_{t-1})$ conditions on every word that came before. That's a different distribution for every possible history. If your vocabulary has 50,000 words, the number of possible histories of length 10 is $50{,}000^{10}$, which is roughly $10^{47}$. There are not that many atoms in the observable universe, let alone sentences in any training corpus.

So we make a simplifying assumption. We pretend the next word only depends on the last $n-1$ words. This is the Markov assumption:

When $n = 2$, we get a bigram model (condition on the previous word). When $n = 3$, a trigram model (condition on the previous two). When $n = 5$, a 5-gram. The bigger $n$ is, the more context the model sees. But the bigger $n$ is, the more unique contexts you need to have observed in training, and most of them will never show up.

That's the fundamental trade-off. More context means better predictions in theory, but worse data coverage in practice.

Counting and the Zero Problem

Let's make this concrete. Here's a small corpus of five sentences:

Look at all those zeros. Even with just 12 unique words and a bigram model, the matrix is already overwhelmingly empty. With $V = 12$ there are $V^2 = 144$ possible bigrams, and only 18 of them actually show up in the corpus. That's 126 zero cells out of 144, or about 87.5% sparsity. The model has never seen most word pairs, and will assign them probability zero.

And that's bigrams. For trigrams, you're indexing into a three-dimensional tensor. The number of possible trigrams is $V^3 = 1{,}728$. Our corpus has 18 trigram tokens (17 distinct), so out of 1,728 possible trigrams, 1,711 are zero. Everything else is zero.

Scale this up to a real vocabulary of 50,000 words. The number of possible trigrams is $50{,}000^3 = 1.25 \times 10^{14}$. Even a billion-word training corpus only covers a tiny fraction of that space.

Why Zeros Are Lethal

Here's where it gets really bad. Remember the chain rule from the last post?

We're multiplying conditional probabilities together. If any single one of those conditionals is zero, the entire product is zero. Your model says the sentence is impossible. A perfectly reasonable sentence that happens to contain one bigram your model never saw in training gets a probability of exactly zero.

Let's walk through it. Suppose we have a trigram model trained on our toy corpus, and we want to score the sentence "a cat sat on the rug". We need these trigram probabilities:

The first two trigrams never appeared in training, so their counts are zero, and their probabilities are zero. The whole sentence gets $P = 0$, perplexity = $\infty$. The model has catastrophically failed on a completely normal sentence, because it happened to see "the cat sat" but never "a cat sat".

This is the curse of sparsity.

Maximum Likelihood Estimation (and Its Limits)

The basic approach is called maximum likelihood estimation, or MLE. For a bigram model, it's just:

Count how many times the bigram $(w_{t-1}, w_t)$ appeared, divide by how many times the context word $w_{t-1}$ appeared. For trigrams, same idea:

MLE gives the exact right answer if your training corpus is infinitely large. With a finite corpus, it overfits to the training data and gives zeros to everything it hasn't seen. We need something better.

Smoothing: Stealing from the Rich

The idea behind smoothing is simple. Take some probability mass away from n-grams you did see and redistribute it to n-grams you didn't see. Every smoothing method is a different answer to the question: how much mass to steal, and where to put it.

Add-k smoothing (Laplace). The crudest approach. Add a constant $k$ to every count:

When $k = 1$, this is Laplace smoothing. It's easy to implement (we used it in the last post's bigram model), but it assigns way too much probability to unseen events and way too little to seen ones. Chen and Goodman showed it performs poorly compared to almost any other method.

Interpolation. Instead of just using the trigram estimate, mix it with the bigram and unigram estimates:

where $\lambda_1 + \lambda_2 + \lambda_3 = 1$. The trigram estimate is the most specific, but might be zero. The bigram is less specific but more likely to have data. The unigram just knows word frequencies and is never zero (assuming every word appears at least once in training). Mixing them together means you always have a fallback. The lambdas are typically tuned on held-out data.

Interpolation works well in practice, and the implementation sketch below uses it.

Backoff. Similar spirit, but instead of always mixing, you only fall back to a lower-order model when the higher-order count is zero. Katz backoff is the classic version.

Kneser-Ney. The one that actually won.

Kneser-Ney: The Right Way to Back Off

Here's the problem with simple interpolation and backoff. When you fall back from a trigram to a bigram to a unigram, the unigram probability $P(w)$ is just how often that word appears overall. But that's not really what you want.

Consider the word "Francisco". It's a fairly common word in English corpora, because "San Francisco" appears a lot. So the unigram probability $P(\text{Francisco})$ is reasonably high. But if I give you the context "I ate a delicious ___" and ask you to fill in the blank, "Francisco" should get basically zero probability. The unigram count is misleading here because "Francisco" appears frequently but only ever in one context.

Kneser and Ney's insight was: when you're backing off to a lower-order model, you shouldn't ask "how often does this word appear?" You should ask "how many different contexts does this word appear in?"

This is the continuation probability:

The numerator counts how many distinct words precede $w$ in the corpus. The denominator is just a normalizing constant (total number of distinct bigram types). A word like "Francisco" that only ever follows "San" gets a continuation count of 1. A word like "the" that follows hundreds of different words gets a high continuation count.

So when you back off and need to estimate the probability of a word in a novel context, Kneser-Ney says: words that appear in many different contexts are more likely to appear in this new context too. Words that are locked into one specific context (like "Francisco") probably shouldn't show up here.

Kneser-Ney starts from absolute discounting: subtract a discount from every positive n-gram count and redistribute the saved mass to a lower-order continuation distribution. In simple presentations this discount is often given as a single value around 0.75. The strongest classic version, modified interpolated Kneser-Ney (Chen & Goodman, 1999), uses separate discounts for count-1, count-2, and count-3+ n-grams, which fits the data noticeably better. That's the one that won their empirical comparison across corpus sizes and n-gram orders. Teh (2006) later showed it can be derived as an approximation to a hierarchical Pitman-Yor process, giving the trick a Bayesian justification.

Kneser-Ney and other heavily engineered n-gram models were the dominant practical baseline through the 2000s. Neural language models began challenging them earlier than the popular telling suggests: Bengio et al. published the neural probabilistic language model in 2003, explicitly framing it as an attack on the curse of dimensionality, and Mikolov et al. showed in 2010 that an RNN language model could outperform strong backoff baselines, in some cases even when the backoff model had much more data. The decisive shift toward neural methods happened across the early 2010s, with word2vec (2013) marking the moment embeddings became the dominant representational story.

Worked Example: Trigram Probabilities by Hand

Let's go back to our toy corpus and work through trigram MLE, then see how interpolation helps.

Our corpus:

1. the cat sat on the mat
2. the cat ate the fish
3. the dog sat on the rug
4. a dog chased the cat
5. the cat slept on a mat

Suppose we want $P(\text{on} \mid \text{cat}, \text{sat})$.

The MLE estimate: count("cat sat on") / count("cat sat") = 1/1 = 1.0. Looks great, but that 1.0 is a lie. We only saw "cat sat" once. We're maximally confident based on a single observation.

Now suppose we want $P(\text{on} \mid \text{dog}, \text{sat})$.

MLE: count("dog sat on") / count("dog sat") = 1/1 = 1.0. Same situation.

And what about $P(\text{on} \mid \text{fish}, \text{sat})$?

MLE: count("fish sat on") / count("fish sat") = 0/0. Undefined. The context "fish sat" never appeared at all.

With interpolation ($\lambda_3 = 0.5, \lambda_2 = 0.3, \lambda_1 = 0.2$), that last case becomes:

The trigram contributes nothing, but the bigram $P(\text{on} \mid \text{sat})$ is 1.0 (every time "sat" appeared in our corpus, it was followed by "on"), and the unigram $P(\text{on})$ is roughly 3/28 (three occurrences of "on" across 28 tokens of training text). So:

That's not zero. The sentence can be scored. The model hasn't catastrophically failed just because one specific trigram was missing.

Implementation: Interpolated Trigram LM

Here's a teaching-sized trigram language model with interpolated smoothing. It mixes trigram, bigram, and unigram probabilities so that an unseen higher-order context doesn't collapse the score to zero, as long as the word itself is in the unigram vocabulary.

import math
from collections import defaultdict
 
class InterpolatedTrigramLM:
    def __init__(self, lambdas=(0.5, 0.3, 0.2)):
        self.l3, self.l2, self.l1 = lambdas
        # Counts for each n-gram order
        self.tri = defaultdict(int)   # (w1, w2, w3) -> count
        self.bi  = defaultdict(int)   # (w1, w2) -> count
        self.uni = defaultdict(int)   # w -> count
        self.total = 0                # total tokens
        self.vocab = set()
 
    def train(self, sentences):
        for tokens in sentences:
            t = ["<s>", "<s>"] + tokens + ["</s>"]
            # Unigram counts cover the real tokens only — boundary symbols
            # are kept out of the unigram distribution so P(w) sums to 1
            # over the actual vocabulary.
            for w in tokens:
                self.uni[w] += 1
                self.total += 1
                self.vocab.add(w)
            for i in range(2, len(t)):
                self.tri[(t[i-2], t[i-1], t[i])] += 1
                self.bi[(t[i-1], t[i])] += 1
 
    def prob(self, w, w1, w2):
        """P(w | w1, w2) using interpolation, renormalizing if a higher-
        order context is missing so the active weights still sum to 1."""
        # Trigram: P(w | w1, w2)
        tri_ctx = sum(v for k, v in self.tri.items()
                      if k[0] == w1 and k[1] == w2)
        p3 = self.tri[(w1, w2, w)] / tri_ctx if tri_ctx > 0 else 0
 
        # Bigram: P(w | w2)
        bi_ctx = sum(v for k, v in self.bi.items() if k[0] == w2)
        p2 = self.bi[(w2, w)] / bi_ctx if bi_ctx > 0 else 0
 
        # Unigram: P(w). Always available (assuming w is in vocab).
        p1 = self.uni[w] / self.total if self.total > 0 else 0
 
        # Only mix in the rungs that actually have context, then renormalize
        # the active weights. Otherwise an unseen trigram context silently
        # drops 0.5 of the mass and the conditional doesn't sum to 1.
        weights, terms = [], []
        if tri_ctx > 0:
            weights.append(self.l3); terms.append(p3)
        if bi_ctx > 0:
            weights.append(self.l2); terms.append(p2)
        weights.append(self.l1); terms.append(p1)
        z = sum(weights)
        return sum(wt * pt for wt, pt in zip(weights, terms)) / z
 
    def perplexity(self, sentences):
        log_prob_sum = 0
        n = 0
        for tokens in sentences:
            t = ["<s>", "<s>"] + tokens + ["</s>"]
            for i in range(2, len(t)):
                p = self.prob(t[i], t[i-2], t[i-1])
                if p == 0:
                    return float("inf")
                log_prob_sum += math.log2(p)
                n += 1
        return 2 ** (-log_prob_sum / n)
 
corpus = [
    "the cat sat on the mat".split(),
    "the cat ate the fish".split(),
    "the dog sat on the rug".split(),
    "a dog chased the cat".split(),
    "the cat slept on a mat".split(),
]
 
lm = InterpolatedTrigramLM(lambdas=(0.5, 0.3, 0.2))
lm.train(corpus)
 
# Test: seen trigram context
print(f"P(on | cat, sat)  = {lm.prob('on', 'cat', 'sat'):.3f}")
 
# Test: unseen trigram, but seen bigram
print(f"P(on | fish, sat) = {lm.prob('on', 'fish', 'sat'):.3f}")
 
# Test: completely novel context
print(f"P(on | rug, fish) = {lm.prob('on', 'rug', 'fish'):.3f}")
 
# Perplexity on a held-out sentence
test = ["a cat sat on the rug".split()]
print(f"\nPerplexity on 'a cat sat on the rug': {lm.perplexity(test):.1f}")

The key thing to notice: prob() is three lines of real logic. Compute the trigram estimate, the bigram estimate, the unigram estimate, mix them. The trigram gives you specificity when you have data. The unigram is the safety net that keeps you off zero. The lambdas control how much you trust each level.

A few things this teaching version skips that a production n-gram model wouldn't. First, there's no <UNK> token: a test word that didn't appear in training has a unigram probability of zero, so the safety net falls through. Real systems define a fixed vocabulary up front and route everything else to <UNK>. Second, the lambdas here are fixed constants. In a production system you'd tune them on held-out data using EM (Jelinek and Mercer's deleted-interpolation algorithm), often with context-dependent weights. Third, you'd replace the simple unigram fallback with Kneser-Ney continuation probabilities. But this basic version already gets you past the zero-probability catastrophe whenever the test word is in vocab.

Misconceptions

"More data fixes sparsity." Yes, more data fills in more of the count table. But the number of possible n-grams grows combinatorially with $n$. With a vocabulary of 50,000 words, possible bigrams: $2.5 \times 10^9$. Possible trigrams: $1.25 \times 10^{14}$. Possible 5-grams: $3.125 \times 10^{23}$. Google's Web 1T 5-gram corpus covered a trillion tokens and remains one of the largest n-gram datasets ever assembled, and even it had massive sparsity at the 5-gram level. You can't corpus-size your way out of a combinatorial explosion.

"N-grams are too simple to be worth understanding." I think it's the other way around. They're worth understanding because they're simple. They make the sparsity problem totally transparent. When you later see a neural language model handle unseen word combinations gracefully, the question to hold is: what is it doing that n-grams couldn't? The answer is generalization through continuous representations, starting with word2vec.

"Smoothing is just a hack." Smoothing is doing something principled: it's a form of regularization. Add-k is a maximum a posteriori estimate with a uniform Dirichlet prior. Kneser-Ney approximates a hierarchical Pitman-Yor process. The math is solid. The real limitation is that discrete counting can only generalize by backing off to shorter contexts. It has no notion of word similarity. "Dog sat" and "cat sat" are equally unrelated in an n-gram model. Neural models will fix that.

What's next

The next post covers word2vec and the embedding revolution, what happens when you replace discrete word identities with continuous vectors, and why that one change makes the sparsity problem dramatically less severe.

Additional reading (and watching)

• Chen, S.F. & Goodman, J. (1999). An Empirical Study of Smoothing Techniques for Language Modeling. Computer Speech & Language, 13(4), 359-394. The definitive comparison of smoothing methods. Modified interpolated Kneser-Ney won across nearly every condition they tested.
• Jurafsky, D. & Martin, J.H. Speech and Language Processing, 3rd ed., Ch. 3. The standard textbook treatment of n-gram language models, covering MLE, smoothing, backoff, and evaluation.
• Kneser, R. & Ney, H. (1995). Improved Backing-Off for M-Gram Language Modeling. ICASSP. Introduced continuation probability, the key insight that drives Kneser-Ney smoothing.
• Teh, Y.W. (2006). A Bayesian Interpretation of Interpolated Kneser-Ney. Showed that Kneser-Ney can be derived as an approximation to a hierarchical Pitman-Yor process, giving it a principled Bayesian justification.
• Mikolov, T. et al. (2010). Recurrent Neural Network Based Language Model. Interspeech. The paper that showed a simple RNN could outperform the best n-gram models, launching the neural language modeling era.
• Brants, T. & Franz, A. (2006). Web 1T 5-gram Version 1. Linguistic Data Consortium. Google's trillion-token web n-gram corpus, released as LDC2006T13. The reference dataset for "what happens when you just scale counting up."
• Jelinek, F. & Mercer, R. (1980). Interpolated Estimation of Markov Source Parameters from Sparse Data. Proceedings of the Workshop on Pattern Recognition in Practice. The deleted-interpolation EM procedure that became the standard way to tune mixing weights between n-gram orders.