N-Gram及其平滑技術(shù)

1、N-Gram及其平滑技術(shù)報告人：李榮陸E-Mail：1相關(guān)資料吳立德等，大規(guī)模中文文本處理，“稀疏事件的概率估計”，pp.5362。翁富良，王野翊，計算語言學(xué)導(dǎo)論， “概率語法”， pp.116145。2統(tǒng)計語言模型假設(shè)一個句子S可以表示為一個序列S=w1w2wn，語言模型就是要求句子S的概率P(S)： 這個概率的計算量太大，解決問題的方法是將所有歷史w1w2wi-1按照某個規(guī)則映射到等價類S(w1w2wi-1)，等價類的數(shù)目遠遠小于不同歷史的數(shù)目，即假定：3N-Gram模型當(dāng)兩個歷史的最近的N-1個詞（或字）相同時，映射兩個歷史到同一個等價類，在此情況下的模型稱之為N-Gram模型。N-Gr

2、am模型被稱為一階馬爾科夫鏈。 N的值不能太大，否則計算仍然太大。根據(jù)最大似然估計，語言模型的參數(shù)： 其中，C(w1w2wi)表示w1w2wi在訓(xùn)練數(shù)據(jù)中出現(xiàn)的次數(shù)4平滑技術(shù)的引入（1）傳統(tǒng)的估計方法對于隨機變量的N次獨立觀察的樣本容量N有如下要求：NK 其中K為隨機變量能夠取到的值的個數(shù)。實際語言模型中往往無法滿足這個要求。例如：詞性標注問題，共有140個可能的標記，考慮當(dāng)前詞前后兩個詞的影響的三階模型。K=140*140*140=2,744,000 給定一個10萬詞左右的人工標注訓(xùn)練集，即 N=100,00，可見訓(xùn)練數(shù)據(jù)顯得非常不足。5平滑技術(shù)的引入（2）假設(shè)k泛指某一事件，N(k)表示事

3、件k觀察到的頻數(shù)，極大似然法使用相對頻數(shù)作為對事件k的概率估計：p(k)=N(k)/N在語言模型中，訓(xùn)練語料中大量的事件N(k)=0，這顯然沒有反映真實情況。我們把這個問題稱為數(shù)據(jù)稀疏問題。這種零值的概率估計會導(dǎo)致語言模型算法的失敗，例如：概率值作為乘數(shù)會使結(jié)果為0，而且不能做log運算。6計數(shù)等價類根據(jù)對稱性原理，事件除了出現(xiàn)次數(shù)之外不應(yīng)具有細節(jié)特征，即所有具有相同計數(shù)r=N(k)的事件k（事件出現(xiàn)的次數(shù)稱為事件的計數(shù)）應(yīng)當(dāng)具有相同的概率估計值，這些計數(shù)相同的事件稱為計數(shù)等價，將它們組成的一個等價類記為計數(shù)等價類Gr。對于計數(shù)為r的計數(shù)等價類，定義nr為等價類中成員的個數(shù)，pr為等價類中事件

4、的概率，R是最大可能出現(xiàn)的計數(shù)次數(shù)，則7交叉檢驗（1）交叉檢驗就是把訓(xùn)練樣本分為m份，其中一份作為保留部分，其余m-1份作為訓(xùn)練部分。訓(xùn)練部分作為訓(xùn)練集估計概率pr，保留部分作為測試集進行測試。我們使用Cr表示保留部分中計數(shù)為r的計數(shù)等價類的觀察個數(shù)。對于保留部分使用最大似然法對進行概率pr進行估計，即使對數(shù)似然函數(shù)最大化：8使用拉格朗日乘子解決約束條件下的最大值問題，即：對pr求偏導(dǎo)，得到交叉檢驗估計：如果測試部分也作為保留部分的話，就是典型的極大似然估計：交叉檢驗（2）9留一估計留一方法是交叉檢驗方法的擴展，基本思想是將給定N個樣本分為N-1個樣本作為訓(xùn)練部分，另外一個樣本作為保留部分。這

5、個過程持續(xù)N次，使每個樣本都被用作過保留樣本。優(yōu)點：充分利用了給定樣本，對于N中的每個觀察，留一法都模擬了一遍沒有被觀察到的情形。對于留一方法，pr的極大似然估計為：10Turing-Good公式因為nRpR與1相比一般可以忽略，留一估計公式可以近似為：留一估計可以利用計數(shù)r=1的事件來模擬未現(xiàn)事件，對于未現(xiàn)事件有如下估計： 這個公式就是著名的Turing-Good公式。11空等價類留一估計中要求么個nr均不為0，在實際問題中當(dāng)r=5時，這個要求通常都不能滿足，即計數(shù)等價類G1,GR中存在空的等價類。這時按照出現(xiàn)次數(shù)進行排序：對應(yīng)的出現(xiàn)r(l)次的事件的個數(shù)記為nr(l)，在進行留一估計時，使

6、用下一個非空的等價類Gr(l+1)代替可能為空的等價類Gr(l)+1，留一估計公式變?yōu)椋?式中對空的等價類沒有估計概率，因為空等價類并沒有對應(yīng)任何有效事件。12Turing-Good估計的優(yōu)缺點和適用范圍缺點：( 1 )無法保證概率估計的“有序性”，即出現(xiàn)次數(shù)多的事件的概率大于出現(xiàn)次數(shù)少的事件的概率。(2)pr與r/N不能很好地近似，好的估計應(yīng)當(dāng)保證pr=r/N。優(yōu)點：其它平滑技術(shù)的基礎(chǔ)。適用范圍：對0r6的小計數(shù)事件進行估計。13約束留一估計單調(diào)性約束：pr-1=pr；折扣約束：p=r/N。約束留一估計：讓計數(shù)估計r*=prN處于距其最近的絕對頻數(shù)之間： 在這個約束下，單調(diào)性約束自然滿足。計算方法：計算時檢查每個pr是否滿足約束，不然就用約束的上下界進行裁剪，然后重新計算，一直迭代下去直到所有pr滿足約束。14折扣模型Katz指出Turing-Good公式實質(zhì)是對模型中觀察到的事件進行折扣，將折扣得來的概率攤到所n0個未現(xiàn)事件中。在這個思想的指導(dǎo)下，估計公式可以下成如下形式： 其中，dr是對計數(shù)為r的事件的計數(shù)的一個折扣函數(shù)。15絕對折扣模型若折扣函數(shù)定義為：dr=b，其中b為一個大于0的常數(shù)。那么未現(xiàn)事件的總概率為： 對應(yīng)絕對折扣模型的估計公式為：16刪除插值法（Deleted Interpolation）其基本思想是，由于N-Gram比N+1-Gram出現(xiàn)的可能性大的多，所