基于CRF模型的英文詞性標注研究

劉星宇，寧慧,2，張汝波

1. 哈爾濱工程大學 軟件學院，黑龍江 哈爾濱 150001

2. 哈爾濱工程大學 計算機科學與技術(shù)學院，黑龍江 哈爾濱 150001

3. 大連民族大學 機電工程學院，遼寧 大連 116600

如今，人工智能已經(jīng)逐步走進人們的生活中，并不斷為人們提供高質(zhì)量的服務(wù)，所以自然語言處理技術(shù)也變得尤為重要。作為人工智能技術(shù)的核心，自然語言處理的詞性標注分析在多個領(lǐng)域中都有所應(yīng)用，如機器翻譯、文本分析、問題解答及機器人科學等領(lǐng)域都具有很高的應(yīng)用價值，在未來還會有更高的發(fā)展空間。而條件隨機場用于詞性分析有著更加準確、靈活的特點，因此使用條件隨機場進行詞性分析的研究具有重大的意義。

針對使用適當?shù)哪Ｐ突蚪Y(jié)構(gòu)來提升詞性標注結(jié)果準確率的問題，本文使用實驗對隱馬爾可夫模型和條件隨機場模型進行了模擬實現(xiàn)，同時使用條件隨機場的不同特征方程進行了多組實驗，并對比了每組實驗的準確率，結(jié)合實驗結(jié)果得到最終結(jié)論。

1 相關(guān)技術(shù)

1.1 條件隨機場

條件隨機場是指在給定一組輸入隨機變量條件下，輸出另一組隨機變量的條件概率分布模型，并假設(shè)輸出的隨機變量構(gòu)成馬爾可夫隨機場。在條件隨機場的定義中，若要求條件概率分布P(Y|X)，要求條件隨機場符合在給定隨機變量X的情況下，隨機變量Y需滿足：

式中：w～v表示與v結(jié)點直接有邊連接的所有結(jié)點w；w≠v表示除了v結(jié)點本身以外的所有結(jié)點w[1]。

若式(1)對任意結(jié)點v成立，則P(Y|X)被稱作是一個條件隨機場。

“條件”指它是個判別式模型P(Y|X)，“隨機場”指它是個無向圖模型，無向圖模型并不關(guān)注于每個事件是否有因果關(guān)系，并不涉及條件概率的分解。對于邊沒有方向的無向圖模型，它只代表2個事件是有聯(lián)系的[2]。條件隨機場最大的優(yōu)點是可以著眼于整個句子定義更靈活性的特征函數(shù)，并讓所有特征可以進行全局歸一化，能夠求得全局的最優(yōu)解，甚至可以在特征函數(shù)中判斷句子是否以問號結(jié)尾成為一個問句，從而更加準確地判斷每個位置的單詞更加接近正確的詞性。其中，利用了yt本身的特征稱為狀態(tài)特征，利用了yt-1和yt之間關(guān)系的特征則稱為轉(zhuǎn)移特征[3]。由于詞性標注是一種鏈型結(jié)構(gòu)，所以可得條件隨機場模型的鏈型表示為圖1所示。

圖1 CRF鏈型模型

1.2 英文詞性標注過程簡介

對于詞性標注問題，可以分解為以下3點：learning問題、marginal prob及MAP Inference。首先learning問題就是進行參數(shù)估計，也就是參數(shù)學習，即利用訓練集來訓練特征函數(shù)來生成并調(diào)整特征值，這里的訓練集應(yīng)該由一個個已經(jīng)標注好的樣本構(gòu)成，并且數(shù)量必須盡可能多才能將參數(shù)調(diào)整到概率上最為準確[4]。marginal prob指的是邊緣概率計算問題，即對于某一個單詞個體，標注成某詞性yt的概率值，即可以用P(yt|x)來表示。MAP Inference指的就是decoding問題，即用一定的算法，找到這樣的一種標注序列，使得條件概率達到最大，最后選擇這種標注作為結(jié)果標注進行預(yù)測[5]。

2 英文詞性標注過程的研究

2.1 邊緣概率計算

對于邊緣概率計算，當特征值通過一定算法學習好后，特征值就可以被使用進行詞性的預(yù)測，而在對整個句子進行預(yù)測時，實際上是對每個單詞相應(yīng)的算法進行預(yù)測，這時就是要計算其邊緣概率，這里使用處于中間推導(dǎo)過程的勢函數(shù)乘積的公式[6]：

需要注意的是，這里為了運算及表達方便，忽略考慮了邊界結(jié)點，相當于在最初的y1結(jié)點前補充一個y0結(jié)點，方便運算處理。式中，P(y|x)中的y代表的是y1,y2,…,yT的所有y值，然而，當進行邊緣概率計算時，即計算某一結(jié)點的標注P(yt=i|x)時，需要將yt以外的結(jié)點值都進行積分處理，又由于y的分布是離散分布，所以對于y的積分即為求和運算，所以可以推導(dǎo)出：

對公式進行簡單的分解來簡化表達，可以得出：

將原來的勢函數(shù)乘積公式(2)代入式(4)，可以得到：

對式(5)進行時間復(fù)雜度分析，可以看出，若一個詞共有S種標注方式，總共有T個yt構(gòu)成，也就是T個要標注的詞，再計算最后T規(guī)模的連乘，總時間復(fù)雜度為O(|S|T×T)，是指數(shù)級的時間復(fù)雜度。對于指數(shù)級時間復(fù)雜度，計算量過大過于復(fù)雜，這種暴力求解的方法可以認為是不可解的，所以需要對其進行進一步的化簡，化簡思路就是將連加進行后移，移到連加運算的主體參數(shù)上，使連加提前進行，做到簡化運算?？梢詫⒐椒譃閮刹糠?，一部分是y1,y2,…,yt-1，一部分是yt+1,yt+2,…,yT，記為Δ左和Δ右，所以公式可化為式(6)的形式[7]：

下面分別來分析，首先對于Δ左，可以將其展開以便觀察和化簡為

其中，若一個詞共有S種標注方式，yt是屬于S集合內(nèi)的。同理，相對于左側(cè)公式，也可以寫出右側(cè)公式：

此時，可以根據(jù)動態(tài)規(guī)劃的思想對公式進行化簡，就轉(zhuǎn)變成了前向-后向算法的形式。在Δ左中，對于一個線性鏈結(jié)構(gòu)，積分(對于離散分布也就是連加)可以按照鏈型的次序進行，將每一步驟的積分結(jié)果作為下一步積分的公式參數(shù)，就形成了動態(tài)規(guī)劃轉(zhuǎn)移方程的形式，即前向算法的形式。例如，對于 ψ1(y0,y1,x)這個式子，由于y0只存在于本式中，而y1除了本式中存在，還存在于ψ2(y1,y2,x)中，所以對于此式可以將y0進行積分，僅保留y1作為下一步積分的公式參數(shù)，此時式子就可以寫成：

進一步思考后不難發(fā)現(xiàn)，y2既存在于此公式中，也存在于 ψ3(y2,y3,x)中，依此類推，最后，Δ左式可以化為

為化簡可以將式(9)中多余的括號去掉進行合并，得到式(10)：

設(shè) αt(i)表示y0,y1,…,yt-1的所有勢函數(shù)以及yt=i的左半部分勢函數(shù)，根據(jù)前向算法以及概率圖模型中精準推斷的變量消除法的思想，原式可以進一步轉(zhuǎn)化為

所以同理，也可以寫出yt右側(cè)的后向算法表達式轉(zhuǎn)化為

因此綜上所述可以得到邊緣概率

2.2 參數(shù)學習

在條件隨機場中的參數(shù)學習問題就是求特征方程的特征值，這里可以使用梯度上升算法，即通過不斷找出偏導(dǎo)數(shù)的絕對值最大的方向進行移動，找到最大值[8]。設(shè)特征值分別為λ和η，則其表達式為

為簡化運算，又由于對數(shù)函數(shù)為單調(diào)函數(shù)，所以可以將公式對數(shù)化，將連乘轉(zhuǎn)化成連加的形式：

此時將argmax后的部分看成整體，作為一個函數(shù)，記為L，根據(jù)梯度上升算法原理，需求出λ和η的 偏導(dǎo) ?λL和 ?ηL，尋找梯度最大方向，一步步找到λ和 η的最大值[4]。下面進行求偏導(dǎo)，如式(7)：

式 中： logZ(x(i),λ,η)稱作log-partition function，是一種配分函數(shù)，它在指數(shù)族分布中是一個非常重要的概念，對其求導(dǎo)所得到的是所對應(yīng)的充分統(tǒng)計量的期望，其偏導(dǎo)數(shù)經(jīng)過推理后可得

對于邊緣概率的計算，依然使用前向-后向算法來求解，即邊緣概率計算的過程，唯一的不同點在于本公式為對2個y變量的求解：

綜上所述，對于 ?λL和 ?ηL，整理可得：

根據(jù)梯度上升算法以及上述所求的結(jié)果，最后求得參數(shù)λ和η[9]：

2.3 詞性預(yù)測

條件隨機場的詞性預(yù)測所用核心算法為維特比算法，在機器學習中，維特比算法是一種應(yīng)用非常廣泛的算法，它基于動態(tài)規(guī)劃思想，在求解隱馬爾可夫模型、條件隨機場的預(yù)測等問題中均用到了該算法。實際上，維特比算法不僅是很多自然語言處理的解碼算法，也是現(xiàn)代數(shù)字通信中使用最頻繁的算法[10]。

維特比算法的目的是要求出圖2中的一條路徑，使得該路徑對應(yīng)的概率值最大。對應(yīng)圖2來講，假設(shè)每個時刻x可能取的值為3種，如果直接求解結(jié)果的話，會有3N的排列組合數(shù)，其中底數(shù)3為籬笆網(wǎng)絡(luò)寬度，指數(shù)N為籬笆網(wǎng)絡(luò)的長度，因此時間復(fù)雜度達到無法運算的指數(shù)級，計算量非常大，若設(shè)每個時刻x可能取的值為D種，則時間復(fù)雜度為O(DN)。維特比利用動態(tài)規(guī)劃的思想來求解概率最大路徑，使得時間復(fù)雜度正比于序列長度，復(fù)雜度為O(ND2)，從而很好地解決了問題[11]。

圖2 維特比算法示意

3 實驗過程與結(jié)果分析

3.1 隱馬爾可夫模型實驗

在使用隱馬爾可夫模型來實現(xiàn)詞性標注時，核心是隱馬爾可夫模型的三大矩陣[4]，分別是初始狀態(tài)概率分布矩陣(π矩陣)、輸出觀測矩陣(A矩陣)和狀態(tài)轉(zhuǎn)移矩陣(B矩陣)[12]。

其中，初始狀態(tài)概率分布矩陣指的是第一個單詞被標注成各個詞性的概率矩陣，若設(shè)第一個結(jié)點前有一個虛擬的start結(jié)點，可以看成在start虛擬結(jié)點到第一個結(jié)點的概率。輸出觀測矩陣指的是在當前位置為詞性n的情況下，出現(xiàn)單詞m的概率。狀態(tài)轉(zhuǎn)移矩陣指的是在前一個位置為詞性n’的情況下，當前位置的詞性為n的概率[13]。

1)先將訓練集讀入。在讀入的過程中將單詞和詞性轉(zhuǎn)化為編號數(shù)字存儲在數(shù)組中以便于進行操作，同時記錄不同單詞總數(shù)M以及詞性種類總數(shù)N。

2)根據(jù)M和N構(gòu)造相應(yīng)大小的初始狀態(tài)概率分布矩陣、輸出觀測矩陣和狀態(tài)轉(zhuǎn)移矩陣。

3)再次讀入訓練集，對三大矩陣進行填充。根據(jù)各個單詞是否是在首位置出現(xiàn)、出現(xiàn)當前詞性時出現(xiàn)了當前單詞的次數(shù)、上一個詞性到當前詞性的組合出現(xiàn)的次數(shù)，對三大矩陣進行不斷累加，訓練完畢后將其概率化，即除以矩陣當前行數(shù)組總長，將當前數(shù)字轉(zhuǎn)化為0-1之間的概率數(shù)字。

4)實現(xiàn)維特比算法的函數(shù)。輸入?yún)?shù)為所要預(yù)測的句子x、三大矩陣、最終預(yù)測總數(shù)組arr。將預(yù)測好的詞性標注情況逐一增加到最終預(yù)測總數(shù)組中，以便于最后求解準確度。并且在其中將矩陣間的乘積提前進行對數(shù)化，將乘積化為加和，簡化運算，以加快運算速度[14]。實現(xiàn)細節(jié)如下所示：

5)使用校驗集來對所訓練好的三大矩陣進行運算，將校驗集切分為一個個的句子，不斷地使用維特比算法進行計算，每次計算完都會將預(yù)測出的詞性標注情況加入到最終預(yù)測總數(shù)組中，最后與校驗集原有的正確標注進行對比，得出準確率。實現(xiàn)細節(jié)如下：

3.2 條件隨機場模型實驗

對于使用條件隨機場進行詞性標注模擬實現(xiàn)，這里使用的是Sklearn_crfsuite庫來對參數(shù)進行學習和訓練，同時為確保結(jié)果對比的有效性，訓練集和校驗集選用的仍然是和HMM相同的數(shù)據(jù)庫。

1)進行數(shù)據(jù)集讀取。將訓練集和校驗集分割成一個個句子，由于句子之間是沒有聯(lián)系的，所以可以以每個句子為單獨樣本來進行實驗。將各個句子的單詞、詞性信息加入到train_sents和test_sents數(shù)組中。

2)進行特征方程的構(gòu)造。這里用6組實驗，利用不同的思想構(gòu)造了特征方程，下面分別介紹這6組特征方程組。

①對word2features0特征方程組，使用的是較為共有的特性，例如是否為數(shù)字、末尾幾個字母是否相同、首字母是否為大寫等特性，來進行參數(shù)訓練。如下：

②對word2features1特征方程組進一步思考是否可以將較為普遍的共性進行具體化。根據(jù)這個思想，通過廣泛搜集信息，找到并整理出了較為完整的詞性后綴集合，通過對后綴的具體要求來構(gòu)造特征方程，將共性進行具體化[15]，部分構(gòu)造代碼如下：

③對于word2features2特征方程組，在word2 features1的基礎(chǔ)上，將后n個字母相同的偏向共性的條件注釋掉，只保留后綴對詞性的要求，來分辨后n個字母相同的條件和具體后綴的條件是否會因為有重疊而影響詞性預(yù)測準確率。

④對于word2features3特征方程組，保留后n個字母相同的條件和相對其他后綴來說較為共性的特殊后綴，觀察更加共性是否是影響詞性預(yù)測準確率的關(guān)鍵條件，特殊后綴構(gòu)造代碼如下：

# 特殊后綴

⑤對于word2features4特征方程組，保留后1、2、3、4個字母相同的條件，以及后綴為5個字母及以上的具體后綴條件，觀察詞性預(yù)測準確率，構(gòu)造代碼如下:

⑥對于word2features5特征方程組，根據(jù)word2 features4的構(gòu)造情況進行對比，保留后1、2、3個字母相同的條件，以及后綴為4個字母及以上的具體后綴條件，觀察詞性預(yù)測準確率。

3)根據(jù)Sklearn_crfsuite庫的要求，構(gòu)造三維數(shù)組參數(shù)。其中，對于訓練集，第一維為每個句子，第二維為每個句子中的每個單詞，第三維為每個單詞所擁有的特性。這里的特性就是用第二步的特征方程來判斷出來的是否符合各個特征方程的布爾值。對于校驗集，第三維為每個單詞所擁有的正確詞性標注，用于最后判斷預(yù)測詞性標注的準確性。

4)使用Sklearn_crfsuite庫中的API并傳入相應(yīng)的參數(shù)，使用擬牛頓法進行參數(shù)學習，使用維特比算法進行詞性預(yù)測，并將結(jié)果與校驗集進行比對，若標注的詞性相同，則same+=1，最后將same除以標注總數(shù)sum，求出最終準確率，代碼實現(xiàn)如下：

3.3 實驗結(jié)果分析

經(jīng)過隱馬爾可夫模型以及條件隨機場的各個不同的特征方程對相同訓練集進行訓練以及相同校驗集進行校驗，得出準確率的結(jié)果如表1和表2所示。

表1 數(shù)據(jù)庫1詞性預(yù)測準確率結(jié)果

表2 數(shù)據(jù)庫2詞性預(yù)測準確率結(jié)果

可以看出，2個數(shù)據(jù)庫中隱馬爾可夫模型的準確率都是完全低于條件隨機場的，證明了條件隨機場模型更適用于詞性標注問題，也證明了條件隨機場對于解決詞性標注問題的全面性和靈活性。

對于條件隨機場模型不同特征方程之間的比較，可以看出2個數(shù)據(jù)庫中word2features4所達到的準確率最高，也就是說，使用相對共性籠統(tǒng)的后n個字母相同加上相對具體的n+1及n+1以上個字母的后綴結(jié)合使用所達到的準確率最高。同時，2個數(shù)據(jù)庫中word2features2所達到的準確率在條件隨機場模型中都是最小的，也就表明若不用相對共性的后n個字母相同的方法構(gòu)造特征函數(shù)，而只用后綴法來構(gòu)造特征函數(shù)時，準確率會降低，也就是說，共性構(gòu)造是不可少的一部分，可以大大提高預(yù)測準確率。

綜上所述，在進行英文詞性標記時，條件隨機場模型表現(xiàn)出更好的效果，相對其他模型有著更準確的預(yù)測。同時，選擇使用相對共性的后n個字母相同加上相對具體的n+1及n+1以上個字母的后綴結(jié)合使用所達到的準確率最高。

4 結(jié)論

本文對隱馬爾可夫模型和條件隨機場模型進行了模擬實驗，同時使用條件隨機場的不同特征方程進行了多組實驗，并對比了每組實驗的準確率。結(jié)果表明，條件隨機場對于解決英文詞性標注問題有著更大的優(yōu)勢，并且將共性的特征與相對具體的后綴特征結(jié)合使用所達到的詞性標注準確率最高。