4.5.3 Some advanced issues in Good-Turing estimation

Good-Turing estimation assumes that the distribution of each bigram is binomial (Church et al., 1991) and assumes we know $ N_0 $, the number of bigrams we haven't seen. We know this because given a vocabulary size of $ V $, the total number of bigrams is $ V^2 $, hence $ N_0 $ is $ V^2 $ minus all the bigrams we have seen.

There are a number of additional complexities in the use of Good-Turing. For example, we don't just use the raw $N_c$ values in Equation (4.26). This is because the re-estimate $c^*$ for $N_c$ depends on $N_{c+1}$, hence Equation (4.26) is undefined when $N_{c+1} = 0$. Such zeros occur quite often. In our sample problem above, for example, since $N_4 = 0$, how can we compute $N_3?$ One solution to this is called Simple Good-Turing (Gale and Sampson, 1995). In Simple Good-Turing, after we compute the bins $N_c$, but before we compute Equation (4.26) from them, we smooth the $N_c$ counts to replace any zeros in the sequence. The simplest thing is just to replace the value $N_c$ with a value computed from a linear regression which is fit to map $N_c$ to $c$ in log space (see Gale and Sampson (1995) for details):

$$ \log(N_{c})=a+b\log(c) $$

In addition, in practice, the discounted estimate $ c^{*} $ is not used for all counts c. Large counts (where c > k for some threshold k) are assumed to be reliable. Katz (1987) suggests setting k at 5. Thus we define

$$ c^{*}=c for c>k $$

The correct equation for $ c^{*} $ when some k is introduced (from Katz (1987)) is:

$$ c^{*}=\frac{(c+1)\frac{N_{c+1}}{N_{c}}-c\frac{(k+1)N_{k+1}}{N_{1}}}{1-\frac{(k+1)N_{k+1}}{N_{1}}},\mathrm{~f o r~}1\leq c\leq k. $$

Second, with Good-Turing discounting as with any other, it is usual to treat N-grams with low raw counts (especially counts of 1) as if the count were 0, i.e., to apply Good-Turing discounting to these as if they were unseen.

It turns out that Good-Turing discounting is not used by itself in discounting N-grams; it is only used in combination with the backoff and interpolation algorithms described in the next sections.

4.6 INTERPOLATION

The discounting we have been discussing so far can help solve the problem of zero frequency $ N $-grams. But there is an additional source of knowledge we can draw on. If we are trying to compute $ P(w_n|w_{n-1}w_{n-2}) $, but we have no examples of a particular trigram $ w_{n-2}w_{n-1}w_n $, we can instead estimate its probability by using the bigram probability $ P(w_n|w_{n-1}) $. Similarly, if we don’t have counts to compute $ P(w_n|w_{n-1}) $, we can look to the unigram $ P(w_n) $.

There are two ways to use this N-gram "hierarchy", backoff and interpolation. In backoff, if we have non-zero trigram counts, we rely solely on the trigram counts. We only "back off" to a lower order N-gram if we have zero evidence for a higher-order N-gram. By contrast, in interpolation, we always mix the probability estimates from all the N-gram estimators, i.e., we do a weighted interpolation of trigram, bigram, and unigram counts.

In simple linear interpolation, we combine different order $N$-grams by linearly interpolating all the models. Thus we estimate the trigram probability $P(w_n|w_{n-1}w_{n-2})$ by mixing together the unigram, bigram, and trigram probabilities, each weighted by a $\lambda$:

$$ \begin{aligned}\hat{P}(w_{n}|w_{n-1}w_{n-2})=&\lambda_{1}P(w_{n}|w_{n-1}w_{n-2})\\&+\lambda_{2}P(w_{n}|w_{n-1})\\&+\lambda_{3}P(w_{n})\end{aligned} $$

such that the $ \lambda s $ sum to 1:

$$ \sum_{i}\lambda_{i}=1 $$

In a slightly more sophisticated version of linear interpolation, each $ \lambda $ weight is computed in a more sophisticated way, by conditioning on the context. This way if we have particularly accurate counts for a particular bigram, we assume that the counts of the trigrams based on this bigram will be more trustworthy, so we can make the $ \lambda $s for those trigrams higher and thus give that trigram more weight in the interpolation. Equation (4.34) shows the equation for interpolation with context-conditioned weights:

$$ \begin{aligned}\hat{P}(w_{n}|w_{n-2}w_{n-1})=&\lambda_{1}(w_{n-2}^{n-1})P(w_{n}|w_{n-2}w_{n-1})\\&+\lambda_{2}(w_{n-2}^{n-1})P(w_{n}|w_{n-1})\\&+\lambda_{3}(w_{n-2}^{n-1})P(w_{n})\end{aligned} $$

How are these $\lambda$ values set? Both the simple interpolation and conditional interpolation $\lambda s$ are learned from a held-out corpus. Recall from Sec. 4.3 that a held-out corpus is an additional training corpus that we use not to set the $N$-gram counts, but to set other parameters. In this case we can use such data to set the $\lambda$ values. We can do this by choosing the $\lambda$ values which maximize the likelihood of the held-out corpus. That is, we fix the $N$-gram probabilities and then search for the $\lambda$ values that when plugged into Equation (4.32) give us the highest probability of the held-out set, There are various ways to find this optimal set of $\lambda s$. One way is to use the EM algorithm to be defined in Ch. 6, which is an iterative learning algorithm that converges on locally optimal $\lambda s$ (Baum, 1972; Dempster et al., 1977; Jelinek and Mercer, 1980).

4.7 BACKOFF

While simple interpolation is indeed simple to understand and implement, it turns out that there are a number of better algorithms. One of these is backoff $ N $-gram modeling. The version of backoff that we describe uses Good-Turing discounting as well. It was introduced by Katz (1987), hence this kind of backoff with discounting is also called Katz backoff. In a Katz backoff $ N $-gram model, if the $ N $-gram we need has zero counts, we approximate it by backing off to the $ (N-1) $-gram. We continue backing off until we reach a history that has some counts:

$$ P_{\mathrm{k a t z}}(w_{n}|w_{n-N+1}^{n-1})=\left\{\begin{array}{l l}{P^{*}(w_{n}|w_{n-N+1}^{n-1}),}&{\quad\mathrm{i f}C(w_{n-N+1}^{n})>0}\\ {\alpha(w_{n-N+1}^{n-1})P_{\mathrm{k a t z}}(w_{n}|w_{n-N+2}^{n-1}),}&{\quad\mathrm{o t h e r w i s e}.}\end{array}\right. $$

Equation (4.35) shows that the Katz backoff probability for an $N$-gram just relies on the (discounted) probability $P^{*}$ if we've seen this $N$-gram before (i.e. if we have nonzero counts). Otherwise, we recursively back off to the Katz probability for the shorter-history $(N-1)$-gram. We'll define the discounted probability $P^{*}$, the normalizing factor $\alpha$, and other details about dealing with zero counts in Sec. 4.7.1. Based on these details, the trigram version of backoff might be represented as follows (where for pedagogical clarity, since it's easy to confuse the indices $w_i, w_{i-1}$ and so on, we refer to the three words in a sequence as $x, y, z$ in that order):

$$ P_{\mathrm{k a t z}}(z|x,y)\;=\;\left\{\begin{array}{l l}{P^{*}(z|x,y),\quad}&{\mathrm{i f}\;C(x,y,z)>0}\\ {\alpha(x,y)P_{\mathrm{k a t z}}(z|y),\quad}&{\mathrm{e l s e}\;\mathrm{i f}\;C(x,y)>0}\\ {P^{*}(z),\quad}&{\mathrm{o t h e r w i s e}.}\end{array}\right. $$

$$ P_{\mathrm{k a t z}}(z|y)=\left\{\begin{aligned}&P^{*}(z|y),\quad&if C(y,z)>0\\&\alpha(y)P^{*}(z),\quad&otherwise.\end{aligned}\right. $$

Katz backoff incorporates discounting as an integral part of the algorithm. Our previous discussions of discounting showed how a method like Good-Turing could be

used to assign probability mass to unseen events. For simplicity, we assumed that these unseen events were all equally probable, and so the probability mass got distributed evenly among all unseen events. Katz backoff gives us a better way to distribute the probability mass among unseen trigram events, by relying on information from unigrams and bigrams. We use discounting to tell us how much total probability mass to set aside for all the events we haven't seen and backoff to tell us how to distribute this probability.

Discounting is implemented by using discounted probabilities $ P^{*}(\cdot) $ rather than MLE probabilities $ P(\cdot) $ in Equation (4.35) and Equation (4.37).

Why do we need discounts and $ \alpha $ values in Equation (4.35) and Equation (4.37)? Why couldn't we just have three sets of MLE probabilities without weights? Because without discounts and $ \alpha $ weights, the result of the equation would not be a true probability! The MLE estimates of $ P(w_n|w_{n-N+1}^{n-1}) $ are true probabilities; if we sum the probability of all $ w_i $ over a given N-gram context, we should get 1:

$$ \sum_{i}P(w_{i}|w_{j}w_{k})=1 $$

But if that is the case, if we use MLE probabilities but back off to a lower order model when the MLE probability is zero, we would be adding extra probability mass into the equation, and the total probability of a word would be greater than 1!

Thus any backoff language model must also be discounted. The $ P^{*} $ is used to discount the MLE probabilities to save some probability mass for the lower order N-grams. The $ \alpha $ is used to ensure that the probability mass from all the lower order N-grams sums up to exactly the amount that we saved by discounting the higher-order N-grams. We define $ P^{*} $ as the discounted ( $ c^{*} $) estimate of the conditional probability of an N-gram, (and save P for MLE probabilities):

$$ P^{*}(w_{n}|w_{n-N+1}^{n-1})=\frac{c^{*}(w_{n-N+1}^{n})}{c(w_{n-N+1}^{n-1})} $$

Because on average the (discounted) $ c^{*} $ will be less than c, this probability $ P^{*} $ will be slightly less than the MLE estimate, which is

$$ c\binom{w^{n}_{n-N+1}}{}\over c\binom{n-1}{n-N+1} $$

This will leave some probability mass for the lower order N-grams which is then distributed by the $ \alpha $ weights; details of computing $ \alpha $ are in Sec. 4.7.1. Fig. 4.9 shows the Katz backoff bigram probabilities for our 8 sample words, computed from the BeRP corpus using the SRILM toolkit.