图灵估计

Good-Turing平滑法可处理N元语法中数据矩阵的稀疏问题，主要思想将非零N元语法的概率均匀分给一些低概率语法，以修改最大似然估计与真实概率之间的偏离。是使用的比较多的一种平滑算法。

应用背景

在自然语言处理的N元模型中，用最大似然估计（MLE）作为某个字符串出现的概率，这样会造成数据稀疏问题，并且使得MLE值偏离真实概率。这个问题与N元语法自身有关，他们不能估计长距离的上下文，总是倾向于过低地估计哪些在训练语料库中不是彼此向邻近出现的符号串的概率。

平滑就是给那些“零概率和低概率的N元语法”指派非零概率的方法。平滑分为打折和回退，打折是指将某个非零N元语法的计数降下来，把这部分概率量指派给那些训练语料库中出现次数为零或很低的事件。回退指用根据N-1元语法计数来建立N元语法模型。

名称由来

Good-Turing平滑法由古德於1953年提出，而这种算法的思想则来自图灵，算法证明参见：Church et al.（1990）

计算方法

Good-Turing基本思想是：用观察计数较高的N元语法数重新估计概率量的大小，并把它指派给那些具有零计数或者较低计数的N元语法。

涉及的符号含义为：

$c$：某个N元语法出现的频数。

$N_{c}$:出現次數為c的N-gram片語的個數，是频数的频数即：

$N_{c}=\sum _{b:c(b)=c}1$

$c^{*}$:Good-Turing平滑计数：

$c^{*}=(c+1){\frac {N_{c+1}}{N_{c}}}$

Katz所做改进

Katz认为，实际上，并非对于所有的计数C都使用打折估计$c^{*}$的计数是可靠的，假定对较大的计数是可靠的（对于某个阈值k，c>k），他建议取k的值为5，即：

$c^{*}=c(c>K)$

当引入某个K时，C*的正确等式为：（Katz，1987）

$c^{*}={\cfrac {(c+1){\cfrac {N_{c+1}}{N_{c}}}-c{\cfrac {(k+1)N_{k+1}}{N_{1}}}}{1-{\cfrac {(k+1)N_{k+1}}{N_{1}}}}},1\leq c\leq k$

Good-Turing常常与Katz回退法一起使用，实际上所有的回退语言模型都必须打折。其他打常见平滑法还有：加1平滑，Witten-Bell打折法，留存估计，删除估计，Add-delta等。

参考文献

• Danie Jurafsky, James H. Marin，孙志伟、孙乐[译]：Speech And Language Processing[M]，北京：电子工业出版社，2005
• 北京大学《自然语言处理概论》课件