尹 陳, 吳 敏

(中國(guó)科學(xué)技術(shù)大學(xué) 軟件學(xué)院, 合肥 230051)

想象一個(gè)人機(jī)對(duì)話系統(tǒng), 當(dāng)計(jì)算機(jī)在屏幕上顯示:

Please turn your homework …

大部分人認(rèn)為homework后面應(yīng)該接to或者是over, 但是不可能是on. 那么計(jì)算機(jī)處理這個(gè)任務(wù)時(shí),它根據(jù)什么來(lái)決定后面接什么？

讓計(jì)算機(jī)處理自然語(yǔ)言的一個(gè)基本問(wèn)題是為自然語(yǔ)言這種上下文有關(guān)的特性建立數(shù)學(xué)模型——統(tǒng)計(jì)語(yǔ)言模型, 它是今天所有自然語(yǔ)言處理任務(wù)的基礎(chǔ). 在20世紀(jì)70年代由賈里尼克提出的N-gram模型是最常用的統(tǒng)計(jì)語(yǔ)言模型之一, 廣泛用于當(dāng)今的多種自然語(yǔ)言處理系統(tǒng)中[1]. 目前關(guān)于N-gram模型應(yīng)用的研究有機(jī)器翻譯自動(dòng)評(píng)分, 摘要生產(chǎn)系統(tǒng)自動(dòng)評(píng)分, 單詞分類, 文本分類等[2–5], 但是卻沒有對(duì)于N-gram模型主要平滑方法的綜合介紹, 所以本文著重介紹了幾種常用的平滑方法.

計(jì)算機(jī)利用N-gram模型計(jì)算出后面每個(gè)可能的詞的概率, 并選擇概率最大的詞放到homework后面,N-gram模型還用于計(jì)算整個(gè)句子在語(yǔ)料庫(kù)中出現(xiàn)的概率, 比如下面兩條語(yǔ)句:

S1:I am watching movie now.

S2:watching I am now movie.

N-gram模型會(huì)預(yù)測(cè)句子S1的概率p(S1)大于句子S2的概率p(S2).

在語(yǔ)音識(shí)別和手寫識(shí)別任務(wù)中, 我們需要估算出每個(gè)詞w的概率p(w)來(lái)識(shí)別出帶有噪音的詞或者是模棱兩可的手寫輸入.

在拼寫糾錯(cuò)系統(tǒng)中, 我們需要找出并糾正句子中拼錯(cuò)的詞, 比如句子:

S3:Their are so many people.

S4:There are so many people.

在句子S3中計(jì)算機(jī)認(rèn)為There被錯(cuò)拼成了Their了, 因?yàn)镾4出現(xiàn)的概率p(S4)大于S3出現(xiàn)的概率p(S3), 所以系統(tǒng)會(huì)將Their更正為There.

在機(jī)器翻譯任務(wù)中, 需要確定每個(gè)詞序列的概率以找出最正確的翻譯結(jié)果:

S5:我今天要去上學(xué).

S6:I today want go on learn.

S7:I today want go to school.

S8:I am going to school today.

由于在英語(yǔ)短語(yǔ)中, go to school出現(xiàn)的概率要比go on learn大以及時(shí)間通常放在句尾, 所以計(jì)算機(jī)認(rèn)為p(S8)＞p(S7)＞p(S6), 因此S8更有可能是正確的翻譯[6].

N-gram模型常用于估算給定語(yǔ)句在語(yǔ)料庫(kù)中出現(xiàn)的概率, 一個(gè)N-gram是一個(gè)長(zhǎng)為N的詞序列. 當(dāng)N=1時(shí)稱為Unigram模型即一元模型, 也叫上下文無(wú)關(guān)模型;當(dāng)N=2時(shí)稱為bigram模型即二元模型;當(dāng)N=3時(shí)稱為trigram模型即三元模型.

1 N-gram模型

N-gram模型的基本原理是基于馬爾可夫假設(shè), 在訓(xùn)練N-gram模型時(shí)使用最大似然估計(jì)模型參數(shù)——條件概率.

1.1 基本原理

假設(shè)S=w1w2w3…wn表示給定的一條長(zhǎng)為n的語(yǔ)句, 其中wi(1≤i≤n)是組成句子S的單詞, 則S出現(xiàn)在語(yǔ)料庫(kù)中的概率:

根據(jù)鏈?zhǔn)椒▌t和條件概率公式,S出現(xiàn)的概率p(S)等于S中每個(gè)單詞wi(1≤i≤n)出現(xiàn)的概率相乘:

所以為了簡(jiǎn)化計(jì)算的復(fù)雜度, 馬爾可夫提出了馬爾可夫假設(shè):假設(shè)任意一個(gè)單詞wi出現(xiàn)的概率只和它前面的單詞wi-1有關(guān):

基于馬爾可夫假設(shè)得到的是二元模型:

馬爾可夫的假設(shè)有不足之處, 比如“happy new year”中“year”其實(shí)和“new”與“happy”都有關(guān), 因此柯爾莫果洛夫?qū)ⅠR爾可夫假設(shè)推廣到一般形式:假設(shè)句子中的每個(gè)單詞與其前面N–1個(gè)詞有關(guān):

這稱為N–1階馬爾可夫假設(shè)[6].

1.2 參數(shù)估計(jì)

在訓(xùn)練N-gram模型時(shí), 一個(gè)重要的問(wèn)題就是模型的參數(shù)估計(jì)即估計(jì)條件概率. 以二元模型為例, 需要估計(jì)條件概率p(wi|wi-1), 假設(shè)c(wi-1)為詞wi-1在訓(xùn)練語(yǔ)料庫(kù)中出現(xiàn)的次數(shù),c(wi-1,wi)為二元組(wi-1,wi)在訓(xùn)練語(yǔ)料庫(kù)中出現(xiàn)的次數(shù), 于是:

假設(shè)一個(gè)只有三條語(yǔ)句的語(yǔ)料庫(kù), 每條語(yǔ)句以結(jié)束:

則二元模型計(jì)算出的部分條件概率如下:

現(xiàn)在我們將在實(shí)際中使用N-gram模型, 以布朗語(yǔ)料庫(kù)的新聞?lì)悇e為訓(xùn)練語(yǔ)料庫(kù), 該語(yǔ)料庫(kù)的規(guī)模有10054個(gè)標(biāo)識(shí)符, 以句子:

S9:I will run for the governor.

為例, 考慮二元模型, 在語(yǔ)料庫(kù)中的各項(xiàng)統(tǒng)計(jì)數(shù)據(jù)如表1和表2所示.

表1 S9中單詞在訓(xùn)練語(yǔ)料庫(kù)中的頻數(shù)

表2 S9中二元組在訓(xùn)練語(yǔ)料庫(kù)中的頻數(shù)和頻率

表1和表2中, (#, I)表示S9以I開頭, (governor,$)表示S9以governor結(jié)尾, 根據(jù)公式(6)計(jì)算S9出現(xiàn)的概率, 由于概率值均在0～1之間, 導(dǎo)致多個(gè)概率相乘的結(jié)果會(huì)非常小, 所以我們對(duì)最終的概率值取以10為底的對(duì)數(shù), 結(jié)果是–11.2849(后面概率計(jì)算結(jié)果均是取對(duì)數(shù)后的結(jié)果).

在實(shí)際應(yīng)用中, 通常使用三元模型的居多, 谷歌公司的翻譯系統(tǒng)則使用四元模型, 這個(gè)模型存儲(chǔ)在500臺(tái)以上的服務(wù)器中.

1.3 零概率問(wèn)題

假設(shè)有如下語(yǔ)句:

S10:Will I run the for governor.

考察一下它出現(xiàn)的概率

表3 S10中二元組在訓(xùn)練語(yǔ)料庫(kù)中的頻數(shù)和頻率

統(tǒng)計(jì)時(shí)出現(xiàn)了很多頻數(shù)為零從而導(dǎo)致頻率為零的結(jié)果, 即所謂的零概率問(wèn)題.

布朗語(yǔ)料庫(kù)的新聞?lì)悇e中使用最頻繁的前50個(gè)單詞的頻數(shù)變化(包括標(biāo)點(diǎn)符號(hào))如圖1所示.

圖1 單詞頻數(shù)變化

在該語(yǔ)料庫(kù)中只有極少數(shù)單詞被經(jīng)常使用, 而絕大多數(shù)單詞很少被使用, 這就是著名的Zipf定律:一個(gè)單詞出現(xiàn)的次數(shù)與它在頻率表里的排名成反比. 假設(shè)在語(yǔ)料庫(kù)中出現(xiàn)r次的詞有Nr個(gè), 那么在布朗語(yǔ)料庫(kù)的新聞?lì)悇e中它們之間的關(guān)系符合圖2所示的Zipf定律.

詞出現(xiàn)的次數(shù)r與詞的數(shù)量Nr是反比例關(guān)系, 即Nr+1＜Nr. 假設(shè)語(yǔ)料庫(kù)的規(guī)模為M, 未出現(xiàn)的詞的數(shù)量是Nr, 則有:

那么出現(xiàn)r次的詞在語(yǔ)料庫(kù)中的頻率為r/M, 那么由于語(yǔ)料庫(kù)規(guī)模的限制, 導(dǎo)致我們統(tǒng)計(jì)二元組(Will,I)的頻數(shù)為0, 但是事實(shí)上Will I這種搭配在英語(yǔ)中很常見, 所以根據(jù)這樣的方法估算概率顯然是有誤差的.

圖2 Zipf定律

2 N-gram模型的評(píng)價(jià)標(biāo)準(zhǔn)

評(píng)價(jià)一個(gè)語(yǔ)言模型的最佳評(píng)價(jià)方法是把模型應(yīng)用到實(shí)際的產(chǎn)品中, 比較該產(chǎn)品在應(yīng)用模型前后的性能提高程度, 這稱為外部評(píng)價(jià). 但是在實(shí)驗(yàn)中, 由于資源的限制我們無(wú)法使用外部評(píng)價(jià), 更多的是使用內(nèi)部評(píng)價(jià)方法, 即在測(cè)試集上使用困惑度作為語(yǔ)言模型的評(píng)價(jià)準(zhǔn)則.

假設(shè)測(cè)試集W=w1w2w3···wN, 于是在測(cè)試集上的困惑度如下:

然后使用鏈?zhǔn)椒▌t擴(kuò)展:

因此, 應(yīng)用到二元模型就得到:

由式(8)可知, 一個(gè)詞序列的概率越大, 它的困惑度就越小, 所以語(yǔ)言模型的優(yōu)化目標(biāo)就是最小化困惑度.

我們可以從另一個(gè)角度來(lái)看待困惑度:語(yǔ)言的加權(quán)平均分支因子. 語(yǔ)言的分支因子指的是可以跟在任意一個(gè)詞后的所有可能的詞的數(shù)量. 假設(shè)有一個(gè)數(shù)字識(shí)別系統(tǒng), 用來(lái)識(shí)別0, 1, 2, ···, 9共10個(gè)數(shù)字, 假設(shè)每個(gè)數(shù)字出現(xiàn)的概率都是P=1/10, 于是對(duì)于任意長(zhǎng)為N的數(shù)字序列, 這個(gè)系統(tǒng)的困惑度是10:

換句話說(shuō), 任意的一個(gè)數(shù)字后面可以接0～9共10個(gè)數(shù)字中的任意一個(gè)數(shù)字, 所以這個(gè)數(shù)字語(yǔ)言的分支因子是10.

我們?cè)诓祭收Z(yǔ)料庫(kù)上分別訓(xùn)練了一元模型, 二元模型和三元模型, 它們的困惑度是

表4 三種N-gram模型的困惑度

由此可見, N-gram模型考慮的上下文越長(zhǎng), 模型的困惑度就越低.

3 平滑

回到前面的零概率問(wèn)題, 避免零概率問(wèn)題的方法之一是防止模型把沒看到的事件(如二元組(Will,I))的概率算為零. 所以我們有兩種解決方法, 增大語(yǔ)料庫(kù)和改變概率估算方法.

我們加入了布朗語(yǔ)料庫(kù)的政府文本類別和學(xué)術(shù)文本類別, 統(tǒng)計(jì)S2中二元組頻數(shù)如表5所示.

表5 S2中二元組在擴(kuò)大后的語(yǔ)料庫(kù)中的頻數(shù)

在增加了語(yǔ)料庫(kù)規(guī)模后, 還是沒有解決零概率問(wèn)題. 所以我們需要平滑:將一部分概率分配給沒看到的事件, 主要的平滑方法有拉普拉斯平滑, 卡茨回退和Kneser-Ney 平滑[7–9].

3.1 拉普拉斯平滑

最簡(jiǎn)單的平滑方法是規(guī)定所有的詞或詞對(duì)至少出現(xiàn)一次, 所以即使是未出現(xiàn)的詞或詞對(duì), 它們的出現(xiàn)次數(shù)也被人為設(shè)定為1. 這種平滑方法稱為拉普拉斯平滑. 拉普拉斯平滑在現(xiàn)代的N-gram模型中表現(xiàn)不是十分好, 但是它是所有其他平滑方法的基礎(chǔ), 現(xiàn)在仍然被廣泛應(yīng)用在文本分類領(lǐng)域中.

假設(shè)語(yǔ)料庫(kù)規(guī)模為M, 語(yǔ)料庫(kù)的詞匯表規(guī)模為V.對(duì)于一元模型來(lái)說(shuō), 設(shè)詞wi的出現(xiàn)次數(shù)為ci, 未使用平滑方法之前估算wi的概率為:

應(yīng)用拉普拉斯平滑后的概率為:

可見拉普拉斯平滑方法將所有的詞計(jì)數(shù)都增加1,這種平滑方法也叫做Add-one平滑.

為了計(jì)算的方便, 通常情況下定義一個(gè)調(diào)節(jié)計(jì)數(shù):

顯然有ci＞, 于是拉普拉斯平滑相當(dāng)于對(duì)原始計(jì)數(shù)ci打了一個(gè)折扣dc:

現(xiàn)在我們將其推廣到二元模型:

再次統(tǒng)計(jì)出S2中二元組在訓(xùn)練語(yǔ)料庫(kù)中的頻率,如表6.

表6 經(jīng)過(guò)Add-one后的S2中二元組的頻率

可以發(fā)現(xiàn)零概率問(wèn)題已經(jīng)被解決. 但是由于語(yǔ)料庫(kù)中未出現(xiàn)的詞或詞對(duì)的數(shù)目太多, 拉普拉斯平滑導(dǎo)致為它們分配了很大的概率空間, 所以我們可以不加1, 轉(zhuǎn)而選擇尋找一個(gè)小于1的正數(shù)k, 此時(shí)的概率計(jì)算公式為:

此時(shí)叫做Add-k平滑.

3.2 卡茨回退

古德和圖靈提出了一種在統(tǒng)計(jì)中相信可靠的統(tǒng)計(jì)數(shù)據(jù), 而對(duì)不可靠的統(tǒng)計(jì)數(shù)據(jù)打折扣的一種概率估計(jì)方法:從概率的總量1中分配一個(gè)很小的比例給沒有看見的事件, 這樣沒有看見的事件也擁有了很小的概率.

在一個(gè)語(yǔ)料庫(kù)中出現(xiàn)次數(shù)越小的詞, 說(shuō)明這個(gè)詞很少使用, 甚至是不可靠的. 所以當(dāng)r較小的時(shí)候, 統(tǒng)計(jì)數(shù)據(jù)可能不可靠, 于是選取一個(gè)閾值σ , 按照古德-圖靈估計(jì)重新計(jì)算r小于σ 的詞的出現(xiàn)次數(shù):

仍然有:

于是當(dāng)r＞σ時(shí), 對(duì)應(yīng)的詞的概率估計(jì)是r/M;當(dāng)r＜ σ時(shí), 對(duì)應(yīng)的詞的概率估計(jì)是r?/M;將1-r/M-r?/M這部分概率分配給沒有看到的詞. 因此二元模型的概率估計(jì)公式如下:

其中,

當(dāng)我們?nèi)ˇ?=8時(shí)對(duì)句子S2的統(tǒng)計(jì)數(shù)據(jù)如表7.

表7 經(jīng)過(guò)卡茨回退后的S2中二元組的頻率

由于一個(gè)單詞wi出現(xiàn)的次數(shù)比兩個(gè)單詞(wi-1,wi)出現(xiàn)的次數(shù)要多得多, 所以它的頻率就越接近概率分布. 同理, 兩個(gè)單詞 (wi-1,wi)出現(xiàn)的次數(shù)要比三個(gè)單詞wi-2,wi-1,wi)出現(xiàn)的次數(shù)多得多, 所以兩個(gè)單詞的頻率比三個(gè)單詞的頻率更接近概率分布. 同時(shí), 低階模型的零概率問(wèn)題要比高階模型輕微, 所以可以使用線性插值的方法, 將高階模型和低階模型做線性組合, 這種方法叫做刪除插值.

比如估算三元模型的概率時(shí), 把一元模型, 二元模型和三元模型結(jié)合起來(lái), 每種模型賦予不同的權(quán)重1,λ2,λ3, 公式如下:

其中, λ1+λ2+λ3=1. 但是刪除插值的效果略低于卡茨回退, 所以現(xiàn)在很少使用.

3.3 Kneser-Ney平滑

Kneser-Ney算法是目前使用最為廣泛的, 效果最好的平滑方法. 它的基本思想是絕對(duì)折扣.

我們從訓(xùn)練語(yǔ)料庫(kù)中隨機(jī)抽取25%的數(shù)據(jù)作為驗(yàn)證集, 統(tǒng)計(jì)得出在訓(xùn)練集和驗(yàn)證集中出現(xiàn)次數(shù)在0～9之間的bigram的對(duì)比數(shù)據(jù)如表8.

表8 bigram數(shù)據(jù)對(duì)比

可以看出訓(xùn)練集中的bigram數(shù)目在超過(guò)1后, 比驗(yàn)證集中bigram數(shù)目約多0.75, 所以對(duì)統(tǒng)計(jì)出的bigram打一個(gè)絕對(duì)折扣——總是將這0.75分配給那些沒看見的bigram:

其中,d可以直接設(shè)為0.75, λ是一個(gè)權(quán)重值.

Kneser-Ney平滑對(duì)絕對(duì)折扣進(jìn)行了改進(jìn), 給定一條語(yǔ)句w1w2···wi-1, 則接下來(lái)的詞wi出現(xiàn)的概率:

于是Kneser-Ney平滑為:

表示正則化的折扣量[10].

4 總結(jié)

N-gram模型在目前的自然語(yǔ)言處理任務(wù)中使用最為廣泛的統(tǒng)計(jì)語(yǔ)言模型, 它的顯著缺點(diǎn)是無(wú)法避免的零概率問(wèn)題, 有時(shí)可以通過(guò)增大語(yǔ)料庫(kù)規(guī)模來(lái)解決,但是自然語(yǔ)言是一種動(dòng)態(tài)的語(yǔ)言, 所以從概率計(jì)算的方法這一角度來(lái)解決零概率問(wèn)題是在目前是比較科學(xué)的. 經(jīng)過(guò)實(shí)驗(yàn)對(duì)于規(guī)模較小(語(yǔ)料庫(kù)規(guī)模在3萬(wàn)以內(nèi))的語(yǔ)言處理任務(wù), 卡茨回退平滑方法效果就已經(jīng)很明顯, 在接下來(lái)的研究中, 我們將重點(diǎn)放在優(yōu)化與綜合利用卡茨回退和Kneser-Ney平滑方法, 利用N-gram模型構(gòu)建一個(gè)提取文章潛在語(yǔ)義的英語(yǔ)作文批改系統(tǒng).

表9 經(jīng)過(guò)Kneser-Ney后的S2中二元組的頻率