ngram-discount官网:
http://www.speech.sri.com/projects/srilm/manpages/ngram-discount.7.html
ngram-discount – 这里主要说明srilm中实现的平滑算法
NOTATION
a_z 代表以a为起始词，以z为结束词的ngram，其中_代表0个或多个词
p(a_z) 前n-1个词为a_的情况下，第n个词为z的条件概率
a_ n元a_z的前n-1个词构成的前缀
_z n元a_z的后n-1个词构成的后缀
c(a_z) n元a_z在训练语料中出现的次数
n(*_z) 符合*_z这一模式的独立n元数目，“*_z”中‘*’代表通配符
n1,n[1] 出现次数为1的ngram数目
DESCRIPTION
Ngram语言模型主要用于估计前n-1词为a_的情况下，第n个词为z的概率，即概率Pr(z|a_)，为简单起见，一般使用P(a_z)表示。估算概率最直接的方式就是分别在训练集中统计c(a_z)和c(a_)，然后求如下公式，即得到相关概率运算结果：
如上的概率估算方法又称为最大似然估计方法。该方法比较直观易懂，但存在一个不足点就是对于语料中不存在的n元，其概率估算结果将为0。为了避免该情况的发生，可以通过将观察到的ngram一部分概率分布出去，并将这部分概率值分配到未观察到的ngram上。
这种概率重新分配方式即为通常所说的平滑(smoothing)或折扣(discounting)。
大部分平滑算法都可以使用如下公式来表示
p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)
若ngram a_z在训练集中发生了，则直接使用概率，该概率值一般都小于最大似然估计概率值结果，这样留下的一部分概率值可用于训练语料中未覆盖到的n元a_*。不同的平滑算法区别主要在于采用何种折扣方法对最大似然估计结果进行折扣。
应用公式计算概率p(a_z)时，若ngram a_z在训练语料中没有出现，则直接使用低阶概率分布p(_z)，若历史a_在训练语料中没有出现，即c(a_) = 0，这时可以直接使用p(_z)作为当前ngram的概率值，即bow(a_) = 1；否则需要将bow(a_)乘到p(_z)上，以保证概率分布的归一性，即：
Sum_z p(a_z) = 1
假设Z为词典中所有词构成的集合，Z0为词典中所有满足条件c(a_z) = 0的词构成的集合，Z1为词典中所有满足条件c(a_z) > 0的词构成的集合。
当c(a_z) > 0时 , 既要考虑最大似然c（a_z）又要考虑回退c( _z ) 。
把g(a_z)剪掉一部分插值给低元。
比如"我 想 吃 苹果"四元语法：
这句话在训练语料中有一次，计算他的四元概率
根据他的公式推测没有减值D
p（苹果 |我 想 吃）= C（我 想 吃 苹果） /C(我 想 吃)
否则如果没有这句就回退bow（我 想 吃）p（想 吃苹果）
如果bow有值就把高元时的计算值拿来用，否则bow=1
p（ 想 吃 苹果 ）也一样有这个训练数据就最大似然
否则计算他的回退值p（ 想 吃 苹果 ）= bow（ 想 吃 ）p（ 吃 苹果 ）
同理 要是有就计算，没有就回退p（ 吃 苹果 ）= bow（吃）p（苹果）
把高元时得到的回退bow（吃）值拿来使用，p（苹果）= C（苹果）/C(总词数)
但是ngram里面的一元词数也是经过打折之后的，不是实际计数得到的值
还有一点值得注意，比如四元组a b c z 作为后缀的z 个数是由训练语料中的总词数和词典中词数的交集（有些词词典里有,数据里没有,就不会有这个z的四元组 ; 训练数据里有，词典里没有作为<UNK>, 只组成一个四元组 a b c <UNK>）决定的。
-gtnmin表示出现次数小于特定值的gram将会被丢弃，对于所有的平滑算法都一样。默认是所有的1元和2元都会保留，其他阶的count>=2的才会保留。
输入命令时加上这个参数，次数出现一次的也会保留。
不输入这个参数虽然>1才会保留，但是出现一次的值也会计算，只是不出现在lm词表里，而只是把对应的回退值返回给低元。
在f(a_z)计算好的情况下，bow(a_)可以通过如下方式估算得到：
Sum_Z1f(a_z) + Sum_Z0bow(a_)p(_z) = 1
bow(a_) = (1 - Sum_Z1f(a_z)) / Sum_Z0p(_z)
= (1 - Sum_Z1f(a_z)) / (1 - Sum_Z1p(_z))
= (1 - Sum_Z1f(a_z)) / (1 - Sum_Z1f(_z))
上式中分母Sum_Z0 p(_z)代表在历史“_”条件下，所有满足条件c(a_z) = 0的词概率之和，而Z1为词典中所有满足条件c(a_z) > 0的词构成的集合，因此存在如下的关系
Sum_Z0 p(_z) + Sum_Z1 p(_z) = 1
因为Z0和Z1构成了ngram “_z”所有可能的情况。因此有：
Sum_Z0 p(_z) = 1 - Sum_Z1 p(_z)
插值模型计算公式
插值平滑算法在c(a_z) > 0的情况下，计算p(a_z)时，除了考虑c(a_z)之外，还需要考虑低阶的 ngram，如c(_z)等。
其中g(a_z)在c(a_z) = 0的情况下，为0。和回退平滑算法一样，在c(a_z)>0的情况下，插值平滑算法也需要从g(a_z)中折扣掉一部分概率，用于c(a_z) = 0的所有z构成的ngram。
"我想吃苹果"（a_z）存在，也要从这里面折掉一部分给到低元的"吃苹果"
折扣平滑算法
bow(a_)计算公式：
也可以用通用公式表示
p(a_z) = (c(a_z) > 0) ? f(a_z) : bow(a_) p(_z)
SRILM中的大部分平滑算法同时拥有回退和插值两种方式。根据以往的经验，一般插值方式的效果要优于回退方式。平滑算法方面，kneser-ney平滑要优于其他的平滑算法。
-cdiscount D
Ney 的绝对折扣（absolute discounting）使用参数D作为折扣常数。D必须要介于0和1之间。如果z1代表所有满足c(a_z) > 0的单词z的集合，则有如下等式存在：
f(a_z) = (c(a_z) - D) / c(a_)
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
上面为回退平滑的计算公式，对于插值平滑，有如下计算公式：
g(a_z) = max(0, c(a_z) - D) / c(a_)
p(a_z) = g(a_z) + bow(a_) p(_z) ; Eqn.4
bow(a_) = 1 - Sum_Z1 g(a_z) ; Eqn.5
= D n(a_*) / c(a_)
其实bow（a_）就是KN 平滑算法中第二项的参数
折扣系数D建议可以通过如下公式计算获取
D = n1 / (n1 + 2*n2)
上式中
n1代表出现次数为1次的ngram数目
n2代表出现次数为2次的ngram数目
后面会讲到这个D怎么分配
-kndiscount 和 –ukndiscount
Kneser-Ney折扣。前一个参数对应于modified Kneser-Ney折扣，而后一个参数对应于最初的Kneser-Ney折扣。Kneser-Ney折扣算法和绝对折扣算法比较相似，该算法同样是在ngram统计量count上减去一个常数D计算折扣概率。modified Kneser-Ney和Kneser-Ney的不同点就在于如何计算该常数D。
Kneser-Ney折扣的主要思想是为低阶的ngram使用一个修改后的概率估计（modified probability estimation）方法。具体来说，n元低阶的修正概率（modified probability）和训练语料中该低阶的不同前驱词数量成比例。通过折扣和归一化运算，有如下公式：
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
其中n(*_z)代表不同的*_z数量，这里*代表独立词通配符。D0和D1代表两个不同的折扣
常数，这是因为不同元数的ngram使用不同的常数。最终的条件概率和回退权重可以通过
如下公式（2）和（3）计算：
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
对于插值平滑有如下计算公式
p(a_z) = g(a_z) + bow(a_) p(_z) ; Eqn.4
假设z1为集合{z: c(a_z) > 0}，对于高阶ngram有：
g(a_z) = max(0, c(a_z) - D) / c(a_) # 用被平滑掉部分的最大似然求解
根据
bow（a_）：Sum_Z0p(_z) = 1 - Sum_Z1 p(a_z)
？# 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_)
对于n元语法 c(a_z) > 0，计算P(a_z)， 并且依然要计算回退bow（a_）
假设z2为集合{z: n(*_z) > 0}，对于低阶ngram有：
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(*_*)
最初的 Knser-Ney 折扣算法（-ukndiscount）对于任何 ngram 使用同一常数 D 进行折扣计算，该折扣常数根据如下公式计算获取：
D = n1 / (n1 + 2*n2)
上式中
n1代表出现次数为 1 次的 ngram 数目
n2代表出现次数为 2 次的 ngram 数目
Chen 和 Goodman 的 Modified Kneser-Ney 折扣（-kndiscount）算法对于每一个 ngram 均使用三个折扣常数，一个用于出现次数为 1 次的 ngram，一个用于出现次数为 2 次的 ngram，一个用于出现次数为 3 次和 3 次以上的 ngram，公式如下所示：
Y = n1/(n1+2*n2)
D1 = 1 - 2Y(n2/n1)
D2 = 2 - 3Y(n3/n2)
D3+ = 3 - 4Y(n4/n3)
Warning：
1. SRILM 默认会在 file.txt 文件中每个句子首尾分别加上句子开始标记和句子结束标记，因此不需要再 file.txt 文件中每个句子加上这两个标记。
2. SRILM 中 Kneser-Ney 折扣算法实际修改了低阶 ngram 的出现次数（counts）。因此当使用 -write 参数输出 -kndiscount 和 -ukndiscount 折扣算法下所有 ngram 的出现次数（counts）时，只有最高阶的 ngram 和以开始的 ngram 的出现次数（counts）为 c(a_z)，其他的 ngram 的出现次数为修改后的值 n(*_z)
3. arpa 格式的模型文件 file.lm每一行为一个 ngram 及其相关信息，具体格式如下：
log10(f(a_z)) <tab> a_z <tab> log10(bow(a_z))
根据公式（2），第一项 log10(f(a_z))代表 ngram a_z 的概率值以 10 为底的对数结果，后面更一个 ngram，ngram 中每一个单词通过空格隔开，最后一项为以 a_z开始的 (n+1) grams 的回退系数求以 10 为底的对数结果。
4.并不是所有的 ngram 都有参数指定的最高元。参数 -gtmin, -gt1min, ..., -gt9min 用于指定最小出现多少次的 n 元才会被包含在语言模型中。默认情况下，所有的一元和二元都会被包含进语言模型，高阶的 ngram 只会包含出现次数大于等于 2 的 ngram。（Some exceptions arise, because if one N-gram is included in the model file, all its prefix N-grams have to be included as well. This causes some higher order 1-count N-grams to be included when using KN discounting, which uses modified counts as described in Warning 2.）（ 出现一些例外情况，因为如果模型文件中包含一个N-gram，则还必须包括其所有前缀N-gram。 当用KN折扣时导致一些>1计数的N-gram像2中提到的那样，计数被修改掉）
5. 并不是模型中的所有 ngram 都有回退值，最高阶的 ngram 并不需要回退值。对于其他的低阶 ngram 来说，其存在回退值是因为其构成了某个更高阶 ngram 的前缀。对于其他的低阶ngram 来说回退值默认为 1，取以 10 为底的对数后即为 0。
Trick：
效果最好的modified Knser-Ney算法，使用插值方法，即-kndiscount -interpolate
-gtnmin表示出现次数小于特定值的gram将会被丢弃，对于所有的平滑算法都一样。默认是所有的1元和2元都会保留，其他阶的count>=2的才会保留。
-gtnmax表示次数小于特定值的count将会被修改，只是针对Good-Turing算法而言。
tips:
更换词典添加新词后，一定要重分词和生成lm模型。
如果不重新分词的话
我吃蓝莓 ------分词------> 我 吃 蓝 莓
我吃蓝莓 ---重新分词---> 我 吃 蓝莓
蓝莓这个词要是不重新分词在lm模型里就没了，不会出现这个词，这个词白加。
