N-gram Models and the Curse of Sparsity

The bigram model in the last post estimated $P(w_t \mid w_{t-1})$ by counting word pairs. An n-gram model extends that approach to longer histories.

Longer histories give us more context, but fewer examples of each context to count. How far can we extend the history before those counts become too sparse?

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}$. That is far more histories than any training corpus could cover.

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.

Counting and the Zero Problem

Consider a 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.

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.

How a Zero Affects Sequence Probability

A zero conditional probability also affects the sequence probability. Recall 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. With zero probability assigned to either one, the sentence gets $P = 0$ and perplexity $= \infty$. Seeing "the cat sat" does not give this count-based model evidence for "a cat sat".

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:

With enough representative data, these relative frequencies approach the conditional probabilities for the chosen context length. They still inherit the Markov assumption. With finite data, unseen continuations get zero probability, so we need smoothing.

Smoothing: Redistributing Probability

Smoothing reserves some probability mass from observed n-grams for unobserved ones. Methods differ in how much mass they reserve and how they distribute it.

Add-k smoothing (Laplace). 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.

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. A strong classical baseline that changes the lower-order distribution.

Kneser-Ney: A Different Fallback to Back Off

A raw unigram fallback favors words that appear often overall, even if they occur in very few distinct contexts.

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 mostly 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.

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, connecting the estimator to a Bayesian model.

Kneser-Ney provided a strong baseline for neural language models. Bengio et al. (2003) used learned word representations to share information across similar contexts; Mikolov et al. (2010) showed that an RNN language model could outperform strong backoff baselines, including some trained with more data.

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. That is the observed fraction, but it is a fragile estimate: we only saw "cat sat" once.

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.

Use interpolation weights $\lambda_3 = 0.5$, $\lambda_2 = 0.3$, and $\lambda_1 = 0.2$. When the entire trigram context is missing, its distribution is undefined. Drop that component and renormalize the remaining weights to sum to one:

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 3/33 (three occurrences of "on" across 28 words plus five end-of-sentence tokens, matching the code below). So:

The estimate stays positive and the full conditional still sums to one. Simply substituting zero for a missing component without renormalizing would leave half the probability mass unassigned.

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>"]
            # Every component predicts the same vocabulary, including </s>.
            # <s> is context only.
            for w in tokens + ["</s>"]:
                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}")

prob() computes each available distribution and mixes it with weights that sum to one. The trigram gives you specificity when you have data. The unigram keeps the probability positive for words seen somewhere in training. This example uses a fixed vocabulary: an entirely unseen word still has zero probability and would need an unknown-token policy for evaluation. The lambdas control how much you trust each level.

Tune interpolation weights on held-out data. Context-dependent weights and Kneser-Ney continuation probabilities provide alternatives to the fixed weights and raw unigram fallback used here.

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 even it had massive sparsity at the 5-gram level.

"N-grams cannot generalize beyond observed sequences." Smoothing gives unseen n-grams probability through shorter contexts. Neural models can also share information between different words through continuous representations, the topic of word2vec.

"Smoothing is just a hack." Smoothing is doing something principled: it's a form of regularization. Add-k is the posterior predictive estimate under a symmetric Dirichlet prior with concentration $k$ per vocabulary item. Teh (2006) showed how an approximation to a hierarchical Pitman–Yor language model recovers interpolated Kneser–Ney.

What's next

The next post covers word2vec and the embedding revolution: learning continuous word representations from the contexts in which words occur.

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.