基于感知器算法的維吾爾語詞性標(biāo)注研究

帕提古力·依馬木，買合木提·買買提，吐爾根·依布拉音，卡哈爾江·阿比的熱西提

(新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046)

1 引言

目前基于統(tǒng)計(jì)的詞性標(biāo)注方法得到了廣泛的應(yīng)用并取得了良好的效果。在基于統(tǒng)計(jì)方法的詞性標(biāo)注中，對兼類詞和未登錄詞的處理是需要解決的問題。對兼類詞和未登錄詞，可以根據(jù)詞的上下文信息來確定詞在句子中的詞性。

維吾爾語屬黏著語, 其形態(tài)變化比較豐富。名詞有數(shù)、格、人稱等語法范疇; 動(dòng)詞有數(shù)、人稱、時(shí)態(tài)、語態(tài)的變化; 形容詞有級的范疇。形態(tài)變化一方面提供了一些深層語法信息, 為詞法分析、詞性標(biāo)注帶來極大的方便, 另一方面也增加了自動(dòng)標(biāo)注的復(fù)雜性。維吾爾語同其他語言一樣也存在詞性歧義現(xiàn)象(詞兼類現(xiàn)象)。在維吾爾語中兼類詞數(shù)量較多，且使用頻率較高，這給維吾爾語詞性標(biāo)注帶來了很大的困難。兼類現(xiàn)象是詞性標(biāo)注中的一個(gè)不可回避的重點(diǎn)和難點(diǎn)，詞性是詞的重要的語法信息，假如一個(gè)詞的詞性無法確定，對后續(xù)句法分析造成直接的影響，句法分析就無法進(jìn)行。如果一個(gè)詞賦予錯(cuò)誤的詞性，將導(dǎo)致嚴(yán)重的句法分析錯(cuò)誤，所以，維吾爾語詞性標(biāo)注在自然語言處理中有至關(guān)重要的意義。本文使用感知器算法進(jìn)行維吾爾語的詞性標(biāo)注。目前基于感知器算法的模型在各個(gè)領(lǐng)域都表現(xiàn)出很好的性能，本文主要利用感知器算法的優(yōu)點(diǎn)，在進(jìn)行詞性標(biāo)注時(shí)利用詞的上下文信息作為特征，在維吾爾語詞性標(biāo)注中取得了好的效果。

2 相關(guān)工作

目前詞性標(biāo)注方法可分為3類： 基于規(guī)則的詞性標(biāo)注方法、基于轉(zhuǎn)換的錯(cuò)誤驅(qū)動(dòng)詞性標(biāo)注方法以及基于統(tǒng)計(jì)的詞性標(biāo)注方法。

1) 基于規(guī)則的詞性標(biāo)注方法

基于規(guī)則的詞性標(biāo)注方法首先由語言學(xué)家制定相應(yīng)的規(guī)則，在規(guī)則中使用大量的上下文信息來對詞性進(jìn)行判斷。詞性標(biāo)注的性能與規(guī)則制定者的語言學(xué)知識具有很大的關(guān)系。其次要構(gòu)造一套對語言的各方面特性都覆蓋的規(guī)則是一個(gè)艱難耗時(shí)的工作，而且隨著規(guī)則數(shù)量的增加，各規(guī)則之間往往會(huì)產(chǎn)生沖突。最具有代表性的基于規(guī)則的詞性標(biāo)注系統(tǒng)是 1971 年開發(fā)的 TAGGIT 標(biāo)注系統(tǒng)[1]。對于維吾爾語來說，基于規(guī)則的詞性標(biāo)注有吐爾根等開發(fā)的基于詞典的維吾爾語詞性標(biāo)注系統(tǒng)[2]。

2) 基于轉(zhuǎn)換的錯(cuò)誤驅(qū)動(dòng)詞性標(biāo)注方法

為了克服手工制定規(guī)則帶來的問題，1995 年 Eric Brill 提出了基于轉(zhuǎn)換的錯(cuò)誤驅(qū)動(dòng)的詞性標(biāo)注方法[3]。該方法最初用于英語的詞性標(biāo)注，基本處理步驟是: 首先為每個(gè)句子賦以初始詞性序列，然后通過將這些句子與正確詞性標(biāo)注的句子相比較，自動(dòng)學(xué)習(xí)一些結(jié)構(gòu)轉(zhuǎn)換規(guī)則，最后將這些規(guī)則作用于新的被賦以同樣初始詞性序列的句子上，就可以得到正確的詞性標(biāo)注。重復(fù)以上的過程直到不再獲取新的轉(zhuǎn)換規(guī)則，這樣就可以構(gòu)建一個(gè)詞性標(biāo)注規(guī)則集[4]。該方法的優(yōu)勢在于能有效地利用語言的詞和語法的規(guī)則以及一定的上下文信息。實(shí)驗(yàn)結(jié)果顯示，此方法可以用較小的訓(xùn)練集達(dá)到較高的分析準(zhǔn)確度。

3) 基于統(tǒng)計(jì)的詞性標(biāo)注方法

基于統(tǒng)計(jì)的方法是目前應(yīng)用最廣泛的詞性標(biāo)注方法?；诮y(tǒng)計(jì)的詞性標(biāo)注方法將詞性標(biāo)注看作是一個(gè)序列標(biāo)注問題，為每一個(gè)詞語賦予一個(gè)正確的候選詞性?；诮y(tǒng)計(jì)的詞性標(biāo)注有基于隱馬爾科夫模型的詞性標(biāo)注方法、基于最大熵的詞性標(biāo)注方法、基于支持向量機(jī)的詞性標(biāo)注方法、基于條件隨機(jī)場的詞性標(biāo)注方法等。在基于統(tǒng)計(jì)的維吾爾語詞性標(biāo)注方面，文獻(xiàn)[5]提出基于N元模型的維吾爾詞性自動(dòng)標(biāo)注方法,使用N元語法模型和動(dòng)態(tài)規(guī)劃的方法進(jìn)行維吾爾語的詞性標(biāo)注，在測試中把訓(xùn)練語料庫和測試語料庫的比例設(shè)置為19∶1，并分析了二元,三元模型對維吾爾語詞性標(biāo)注的效率。訓(xùn)練和測試語料庫的規(guī)模差距較大，該測試基本上接近于封閉測試。根據(jù)文獻(xiàn)[6]的錯(cuò)誤分析，模型性能下降的主要原因是未登錄詞較多。實(shí)際上，大多數(shù)未登錄詞在訓(xùn)練庫里已有詞干形式，只是因?yàn)樵~干附加了詞綴發(fā)生形態(tài)變化導(dǎo)致模型與訓(xùn)練庫的匹配失敗。文獻(xiàn)[7]中提出基于條件隨機(jī)場的詞性標(biāo)注方法,有效地利用了所有可用的信息，并選擇不同的模板進(jìn)行試驗(yàn)。最后選用模板C建立基于條件隨機(jī)場的維吾爾語詞性標(biāo)記標(biāo)注模型。文獻(xiàn)[7]還提出基于混合策略的維吾爾語詞性標(biāo)注并取得了良好的結(jié)果。常見的基于統(tǒng)計(jì)的方法還有神經(jīng)元網(wǎng)絡(luò)、決策樹、線性分離網(wǎng)絡(luò)標(biāo)注模型等等。

3 訓(xùn)練算法和特征選擇

本文主要用感知器算法進(jìn)行訓(xùn)練并根據(jù)維吾爾語的特點(diǎn)選擇特征。以下詳細(xì)介紹感知器算法和選擇的特征。

3.1 感知器算法

目前基于統(tǒng)計(jì)的方法是詞性標(biāo)注、文本識別等方面的主流方法。在基于統(tǒng)計(jì)的方法中，問題被描述為統(tǒng)一的序列標(biāo)注問題，即給定一個(gè)觀測序列X=(x1,x2,…,xn)，需要求解最優(yōu)的標(biāo)記序列Y=(y1,y2,…,yn)。 其中一類方法從概率的角度來估計(jì)X和Y的概率分布，這類方法常用的統(tǒng)計(jì)模型有最大熵模型(Maximum Entropy Model，ME)[8]，隱馬爾科夫模型(Hidden Markov Model，HMM)[9]以及條件隨機(jī)場模型(Condition Random Fields Model，CRF)[10]等。在另一類序列標(biāo)注算法中，定義觀測序列X=(x1,x2,…,xn)對應(yīng)狀態(tài)序列Y=(y1,y2,yn)的分?jǐn)?shù)(score)為式(1)所示。

(1)

其中fn(X,Y)為特征函數(shù)，wn為第n個(gè)特征對應(yīng)的權(quán)重。

當(dāng)特征函數(shù)取特定值時(shí)，則該模板被實(shí)例化，得到具體的特征。特征值一般可以定義為下面的一個(gè)二值函數(shù)形式：

給定觀測序列X=(x1,x2,…,xn)，最好的狀態(tài)序列Y為score最大的狀態(tài)序列，即式(2)所示。

Y=argmaxY′score(X,Y′)

(2)

當(dāng)通過訓(xùn)練得到每個(gè)特征對應(yīng)的權(quán)重后，我們可以使用動(dòng)態(tài)規(guī)劃算法快速得到score最大的狀態(tài)序列。

在線算法[11]是一種常用的訓(xùn)練算法，在在線算法中，每次僅僅使用一個(gè)實(shí)例對參數(shù)進(jìn)行更新，而不像梯度下降之類的批處理訓(xùn)練算法，每次更新參數(shù)都需要用到所有的訓(xùn)練語料，導(dǎo)致對資源的巨大消耗。感知器算法[12]是一種典型的在線算法。感知器算法每次使用一個(gè)訓(xùn)練實(shí)例對模型參數(shù)進(jìn)行更新，在更新參數(shù)時(shí)每次將需要更新的參數(shù)重加 1 或者減 1。感知器算法的代碼如下所示：

Input:Trainingexamples(xi,yi)

Algorithm:Fort=1 ..T,i=1..n

zi=F(xi),

為了防止模型對數(shù)據(jù)的過擬合，常對參數(shù)進(jìn)行平均化操作，即Average Perceptron 算法。

算法的表達(dá)形式如圖1所示。

圖1 算法的表達(dá)形式

(3)

用簡單的例子描述感知器算法在維吾爾語詞性標(biāo)注的過程:

gold-standard: NB MI AO NB VN ?(x,y)

Yiraqtin bir qara at k?liwatatti

current output : NB MI AO VN VN ?(X,Z)

Yiraktin bir qara at k?liwatatti

上述例子假設(shè)有以下的特征:

詞性 ti-1ti;詞/詞性組合Wi/ti 根據(jù)上面的算法，對參數(shù)進(jìn)行更新。

weights ++: (AO, NB)( NB→at)

weights --: (AO, VN)( VN→at)

通過感知器訓(xùn)練算法得到每個(gè)特征對應(yīng)的權(quán)重后，我們可以使用動(dòng)態(tài)規(guī)劃算法快速得到最優(yōu)的狀態(tài)序列。

3.2 特征選擇

特征選擇是指針對特定的任務(wù)，為模型選取特征集合。詞性的正確判斷依賴于可靠的特征信息。維吾爾語詞性自動(dòng)標(biāo)注模型的關(guān)鍵是利用對詞性歧義消除的特征構(gòu)建特征模塊，盡量減少?zèng)_突的特征。根據(jù)維吾爾語的語言知識，維吾爾語詞的結(jié)構(gòu)，形態(tài)等特征信息與詞性的關(guān)系以及維吾爾語的語法特點(diǎn)，本文中主要使用的基本特征如表1所示。

表1 基本特征表

4 解碼算法

本文中使用Viterbi算法快速地得到最優(yōu)的狀態(tài)序列。Viterbi算法是基于動(dòng)態(tài)規(guī)劃(Dynamic Programming)的思想，找“正確”的狀態(tài)序列--詞性。具體的就是先解決最基本的子問題，然后再尋找整個(gè)問題即最優(yōu)解。對已知詞序列w1,w2…wm，詞性標(biāo)記序列t1t2…tm，尋找該詞序列上可能性最優(yōu)的詞性序列c1c2…cm。

Viterbi 算法有三個(gè)步驟： (1)初始化； (2)推導(dǎo)； (3)終止和讀取路徑(最優(yōu)解)。下面給出標(biāo)準(zhǔn)的Viterbi算法：

定義一個(gè)局部概率θm(i)，它表示的是時(shí)刻t到達(dá)狀態(tài)Ci的所有序列概率中最大的概率。再定義一個(gè)反向指針μm(i)，它用來表示的是時(shí)刻t到達(dá)最佳狀態(tài)ci的路徑。

(1) 初始化：t=1，表示所處狀態(tài)ci的初始概率

(2) 推導(dǎo)階段

遞歸計(jì)算通向詞wm的詞性標(biāo)記ci的最佳路徑

(3) 終止和讀取路徑(最優(yōu)解)

終止，即到達(dá)最后一個(gè)詞wm時(shí)的最佳詞性標(biāo)注

P=max[θt(i)]cm=argmax[θt(i)] 1≤i,j≤N

從最后一個(gè)詞wm開始，回退求取每個(gè)詞的最佳狀態(tài)序列：

cm=θm+1(cm+1)m=M-1M-2, ………1

這樣可以得到最優(yōu)詞性標(biāo)序列c1c2…cm

5 實(shí)驗(yàn)與分析

維吾爾語中有名詞、形容詞、數(shù)詞、代詞、副詞、量詞、連詞、語氣詞、嘆詞、后置詞、動(dòng)詞等12個(gè)詞類。新疆大學(xué)多語種信息技術(shù)實(shí)驗(yàn)室自然語言處理組對維吾爾語規(guī)則進(jìn)行深入研究，結(jié)合實(shí)際文本制定了現(xiàn)代維吾爾語詞性標(biāo)注集(共計(jì)137個(gè)一級標(biāo)注，71個(gè)二級標(biāo)注，51個(gè)三級標(biāo)注)，該標(biāo)注集主要用于新疆大學(xué)多語種信息技術(shù)實(shí)驗(yàn)室將要研究的維吾爾語詞法分析器、句法分析器、機(jī)器翻譯等領(lǐng)域。本實(shí)驗(yàn)主要使用新疆大學(xué)自然語言處理實(shí)驗(yàn)室構(gòu)建的維吾爾語語料庫，此語料庫已進(jìn)行人工標(biāo)注。為了更好地評價(jià)維吾爾文詞性自動(dòng)標(biāo)注的結(jié)構(gòu)，采用計(jì)算正確率。表達(dá)式如下：

詞性自動(dòng)標(biāo)注正確率=(標(biāo)注結(jié)果正確詞數(shù)/語料的總詞數(shù))×100%

為了說明不同方法的優(yōu)劣，所以選擇了其他方法的實(shí)驗(yàn)結(jié)果與之比較。

實(shí)驗(yàn)結(jié)果如表2所示。

表2 維吾爾語詞性自動(dòng)標(biāo)注算法比較結(jié)果

從上面的例子和表2可以看出，感知器算法對維吾爾語詞性標(biāo)注有更大的貢獻(xiàn)。

6 總結(jié)

本文使用基于感知器算法的序列標(biāo)注方法進(jìn)行詞性標(biāo)注。本方法具有在線算法的優(yōu)點(diǎn)，它可以充分利用多個(gè)任意的特征并每次使用一個(gè)訓(xùn)練實(shí)例對模型參數(shù)進(jìn)行更新，在更新參數(shù)時(shí)每次將需要更新的參數(shù)重加1或者減1。這個(gè)優(yōu)點(diǎn)對維吾爾語詞性標(biāo)注尤其是標(biāo)注中處理詞性歧義(兼類現(xiàn)象)有很大的貢獻(xiàn)。目前根據(jù)維吾爾語的特點(diǎn)，選擇考慮詞的上下文信息的特征，使維吾爾語詞性標(biāo)注方法能夠取得很好的標(biāo)注效果。雖然標(biāo)注效果好，但還是需要加其他的特征并用別的訓(xùn)練測試比例進(jìn)行實(shí)驗(yàn)。因此今后將進(jìn)一步擴(kuò)充語料庫規(guī)模，同時(shí)加入更多的特征信息進(jìn)行研究。

[1] 吐爾根·依不拉音，阿里甫·庫爾班.基于詞典的現(xiàn)代維吾爾語詞性自動(dòng)標(biāo)注系統(tǒng)的研究[A].中文輸入技術(shù)發(fā)展歷程及輸入方案匯編(論文集)[C]，2006.11.

[2] Màrquez, Lluís, LluisPadro et al. A Machine Learning Approach to POS Tagging. Machine Learning 2000，39(1)： 59-91.

[3] Brill Eric. Transformation-based Error-driven Learning and Natural Language Processing: A Case Study in Part-of-speech Tagging. Computational linguistics.1995,21(4): 543-565.

[4] 周明, 吳進(jìn), 黃昌寧. 用于詞性標(biāo)注的一種快速學(xué)習(xí)算法對Brill 的基于變換算法的一項(xiàng)改進(jìn)[J]. 計(jì)算機(jī)學(xué)報(bào),1998 (4) : 357-366

[5] 買合木提·買買提，吐爾根·依布拉音.基于n‐gram 的維吾爾語詞性標(biāo)注研究[C]//第二屆中國少數(shù)民族青年自然語言處理學(xué)術(shù)研討會(huì).2008 年10 月，中國安徽合肥.2008： 185-189.

[6] 艾斯卡爾·亞克甫,肖克來提,玉素甫·艾白都拉.維吾爾語詞頻統(tǒng)計(jì)子系統(tǒng)的體系結(jié)構(gòu)[J].新疆師范大學(xué)學(xué)報(bào) (自然科學(xué)版)2006,25(2): 16-20

[7] 艾山·吾買爾·維吾爾語詞法句法分析關(guān)鍵技術(shù)的研究[D].博士論文，新疆大學(xué)，2010年.

[8] Ratnaparkhi A. A Maximum Entropy Model for Part-of-speech Tagging[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing. 1996, 1: 133-142.

[9] Dobrushin R L. Central Limit Theorem for Nonstationary Markov Chains[J]. Theory of Probability & Its Applications, 1956, 1(1): 65-80.

[10] Lafferty John, Andrew McCallum, Fernando CN Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. ICML 18(2001): 45-54.

[11] Manshadi V H, Gharan S O, Saberi A. Online Stochastic Matching: Online Actions Based on Offline Statistics[J]. Mathematics of Operations Research, 2012, 37(4): 559-573.

[12] Freund Y, Schapire R E. Large Margin Classification Using the Perceptron Algorithm [J]. Machine Learning, 1999, 37(3): 277-296.