Smoothing Techniques › The Zero Probability Problem

Before diving into solutions, let's develop a crisp understanding of why this problem is so severe and how pervasive it is.

Suppose you train a bigram model on 1 million words of newspaper text. Your model has learned $P(\text{"president"} \mid \text{"the"})$, $P(\text{"company"} \mid \text{"the"})$, and thousands of other bigrams. Now you want to evaluate the probability of a sentence containing the bigram "the aardvark." Unless your training corpus happened to discuss aardvarks, this bigram has count zero. MLE gives it probability zero.

The formal quantity at stake is the MLE bigram probability. To estimate how likely word $w_i$ is given the preceding word $w_{i-1}$, MLE computes:

$$P_{\text{MLE}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}$$

where:

• $C(w_{i-1}, w_i)$: the count of the bigram $w_{i-1} w_i$ in the training corpus
• $C(w_{i-1})$: the count of the word $w_{i-1}$ in the training corpus (the context)

When $C(w_{i-1}, w_i) = 0$, the probability is zero, regardless of how large the corpus is.

How bad is this in practice? A vocabulary of $|V|$ words produces $|V|^2$ possible bigrams and $|V|^3$ possible trigrams. For a typical vocabulary of 50,000 words, that's 2.5 billion possible bigrams and 125 trillion possible trigrams. No training corpus of any realistic size will cover more than a tiny fraction of these. Zipf's Law compounds the problem: most words are rare, so most n-grams that do occur in language appear only once or twice even in large corpora. The distribution is extremely heavy-tailed, which means that even after collecting tens of millions of sentences, you'll still encounter enormous numbers of bigrams in real text that never appeared in your training data.

To make this concrete, consider what happens at the level of trigrams. A well-built bigram model might have coverage for most bigrams in common text. But a trigram model trained on even a large corpus will miss the vast majority of possible three-word sequences. This is the curse of dimensionality applied to discrete combinatorial spaces: the number of possible sequences grows exponentially in $n$, but the amount of training data grows only linearly. The mismatch is permanent, no matter how much data you collect.

Smoothing solves this by ensuring every n-gram gets a positive probability. The challenge is doing this in a principled way that doesn't distort the probability distribution too badly. A terrible smoothing method would assign equal probability to all unseen n-grams regardless of how plausible they are. A good one will allocate probability mass in proportion to evidence about how likely each word is to appear in a given context, even if that specific context was never observed.

One important constraint governs any valid smoothing scheme: the probabilities of all possible next words given a context must still sum to 1. This is the fundamental property that makes a conditional probability distribution valid.

If we add probability mass to unseen n-grams, we must subtract an equal amount from the seen ones. This is the "conservation" intuition behind smoothing: probability mass is neither created nor destroyed, only redistributed. The question is how to redistribute it wisely.

Most smoothing methods follow a two-step pattern. First, they apply a discount to reduce the probability assigned to seen n-grams. Second, they distribute the freed-up probability mass to unseen n-grams using some lower-order model as a guide. The choice of how much to discount and where to send the freed mass is what distinguishes one smoothing method from another.