圖靈估計

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
• 北京大學《自然語言處理概論》課件