平滑的目的——解决数据稀疏性的问题

Knesser-Ney Smoothing

核心思想——劫富济贫

absolute discount smoothing

公式：

$P(w|u)=\frac{max(uw\in D-\delta ,0)}{{\sum }_{w^{\prime }}u{w}^{\prime }}+\lambda P_{KN}(w)$

$其中，P_{KN}(w)=\frac{C_{KN}(w)}{{\sum }_{w^{\prime }}{C}_{KN}(w^{\prime })}$

这样写，事实上，当词库中没有该单词组$uw$时，就用$w$的在词库中出现的频率来代替，但事实上，这样做会存在一个问题，举例如下：
这部分参考周周_hey的讲解：
https://www.jianshu.com/p/044108934966
San Francisco 是个地名，这个地名出现的频率很高。所以 Francisco 这个词出现的频率很高，那他对应的unigram概率应该也很高，也就是说比“glasses”这个的概率更高，但是实际上"Francisco"这个词单独出现的概率很低，他都是跟在"San"的后面出现的，unigram的计算方法不会考虑到这一点，导致Francisco的unigram特别高，那这个一元是不准确的。

又例如，conditioning和fencing这两个单词，乍一看，conditioning出现频率大于fencing，因为很多文章会用到air conditioning这一短语，大部分的conditioning会跟在air后面，然后fencing击剑这一运动就不是那么的常见了。如果给定一个没有见过的单词，conditioning出现在该单词后面的可能性小于fencing出现在该单词后面的可能性，所以，这种计算方法是不准确的。

解决办法：可以用$w$这个字前面出现的字的情况的数量来代替原先的用该字在词库中的数量，用数学公式表示就是：

$C_{KN}=|u:uw\in D|$

这里对公式进行说明一下，$u$是指目前的字，$w$是指$u$前面一个字，$uw$是指在$w$出现的条件下，$u$也出现的情况;$w^{\prime }$表示$u$前面的任何一个字

所以，最终的公式可以写为：

$P(w|u)=\frac{max(uw\in D-\delta ,0)}{{\sum }_{w^{\prime }}u{w}^{\prime }}+\lambda P_{KN}(w)$
$其中，P_{KN}(w)=\frac{C_{KN}(w)}{{\sum }_{w^{\prime }}{C}_{KN}(w^{\prime })}，C_{K}N=|u:uw\in D|$

Good-Turing Smoothing

以 trigrams(三元组)为例
$Vocabsize=10^4$
$trigrams=10^{12}$
在这$10^{12}$种可能性中，在数据集中出现的三元组的个数假定为：
$Totaltrigrams$ = $10^6$
在这出现的三元组中，每个三元组出现的频度也是不一样的，
$occurringonce=7.5\ast 10^5$
$occurringtwice=2\ast 10^5$
$occurringthreetimes=9\ast 10^4$
$...$
$occurringzerotimes=10^{12}-10^6$
随着词在数据里出现的次数增多，这样的不同的词的个数会越来越少

目的是给这些数据里没有出现但是可能存在的三元组一个非零的次数

想法：用一个更大的数据集包含现在的数据集，那么那些为零的次数在更大的数据集里面次数就可能不为0了，
设原来出现的次数为$r$，在更大数据集里面出现的次数为$C_r$，我们要做的就是一个从$r$到$C_r$的映射

把原来有意义的数据，按照出现的次数打乱，第一列就是出现一次的词（$r=1$），第二列就是出现两次的词（$r=2$）,以此类推，每一个框就代表这个词在data中出现的总次数，$N1$表示这一列有$N1$个框，总词数 = $1\ast N1+2\ast N2+...$

$trigrams={\sum }_{r=1}^{\infty }r\ast N_r$

假定在更大的数据集里面，框的批次规律不发生改变，在原来数据集中出现零次的框在更大数据集里面假定用N1的框，在原来数据集中出现一次的框在更大数据集里面假定用N2的框，依此类推

$occurringonce=7.5\ast 10^5\to r\ast N_r=7.5\ast 10^5$
$occurringtwice=2\ast 10^5\to r\ast N_r=2\ast 2\ast 10^5$
$occurringthreetimes=9\ast 10^4\to r\ast N_r=3\ast 9\ast 10^4$
$...$
$occurringzerotimes=10^{12}-10^6\to r\ast N_r=0$

估算：

$r\ast N_r=C_{r-1}\ast N_{r-1}$
$C_{r-1}=\frac{r\ast N_r}{N_{r-1}}$

例如：

$C_0=\frac{7.5\ast 10^5}{10^{12}}=7.5^{-7}$
$C_1=\frac{4\ast 10^5}{7.5\ast 10^5}=0.53$