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

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

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

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

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

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

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