4.9.1 Advanced Smoothing Methods: Kneser-Ney Smoothing

In this section we give a brief introduction to the most commonly used modern N-gram smoothing method, the interpolated Kneser-Ney algorithm.

Kneser-Ney has its roots in a discounting method called absolute discounting. Absolute discounting is a much better method of computing a revised count $ c^{*} $ than the Good-Turing discount formula we saw in Equation (4.26), based on frequencies-of-frequencies. To get the intuition, let's revisit the Good-Turing estimates of the bigram $ c^{*} $ extended from Fig. 4.8 and reformatted below:

The astute reader may have noticed that except for the re-estimated counts for 0 and 1, all the other re-estimated counts $ c^{*} $ could be estimated pretty well by just subtracting 0.75 from the MLE count $ c! $ Absolute discounting formalizes this intuition, by subtracting a fixed (absolute) discount $ d $ from each count. The intuition is that we have good estimates already for the high counts, and a small discount $ d $ won't affect them much. It will mainly modify the smaller counts, for which we don't necessarily trust the estimate anyway. The equation for absolute discounting applied to bigrams (assuming a proper coefficient $ \alpha $ on the backoff to make everything sum to one) is:

$$ P_{\mathrm{a b s o l u t e}}(w_{i}|w_{i-1})=\left\{\begin{array}{l l}\frac{C(w_{i-1}w_{i})-\mathbf{D}}{C(w_{i-1})},&\text{if}C(w_{i-1}w_{i})>0\\ \alpha(w_{i})P_{\mathrm{a b s o l u t e}}(w_{i}),&\text{otherwise.}\end{array}\right. $$

In practice, we might also want to keep distinct discount values d for the 0 and 1 counts.

Kneser-Ney discounting (Kneser and Ney, 1995) augments absolute discounting with a more sophisticated way to handle the backoff distribution. Consider the job of predicting the next word in this sentence, assuming we are backing off to a unigram model:

I can't see without my reading ___.

The word glasses seems much more likely to follow here than the word Francisco. But Francisco is in fact more common, so a unigram model will prefer it to glasses. We would like to capture the intuition that although Francisco is frequent, it is only frequent after the word San, i.e. in the phrase San Francisco. The word glasses has a much wider distribution.

Thus instead of backing off to the unigram MLE count (the number of times the word w has been seen), we want to use a completely different backoff distribution! We want a heuristic that more accurately estimates the number of times we might expect to see word w in a new unseen context. The Kneser-Ney intuition is to base our estimate on the number of different contexts word w has appeared in. Words that have appeared in more contexts are more likely to appear in some new context as well. We can express this new backoff probability, the “continuation probability”, as follows:

$$ P_{\mathrm{C O N T I N U A T I O N}}(w_{i})=\frac{\left|\left\{w_{i-1}:C(w_{i-1}w_{i})>0\right\}\right|}{\sum_{w_{i}}\left|\left\{w_{i-1}:C(w_{i-1}w_{i})>0\right\}\right|} $$

The Kneser-Ney backoff intuition can be formalized as follows (again assuming a proper coefficient $ \alpha $ on the backoff to make everything sum to one):

$$ P_{\mathrm{K N}}(w_{i}|w_{i-1})=\left\{\begin{array}{l l}\frac{C(w_{i-1}w_{i})-\mathbf{D}}{C(w_{i-1})},&\text{if}C(w_{i-1}w_{i})>0\\ \alpha(w_{i})\frac{|\{w_{i-1}:C(w_{i-1}w_{i})>0\}|}{\sum_{w_{i}}|\{w_{i-1}:C(w_{i-1}w_{i})>0\}|}&\text{otherwise.}\end{array}\right. $$

Finally, it turns out to be better to use an interpolated rather than backoff form of Kneser-Ney. While Sec. 4.6 showed that linear interpolation is not as successful

as Katz backoff, it turns out that more powerful interpolated models, such as interpolated Kneser-Ney, work better than their backoff version. Interpolated Kneser-Ney discounting can be computed with an equation like the following (omitting the computation of $ \beta $):

$$ P_{\mathrm{K N}}(w_{i}|w_{i-1})=\frac{C(w_{i-1}w_{i})-\mathbf{D}}{C(w_{i-1})}+\beta(w_{i})\frac{\left|\left\{w_{i-1}:C(w_{i-1}w_{i})>0\right\}\right|}{\sum_{w_{i}}\left|\left\{w_{i-1}:C(w_{i-1}w_{i})>0\right\}\right|} $$

A final practical note: it turns out that any interpolation model can be represented as a backoff model, hence stored in ARPA backoff format. We simply do the interpolation when we build the model, so the 'bigram' probability stored in the backoff format is really 'bigram already interpolated with unigram'.