Smoothing Techniques › Good-Turing Estimation

Good-Turing smoothing takes a fundamentally different and more sophisticated approach. Rather than adding a fixed constant, it estimates the true probability of unseen events using information about the frequency of rare events in the data itself.

The key insight, due to Alan Turing and I. J. Good (developed during World War II for cryptanalysis and later published in 1953), is this: the probability of seeing a new n-gram, one you haven't seen before, can be estimated from the fraction of n-grams you saw exactly once. Things you've seen only once are "almost" like things you haven't seen at all, and they give you a statistical foothold for estimating the probability of completely novel events.

This is a remarkably elegant idea. The problem is that you can't directly observe the probability of something you've never seen. But you can observe how many things appeared exactly once, and use that as a proxy for the rate at which you're still missing things.

Define $N_c$ as the frequency of frequency $c$: the number of distinct n-grams that occur exactly $c$ times in the training corpus. This is sometimes called the "count of counts" or "frequency spectrum."

For example:

• $N_0$ = number of possible n-grams never seen (conceptually very large)
• $N_1$ = number of n-grams seen exactly once ("hapax legomena")
• $N_2$ = number of n-grams seen exactly twice
• And so on...

The sequence $N_1, N_2, N_3, \ldots$ reveals the shape of the count distribution. In natural language, this sequence is always steeply decreasing: many n-grams appear once, fewer appear twice, even fewer appear three times, and so on. This follows from Zipf's Law, which we encountered in the chapter on N-gram Language Models.

Good-Turing estimation defines an adjusted count $c^*$ for any n-gram with raw count $c$. The core idea is to replace each raw count $c$ with an estimate that accounts for the systematic underestimation caused by data sparsity:

$$c^* = (c + 1) \frac{N_{c+1}}{N_c}$$

where:

• $c$: the raw count of the n-gram
• $c^*$: the Good-Turing adjusted count (what the count "should" be given the shape of the distribution)
• $N_c$: the number of distinct n-grams with raw count exactly $c$
• $N_{c+1}$: the number of distinct n-grams with raw count exactly $c + 1$

The formula says: if you want to estimate the "true" probability of n-grams seen $c$ times, look at how many n-grams were seen $c+1$ times. The ratio $N_{c+1} / N_c$ tells you about the shape of the count distribution.

Think of it this way. Suppose you collect a new independent sample of the same text distribution. Some of the n-grams you never saw in the original corpus will appear in this new sample, and some of those n-grams will appear exactly once. The fraction of the original probability mass coming from never-seen events is approximately $N_1 / N$, where $N$ is the total number of tokens. This gives you a foothold for estimating the total probability mass that belongs to the "unseen" category.

More generally, the adjusted count $c^*$ for n-grams with raw count $c$ adjusts upward when $N_{c+1}$ is large relative to $N_c$ (suggesting there are many n-grams with count $c$ that, in another sample, would have appeared $c+1$ times) and adjusts downward when $N_{c+1}$ is small relative to $N_c$.

For the total probability of unseen n-grams (count = 0), Good-Turing gives a direct estimate: it should equal the fraction of tokens that were singletons. Formally:

$$P_{\text{GT}}(\text{unseen}) = \frac{N_1}{N}$$

where:

• $N_1$: the number of distinct n-grams seen exactly once
• $N$: the total number of tokens in the training corpus

This is the fraction of the probability mass assigned to all unseen events collectively. We then divide this evenly among all unseen n-grams, giving each unseen n-gram a probability of $N_1 / (N \cdot N_0)$.

The formula has a beautiful consistency property: you can verify that the adjusted counts, when summed and normalized, produce a valid probability distribution. The total probability mass remains 1.

Good-Turing estimation has several practical limitations that arise when you try to apply it to real data.

The most significant limitation is that the ratio $N_{c+1}/N_c$ becomes unreliable for large values of $c$. When $c$ is large (say, 20 or more), $N_c$ and $N_{c+1}$ may both be very small integers, making the ratio noisy. If $N_5 = 3$ and $N_6 = 1$, then $N_6/N_5 = 1/3$, which might just be random fluctuation rather than a meaningful signal. In practice, Good-Turing is only applied for small values of $c$ (typically $c \leq 5$). For larger counts, the MLE estimate is usually used directly because the probability estimates are already reliable enough.

The $N_c$ sequence can also be erratic for intermediate values of $c$. Simple Good-Turing (SGT) addresses this by fitting a smooth curve through the $N_c$ values before using them in the formula. This prevents the ratio from being dominated by random spikes in the frequency-of-frequency distribution.

Good-Turing also has no mechanism for out-of-vocabulary words: it handles unseen n-grams of known words, but if a word itself is novel, you need a separate strategy. For test data containing words never seen in training, even the best smoothing of the n-gram model breaks down unless you have a dedicated unknown-word handling strategy.

Despite these limitations, Good-Turing provides a principled statistical foundation for understanding what "unseen probability" should be, and it motivates more sophisticated methods that build on its frequency-of-frequency insight.