Discounting, Backoff and Interpolation in NLP N-Gram

N-Gram

The model of n-gram is to leverage the previous (n-1) words to predict the next word. Such assumption that the probability distribution of the next word is only dependent of its previous (n-1) words is called the Markov Assumption. Starting from the simplest, if the probability is only dependent of itself, the model is called a "Uni-Gram". Then `P(w_i) = \frac{C(w_i)}{N}`. If the probability is conditioned on the previous word, the model is called "Bi-Gram". The probability is estimated by the frequency of the particular bi-gram out of all possible bi-grams given the previous word.

`p(w_i|w_{i-1}) = \frac {C(w_{i-1}w_i)}{\sum_w C(w_{i-1}w)}`

The number of bi-grams starting with the previous word is also the count of the previous word.

`p(w_i|w_{i-1}) = \frac {C(w_{i-1}w_i)}{C(w_{i-1})}`

Generalizing to n-grams,

`p(w_i|w_{i-n+1:i-1}) = \frac {C(w_{i-n+1:i-1}w_i)}{C(w_{i-n+1:i-1})}`

There may be a lot of n-grams that never appear in the corpus, and the probabilities computed by the above model would be zero, which is not the real case. Thus the technique of smoothing is adopted to assign some probability mass to zero counts.

Add-One Smoothing

The most straight forward one is the Add-one Smoothing, also known as Laplace Smoothing. Simply add 1 count to every n-gram and increase the total count of n-grams by the size of the vocabulary. For uni-grams:

`P^\star(w_i) = \frac{C(w_i)}{\sum_i(C(w_i))} = \frac{C(w_i)+1}{\sum_i(C(w_i)+1)} = \frac{C(w_i)+1}{N+V}`

For bi-grams:

`p^\star(w_i|w_{i-1}) = \frac {C(w_{i-1}w_i) + 1}{\sum_{w}(C(w_{i-1}w)+1)} = \frac {C(w_{i-1}w_i) + 1}{C(w_{i-1}) + V}`

One problem of Add-one Smoothing is that for those n-grams with non-zero but small counts, their probability changes drastically. Say in a corpus with a vocabulary of 1000 words, the bi-gram "dog eats" appears once, and the word "dog" appears twice. The initial `P(eats|dog) = \frac{1}{2}`, but the smoothed `P(eats|dog) = \frac{1+1}{2+1000}`.
The extension of Add-one Smoothing is Add-k Smoothing, and is computed as:

`P_{Add-k}^\star(w_i|w_{i-1})=\frac{C(w_{i-1}w_i)+k}{C(w_{i-1})+kV}`

Discount v.s. Discounting v.s. Smoothing

Discounting: The term Discounting is just a parallel perspective to look at smoothing. Because smoothing is also a kind of discount on the non-zero word counts. One kind of smoothing method we'll cover later is called Absolute-Discounting Smoothing. Thus discounting generally refers to the samething as smoothing.
Discount: Discount, on the other hand, is a ratio that describes how much the counts have changed after the smoothing. Still take Add-One Smoothing as an example. Say there are `N` words in the corpus and `V` tokens in the vocabulary. The count of each token in the vocabulary is `C(w_i)`, and the probability of each token is `P(w_i) = \frac{C(w_i)}{N}`. Define the count of words in regard of unchanged size of the corpus after Add-One Smoothing as adjusted counts or effective counts `C^\star(w_i)`. If the smoothed counts were to remain the same proportion, we would have `N = \sum_{i=1}^VC(w_i) = \sum_{i=1}^VC^\star(w_i)` and that `P(w_i) = P^\star(w_i)`, i.e. `\frac{C(w_i)}{N} = \frac{C(w_i)+1}{N+V}`.

`C^\star(w_i) = \frac{(C(w_i)+1)N}{N+V}`

That is to say, after smoothing, the current count of the word `w_i` counts as appearing `C^\star(w_i)` times in the original corpus.
Now we finally the fine the ratio of discount:

`d_i = \frac{C^\star(w_i)}{C(w_i)} = \frac{(C(w_i)+1)N}{C(w_i)(N+V)}`

That is to say, the count of the word `w_i` is now in `d_i` proportion of its original counts.
Similarly, for bi-grams, we have:

`C^\star(w_{i-1}w_i) = \frac{(C(w_{i-1}w_i)+1)N}{C(w_{i-1})+V}` `d_i = \frac{(C(w_{i-1}w_i)+1)N}{C(w_i)(C(w_{i-1})+V)}`

Good-Turing Smoothing

Unlike Add-One Smoothing who smooths the probability by directly adding one count, Good-Turing Smoothing re-distributes the probability mass based on the frequency of n-grams. Say there are `N` words in the corpus. The number of words appearing `c` times is `n_c`. Then `N = \sum_{c=1}^\inftyn_c*c`. Now we set the smoothed frequency to be `c^\star`, given the total amount of words unchanged, we have

`\sum_{c^\star=1}^\inftyn_c*c^\star=\sum_{c=1}^\inftyn_{c+1}*(c+1)`

That gives us `c^\star = \frac{n_{c+1}*(c+1)}{n_c}` and the smoothed probability being `P_c^\star = \frac{c^\star}{N} = \frac{n_{c+1}*(c+1)}{n_c*N}`.
For example, for those words with zero probability, the count `c = 0`, and there are 10 000 such words, i.e. `n_0 = 10000`. Say given the number of words appearing once `n_1 = 2000`, we can compute `c^\star = (0+1)\times 2000 / 10000 = 0.2`.
Notice that for a word appearing, say 10 times, in the corpus, the statistical properties of this word tend to be more accurate and smoothing would, to some extent, diminish such merit. Thus, in many cases, we only consider do smoothing within a threshold, i.e. `c^\star = \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}}, 1 \leq c \leq k`.

Backoff: Katz Smoothing

上面的方法都是解决零频率 N 元语法问题，此外还可以通过利用对应的 N-1 元或更低元的语法来计算。主要有两种方法：Backoff 和 Interpolation，Backoff 中，只有当阶数较高的 N 元语法中存在零计数时，才把阶数较高的 N 元语法降为阶数较低的 N 元语法。

1987 年提出
$\hat {P}(w_i|w_{i-2}w_{i-1}) = {P(w_i|w_{i-2}w_{i-1}), c(w_{i-2}w_{i-1}w_i) > 0}$
$\hat {P}(w_i|w_{i-2}w_{i-1}) = {\alpha_1 P(w_i|w_{i-1}), c(w_{i-2}w_{i-1}w_i) = 0\ and\ c(w_{i-1}w_i) > 0}$
$\hat {P}(w_i|w_{i-2}w_{i-1}) = {\alpha_2 P(w_i), other}$
α 的目的是使等式的结果为真正的概率，保证： $\sum_{i,j} P(w_n|w_iw_j) = 1$

Interpolation: Jelinek-Mercer Smoothing

1980 年提出，使用线性插值把不同阶的语法结合起来，不同阶通过权值加权
$\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)},\ \sum_i \lambda_i = 1$
实际不仅仅只为三元语法训练三个 λ，还把每一个 λ 看成上下文的函数。

Absolute Discounting

Kneser-Ney Smoothing

另外还有以下两种表现不错的平滑算法，可以参考：LM

Absolute Discounting: Discounting of the counts for frequent N-grams is necessary to save some probability mass for the smoothing algorithm to distribute to the unseen N-grams.
Kneser-Ney Smoothing: Augments absolute discounting with a more sophisticated way to handle the lower-order unigram distribution.

对于大语料，可以使用非常简单的 Stupid Backoff：放弃了计算真实的概率分布，高阶没有折扣概率，如果高阶 N-gram 的计数为零，只需退回到低阶 N-gram，使用固定权重，可以参考：LM。

Ngram 可以用于处理上下文有关的错误，基本思想是：对于句子中的每个单词生成它的一切可能的错误拼写，或者是只包括排版印刷错误而造成的错拼，或者是也包括同音词造成的错拼，然后选出使该句子具有最高先验概率的拼写。此外还有 Bayes 分类法、Bayes 分类法与三元语法结合、判定表方法、基于转换的学习方法、潜在语义分析法、筛选算法（效果最好）。

小结

N 元语法

一个单词的概率只依赖于它前面一个单词的这种假设叫作 Markov 假设，这样的模型叫 Bi-gram，即二元语法模型，也叫一阶 Markov 模型。
N 增加时，精确度相应增加，同时生成句子的局限性增加（可选的下个词减少）；严重依赖于语料库。

数据平滑

Add-One (Add-α)：简单，未登录词或低概率词会被给予过高的概率。
Witten-Bell：看一个零概率 N 元语法的概率可以用首次看一个 N 元语法的概率模拟。
Good-Turing：可以复杂，但简单修改也能工作的很好；仍然没有区分不同类型的罕见事件。
Katz Smoothing (Backoff)/Jelinek-Mercer Smoothing (Deleted Interpolation)：利用对应的 N-1 元或更低元的语法（结合不同阶）来计算；前者只有当阶数较高的 N 元语法中存在零计数时，才把阶数较高的 N 元语法降为阶数较低的 N 元语法。。
Absolute Discounting/Kneser-Ney Smoothing：前者对 N 元语法计数进行绝对折扣；后者假设过去在更多情境中出现的词语更有可能出现在某些新的语境中。

具体表现

Jelinek-Mercer 在小型训练集上表现更好； Katz 在大型训练集上表现更好。
Katz 平滑对大数量的 N-gram 表现良好； Kneser-Ney 最适合小数量。
在低（非零）计数的 Ngram 上，Jelinek-Mercer 优于 Katz。
Absolute Discounting 优于 Linear Discounting。
应用场景
Applications like Text Categorization Add one smoothing can be used.
State of the art technique Kneser-Ney Smoothing: both interpolation and backoff versions can be used.
Very large training set like web data like Stupid Backoff are more efficient.

这章虽然是非常简单的 Ngram 语法，但 Smoothing 的各种算法却非常有意思，从中可以深刻地感受到对一个简单问题处理的智慧，我想这可能也是算法的魅力吧。关于 Witten-Bell Smoothing 找了好久才找到一个容易理解的资料（参考文献 2），更多关于 N-gram 和 Smoothing 可以参阅：LM

参考文献：

Computational Linguistics 加一平滑的例子不错。
Foundations of Artificial Intelligence · Advanced AI Techniques - Lectures 参考了 7b 的 Witten-Bell 平滑。
20050421-smoothing-tutorial.pdf 和 scribe6.pdf 比较全面介绍了各种平滑算法的思想。
All4NLP/Ngram at master · hscspring/All4NLP 有两个不错的 PPT。

还有几个可以的课件：