4.5.2 Good-Turing Discounting

There are a number of much better discounting algorithms that are only slightly more complex than add-one smoothing. In this section we introduce one of them, known as Good-Turing smoothing.

The intuition of a number of discounting algorithms (Good Turing, Witten-Bell discounting, and Kneyser-Ney smoothing) is to use the count of things you've seen once to help estimate the count of things you've never seen. The Good-Turing algorithm was first described by Good (1953), who credits Turing with the original idea. The basic insight of Good-Turing smoothing is to re-estimate the amount of probability mass to assign to N-grams with zero counts by looking at the number of N-grams that occurred one time. A word or N-gram (or any event) that occurs once is called a singleton, or a hapax legomenon. The Good-Turing intuition is to use the frequency of singletons as a re-estimate of the frequency of zero-count bigrams.

Let's formalize the algorithm. The Good-Turing algorithm is based on computing $ N_c $, the number of N-grams that occur c times. We refer to the number of N-grams that occur c times as the frequency of frequency c. So applying the idea to smoothing the joint probability of bigrams, $ N_0 $ is the number of bigrams with count 0, $ N_1 $ the number of bigrams with count 1 (singletons), and so on. We can think of each of the $ N_c $ as a bin which stores the number of different N-grams that occur in the training set with that frequency c. More formally:

$$ N_{c}=\sum_{x:count(x)=c}1 $$

The MLE count for $ N_{c} $ is c. The Good-Turing estimate replaces this with a smoothed count $ c^{*} $, as a function of $ N_{c+1} $:

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

We can use (Equation (4.26)) to replace the MLE counts for all the bins $N_1$, $N_2$, and so on. Instead of using this equation directly to re-estimate the smoothed count $c^*$ for $N_0$, we use the following equation for the probability $P_{GT}^*$ for things that had zero count $N_0$, or what we might call the missing mass:

原书第 112 页

$$ P_{GT}^{*}(\mathrm{t h i n g s}\mathrm{w i t h}\mathrm{f r e q u e n c y z e r o i n t r a i n i n g})=\frac{N_{1}}{N} $$

Here $N_{1}$ is the count of items in bin 1, i.e. that were seen once in training, and $N$ is the total number of items we have seen in training. Equation (4.27) thus gives the probability that the $N+1$st bigram we see will be one that we never saw in training. Showing that (Equation (4.27)) follows from (Equation (4.26)) is left as Exercise 4.8 for the reader.

The Good-Turing method was first proposed for estimating the populations of animal species. Let's consider an illustrative example from this domain created by Joshua Goodman and Stanley Chen. Suppose we are fishing in a lake with 8 species (bass, carp, catfish, eel, perch, salmon, trout, whitefish) and we have seen 6 species with the following counts: 10 carp, 3 perch, 2 whitefish, 1 trout, 1 salmon, and 1 eel (so we haven't yet seen the catfish or bass). What is the probability that the next fish we catch will be a new species, i.e., one that had a zero frequency in our training set, i.e., in this case either a catfish or a bass?

The MLE count $c$ of a hitherto-unseen species (bass or catfish) is 0. But Equation (4.27) tells us that the probability of a new fish being one of these unseen species is $\frac{3}{18}$, since $N_{1}$ is 3 and $N$ is 18:

$$ P_{GT}^{*}(\mathrm{things~with~frequency~zero~in~training})=\frac{N_{1}}{N}=\frac{3}{18} $$

What is the probability that the next fish will be another trout? The MLE count for trout is 1, so the MLE estimated probability is $ \frac{1}{18} $. But the Good-Turing estimate must be lower, since we just stole $ \frac{3}{18} $ of our probability mass to use on unseen events! We'll need to discount the MLE probabilities for trout, perch, carp, etc. In summary, the revised counts $ c^* $ and Good-Turing smoothed probabilities $ p_{\text{GT}}^{*} $ for species with count 0 (like bass or catfish) or count 1 (like trout, salmon, or eel) are as follows:

| | unseen (bass or catfish) | trout |

| --- | --- | --- |

| c | 0 | 1 |

| MLE p | $ p = \frac{0}{18} = 0 $ | $ \frac{1}{18} $ |

| $ c^{*} $ | | $ c^{*}(\text{trout}) = 2 \times \frac{N_2}{N_1} = 2 \times \frac{1}{3} = .67 $ |

| GT $ p_{GT}^{*} $ | $ p_{GT}^{*}(\text{unseen}) = \frac{N_1}{N} = \frac{3}{18} = .17 $ | $ p_{GT}^{*}(\text{trout}) = \frac{67}{18} = \frac{1}{27} = .037 $ |

Note that the revised count $ c^* $ for eel was discounted from $ c = 1.0 $ to $ c^* = .67 $, (thus leaving some probability mass $ p_{\mathrm{GT}}^{*} $ (unseen) = $ \frac{3}{18} = .17 $ for the catfish and bass). And since we know there were 2 unknown species, the probability of the next fish being specifically a catfish is $ p_{\mathrm{GT}}^{*} $ (catfish) = $ \frac{1}{2} \times \frac{3}{18} = .085 $.

Fig. 4.8 gives two examples of the application of Good-Turing discounting to big-gram grammars, one on the BeRP corpus of 9332 sentences, and a larger example computed from 22 million words from the Associated Press (AP) newswire by Church and Gale (1991). For both examples the first column shows the count c, i.e., the number of observed instances of a bigram. The second column shows the number of bigrams that

原书第 113 页

had this count. Thus 449,721 of the AP bigrams have a count of 2. The third column shows $ c^{*} $, the Good-Turing re-estimation of the count.

| --- | --- | --- | --- | --- | --- |

| c (MLE) | $ N_c $ | c $ ^{*} $ (GT) | c (MLE) | $ N_c $ | c $ ^{*} $ (GT) |

| 0 | 74,671,100,000 | 0.0000270 | 0 | 2,081,496 | 0.002553 |

| 1 | 2,018,046 | 0.446 | 1 | 5315 | 0.533960 |

| 2 | 449,721 | 1.26 | 2 | 1419 | 1.357294 |

| 3 | 188,933 | 2.24 | 3 | 642 | 2.373832 |

| 4 | 105,668 | 3.24 | 4 | 381 | 4.081365 |

| 5 | 68,379 | 4.22 | 5 | 311 | 3.781350 |

| 6 | 48,190 | 5.19 | 6 | 196 | 4.500000 |

Figure 4.8 Bigram “frequencies of frequencies” and Good-Turing re-estimations for the 22 million AP bigrams from Church and Gale (1991) and from the Berkeley Restaurant corpus of 9332 sentences.