参考
http://www.speech.sri.com/projects/srilm/manpages/ngram-discount.7.html
本篇文章主体部分是对上面页面的翻译。
背景
直接用极大似然估计ngram概率，会出现测试集中很多Ngram在训练集中没有出现，导致零概率现象。解决办法就是smoothing或者又称为discount。
综述
Ngram 主体部分就是统计(或者说数数)，考虑零概率现象，需要平滑，然后出现了各种各样的平滑算法，都是对下面两个问题的回答：
- "蛋糕"如何切？
- 切出来的"蛋糕"如何分配？
用公式表示就是：
p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)
所有的问题就变成：
- f(a_z)是什么？ 怎么求？
- bow(a_)怎么求？
在开始之前对符号做一下说明：
a_z An N-gram where a is the first word, z is the last word, and "" represents 0 or more words in between.
p(a_z) The estimated conditional probability of the nth word z given the first n-1 words (a) of an N-gram.
a_ The n-1 word prefix of the N-gram a_z. NGram历史
_z The n-1 word suffix of the N-gram a_z. NGram backoff后的(N-1) gram，去掉最远的那个词。
c(a_z) The count of N-gram a_z in the training data.
n(*_z) The number of unique N-grams that match a given pattern. * represents a wildcard matching a single word.
n[1] The number of unique N-grams with count = 1.
主要公式
- 极大似然公式：
(1) p(a_z) = c(a_z)/c(a_)
- 零概率问题，需要数据平滑，对上面公式的修正：
(2) p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)
所有的概率计算都是利用上面的那个公式，绝大多数算法的不同点就在于f(a_z)的表示和计算。
- 假设f(a_z)我们已知了，那剩下的所有问题就是计算历史词的backoff值：bow(a_)
计算依据：概率规范性，也就是说对于已知的历史词，其后跟所有词的概率值之和=1
(3) Sum_Z p(a_z) = 1
Sum_Z1 f(a_z) + Sum_Z0 bow(a_) p(_z) = 1
bow(a_) = (1 - Sum_Z1 f(a_z)) / Sum_Z0 p(_z)
= (1 - Sum_Z1 f(a_z)) / (1 - Sum_Z1 p(_z))
= (1 - Sum_Z1 f(a_z)) / (1 - Sum_Z1 f(_z))
其中：
Z： the set of all words in the vocabulary 词典中所有词的集合
Z0：the set of all words with c(a_z) = 0 训练集中历史词a_后没有出现的词集合
Z1：the set of all words with c(a_z) > 0 训练集中历史词a_后出现了的词集合。
另外，当c(a_) = 0时，bow(a_)=1,也就是直接用低阶N-1 gram概率来代表Ngram概率。
- backoff方式概率计算如上，如果是interpolate方式，即使c(a_z)>0, p(a_z)计算也会用到低阶ngram信息，用公式表示如下：
(4) p(a_z) = g(a_z) + bow(a_) p(_z)
- 对应的bow(a_)计算公式如下：
(5) Sum_Z p(a_z) = 1
Sum_Z1 g(a_z) + Sum_Z bow(a_) p(_z) = 1
bow(a_) = 1 - Sum_Z1 g(a_z)
- backoff和interpolate 可以统一起来。
将f(a_z)表示成以下形式：
(6) f(a_z) = g(a_z) + bow(a_) p(_z)
backoff和interpolate概率计算就统一成下面的公式：
p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)
示例
bow(a_)计算已经在上面说明，接下来就是计算f(a_z)、f(_z)、以及interpolate方式中的g(a_z)
cdiscount D
f(a_z) = (c(a_z) - D) / c(a_)
g(a_z) = max(0, c(a_z) - D) / c(a_)
D = n1 / (n1 + 2*n2)kndiscount and ukndiscount
backoff方式
f(a_z) = (c(a_z) - D0) / c(a_) ;; for highest order N-grams
f(_z) = (n(*_z) - D1) / n(*_*) ;; for lower order N-grams
interpolate方式
Let Z1 be the set {z: c(a_z) > 0}. For highest order N-grams we have:
g(a_z) = max(0, c(a_z) - D) / c(a_)
bow(a_) = 1 - Sum_Z1 g(a_z)
= 1 - Sum_Z1 c(a_z) / c(a_) + Sum_Z1 D / c(a_)
= D n(a_*) / c(a_)
Let Z2 be the set {z: n(*_z) > 0}. For lower order N-grams we have:
g(_z) = max(0, n(*_z) - D) / n(*_*)
bow(_) = 1 - Sum_Z2 g(_z)
= 1 - Sum_Z2 n(*_z) / n(*_*) + Sum_Z2 D / n(*_*)
= D n(_*) / n(*_*)
其中ukndiscount 使用同一个discount常数D，计算公式如下：
D = n1 / (n1 + 2*n2)
kndiscount 不同次数的ngram 用不同的discount常数，计算公式如下
Y = n1/(n1+2*n2)
D1 = 1 - 2Y(n2/n1)
D2 = 2 - 3Y(n3/n2)
D3+ = 3 - 4Y(n4/n3)
-
Good-Turing discounting
srilm默认的discount方式。
Good-Turing discount- 当ngram次数大于gtmax，使用极大似然统计。srilm默认是7,公式中的k
- (0, gtmax]之间，p(a_z) = f(a_z)。
- 等于0时，回退，p(a_z) = bow(a_) p(_z)
其中计算公式如下：
只有backoff方式：
p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z) ; Eqn.2
bow(a_) = (1 - Sum_Z1 f(a_z)) / (1 - Sum_Z1 f(_z)) ; Eqn.3
FAQ
backoff 与 interpolate 异同点
ngram count 大于0时，其概率计算，backoff不用低阶信息，interpolate使用低阶信息；
ngram count 等于0时，其概率计算，backoff与interpolate都使用低阶信息。
以下为chen 1999原文：
The key difference between backoff� and interpolated models is that in determining the probability of n-grams with nonzero counts, interpolated models use information from lower-order distributions while backoff models do not. In both backoff and interpolated models, lower-order distributions are used in determining the probability of ngrams with zero counts
