基于歷史模型的蒙古文自動詞性標(biāo)注研究

趙建東，高光來，飛 龍

（內(nèi)蒙古大學(xué) 計算機(jī)學(xué)院，內(nèi)蒙古 呼和浩特010021）

1 引言

詞性標(biāo)注是自然語言處理領(lǐng)域的基礎(chǔ)性研究課題之一，該項研究對于機(jī)器翻譯、語法分析、語義分析等領(lǐng)域的研究有著重要的意義。在漢語、英語等方面已經(jīng)有了許多自動詞性標(biāo)注方面的研究，采用的方法主要有基于轉(zhuǎn)換［1]、隱馬爾科夫模型［2]、支持向量機(jī)［3]、最大熵模型［4]等方法。

蒙古文作為少數(shù)民族語言，詞性標(biāo)注的研究開始較晚，研究工作也比較少。目前為止，胡冠龍等人做了改進(jìn)的基于轉(zhuǎn)換方法的拉丁蒙文詞性標(biāo)注［5]；艷紅等用基于隱馬爾科夫模型（HMM）的方法對蒙古語自動詞性標(biāo)注進(jìn)行了研究［6]；張貫紅等人做了最大熵蒙古文詞性標(biāo)注的研究［7]等。這些工作對于研究蒙古文的自動標(biāo)注具有重要的作用，但是每種方法都有一些不足。基于轉(zhuǎn)換的蒙古文詞性標(biāo)注方法，是一種基于規(guī)則的方法，這種方法通常采用手工來編制復(fù)雜的詞性標(biāo)注規(guī)則系統(tǒng)，可以充分利用人的語言知識，但是帶有很強(qiáng)的主觀性，容易產(chǎn)生規(guī)則沖突，對語言學(xué)專家的依賴性強(qiáng)，存在知識獲取的瓶頸問題，并且加工、調(diào)試規(guī)則費時費力?；贖MM的蒙古文詞性標(biāo)注方法是基于統(tǒng)計的方法，由于人工標(biāo)注訓(xùn)練語料庫的易得性和統(tǒng)計模型的健壯性，使它成為主流的詞性標(biāo)注方法，但是這種方法無法使用復(fù)雜特征，對未登錄詞詞性標(biāo)注的準(zhǔn)確率較低，而蒙古文中外來詞匯量很大，這需要尋求其他方法來進(jìn)行改善。最大熵模型能夠較好的包容各種約束信息及與自然語言模型相適應(yīng)等優(yōu)點，在蒙古文詞性標(biāo)注研究中取得了比較好的效果。但算法收斂的速度較慢，所以導(dǎo)致它的計算代價較大，時空開銷大，而且數(shù)據(jù)稀疏問題比較嚴(yán)重。針對這些問題本文用加入lookahead學(xué)習(xí)機(jī)制的基于歷史模型的方法研究了蒙古文自動詞性標(biāo)注，這種方法具有HMM模型和最大熵模型的優(yōu)點。通過與基于最大熵模型的方法進(jìn)行對比，實驗結(jié)果表明，加入lookahead學(xué)習(xí)機(jī)制的基于歷史模型的蒙古文自動詞性標(biāo)注方法優(yōu)于基于最大熵模型的蒙古文詞性標(biāo)注方法。這對于進(jìn)一步研究蒙古文自動詞性標(biāo)注具有重要的意義。

本文的結(jié)構(gòu)安排如下，第2節(jié)詳細(xì)介紹基于歷史模型的詞性標(biāo)注的方法，第3節(jié)為蒙古文自動詞性標(biāo)注實驗，最后一節(jié)為結(jié)論。

2 基于歷史模型的詞性標(biāo)注方法

2.1 基于歷史模型的發(fā)展

基于歷史模型的方法［8]已經(jīng)被廣泛應(yīng)用于詞性標(biāo)注等一系列的自然語言處理任務(wù)中。它的思想是將復(fù)雜的結(jié)構(gòu)預(yù)測問題分解成一系列的分類問題，并把過去的決策和部分完成的結(jié)構(gòu)信息作為特征，然后用基于機(jī)器學(xué)習(xí)的分類器來做每一個決策?；跉v史模型的方法有很多優(yōu)點，但是，由于標(biāo)注偏置問題在詞性標(biāo)注等方面的準(zhǔn)確率經(jīng)常不如全局優(yōu)化的方法。近年來基于全局優(yōu)化模型的方法越來越流行，但同時也暴露出了計算復(fù)雜度高的缺點。

研究［9]發(fā)現(xiàn)，在決策過程中采用lookahead學(xué)習(xí)機(jī)制可以顯著地提高基于歷史模型方法的準(zhǔn)確率。這里的lookahead和句法分析中的“l(fā)ookahead”的含義不同，句法分析中的“l(fā)ookahead”是根據(jù)觀察正確的詞來選擇正確的解析操作。這里的lookahead是指選擇最佳操作的過程，在這個過程中要考慮未來操作的不同序列，并評價由這些序列構(gòu)成的結(jié)構(gòu)。換句話說，就是在未來的操作空間執(zhí)行搜索時采用了lookahead機(jī)制。

2.2 “移進(jìn)—歸納”分析器

為了介紹基于歷史模型中的lookahead，先簡單介紹一個基于歷史模型的依存分析方法的例子—“移進(jìn)—歸納”分析器?！耙七M(jìn)—歸納”算法主要包含堆棧和隊列兩種數(shù)據(jù)結(jié)構(gòu)。堆棧用來儲存中間的解析結(jié)果，隊列用來儲存讀取的單詞。移進(jìn)和歸納兩種操作方式在這兩種數(shù)據(jù)結(jié)構(gòu)中構(gòu)成一個接一個的關(guān)系。通過移進(jìn)和歸納操作，“移進(jìn)—歸納”分析器從單詞序列中讀取單詞并且構(gòu)建一個依存關(guān)系樹，同時把依存關(guān)系儲存在堆棧中。我們在一個狀態(tài)時，通常不知道是應(yīng)該選擇移進(jìn)還是歸納。傳統(tǒng)的方法是用多級分類器去決定下一個操作，分類器要根據(jù)堆棧和隊列中詞的表面形態(tài)、詞性等信息去選擇最合理的操作。

在lookahead策略中，是根據(jù)未來的狀態(tài)去做出決定。由于未來的狀態(tài)能夠提供更多的附加信息或者有用的消歧信息，所以從理論上講用這種方法可以提高準(zhǔn)確率。但是，這樣也會帶來一些問題，隨著lookahead的深度的增加，lookahead方法的計算代價會增加。不過這種代價被證明是有價值的。

2.3 Lookahead學(xué)習(xí)機(jī)制

我們用狀態(tài)表示部分完成的分析，相當(dāng)于基于歷史的確定性分析中在每個決策點收集的歷史信息，狀態(tài)還可以根據(jù)允許的操作來進(jìn)行轉(zhuǎn)移。在詞性標(biāo)注中，狀態(tài)就是單詞，我們需要將詞性的標(biāo)簽分配給當(dāng)前的目標(biāo)單詞，允許的可能的操作就是詞性集合中的所有詞性標(biāo)簽。

2.3.1 搜索算法

在lookahead學(xué)習(xí)機(jī)制中需要一個搜索算法來搜索每個可能的操作，圖1為搜索算法的偽代碼。該算法采用深度優(yōu)先策略執(zhí)行搜索，在狀態(tài)空間中找到得分最高的狀態(tài)，搜索復(fù)雜度由深度d決定。這個搜索過程是執(zhí)行一個遞歸函數(shù)，遞歸函數(shù)以剩余的搜索深度和當(dāng)前的狀態(tài)作為它的輸入，最終以得分最高的狀態(tài)及其得分作為返回值。假設(shè)一個線性得分模型，每個狀態(tài)S的得分就是當(dāng)前的權(quán)值向量ω和代表狀態(tài)的特征向量Φ（S）的點積。得分從搜索樹的每個葉子節(jié)點開始計算并將其備份到根節(jié)點（在詞性標(biāo)注等實際應(yīng)用中，如果每次都從葉子節(jié)點開始計算，這樣效率會太低，所以通常是狀態(tài)每次被一個操作更新時就直接計算得分的增量，以此來得到每個狀態(tài)的得分）。采用這種搜索算法進(jìn)行標(biāo)注的時間復(fù)雜度是O（nmD＋1），其中n是處理句子需要的操作次數(shù)，m是每個狀態(tài)可能的平均操作數(shù)。D是搜索的深度。由于這種搜索的方式是基于歷史的，所以并不需要局部的特征，即我們可以根據(jù)任意的特征進(jìn)行決策?？梢哉f這種學(xué)習(xí)的機(jī)制權(quán)衡了全局最優(yōu)參數(shù)學(xué)習(xí)和特征的靈活選擇性。分從搜索樹的葉子節(jié)點就開始被備份。研究證明如果訓(xùn)練數(shù)據(jù)是線性可分的，則這種訓(xùn)練算法是收斂的，并且邊界最后至少能達(dá)到真正邊界的一半［9]。同許多采用感知器的研究［11]一樣，文中采用的訓(xùn)練算法在整個訓(xùn)練迭代結(jié)束時，也將權(quán)值向量進(jìn)行了平均。

3 蒙古文自動詞性標(biāo)注實驗

圖1 搜索算法

2.3.2 訓(xùn)練一個邊緣感知機(jī)

為了優(yōu)化lookahead搜索算法中的權(quán)值，我們采用了邊緣感知機(jī)的學(xué)習(xí)算法［10]。邊緣感知機(jī)和支持向量機(jī)類似，與沒有采用邊緣的感知機(jī)相比，它能夠產(chǎn)生更加精確的模型。圖2給出了我們采用的學(xué)習(xí)算法的偽代碼。這個學(xué)習(xí)算法與標(biāo)準(zhǔn)的邊緣感知機(jī)的訓(xùn)練算法相似，即當(dāng)感知機(jī)出現(xiàn)錯誤時，我們用兩個不同的特征向量來更新權(quán)值，一個特征向量對應(yīng)正確的操作；另一個特征向量對應(yīng)得分最高的操作，當(dāng)邊緣不足夠大的時候，也可以對應(yīng)為得分次最高的操作。需要注意的是次最優(yōu)操作向量可以用正確操作的得分減去邊緣距離這樣一個簡單的技巧而自動選擇，即圖2中的第13行。這種權(quán)值更新算法與邊緣感知機(jī)的標(biāo)準(zhǔn)算法相比，唯一不同的是，這種算法用到了根據(jù)lookahead搜索算法得到的狀態(tài)以及狀態(tài)的得分（圖2中第11行），這些狀態(tài)及其得

圖2 感知機(jī)權(quán)值更新算法

3.1 語料庫的構(gòu)建

蒙古文是一種拼音文字，它的拼寫規(guī)則是以詞為單位豎寫，詞與詞之間用空格分開，采取從上到下的書序，從左到右的行序。蒙古文字母在詞中變化有很多，在一個蒙古文單詞中，蒙古文字母在上、中、下位置不同而導(dǎo)致的寫法也不同，并且蒙古文字母中形同音不同的現(xiàn)象比較普遍。鑒于蒙古文中元音與輔音的形式變化多樣問題，對蒙古文進(jìn)行處理時，通常采用拉丁轉(zhuǎn)寫的方法。這樣有助于蒙古文的校正、統(tǒng)計和研究。

構(gòu)建語料庫時，我們選取了10990句蒙古文句子，先根據(jù)轉(zhuǎn)換規(guī)則將蒙古文轉(zhuǎn)到拉丁轉(zhuǎn)寫，再進(jìn)行詞性標(biāo)注。采用的詞性主要有：語氣詞、名詞、動詞、連詞、副詞、形容詞、數(shù)詞、量詞、后置詞、構(gòu)成附加成分、模擬詞、情態(tài)詞、感嘆詞、時位詞、時間詞、不確定詞、復(fù)合詞、代詞、標(biāo)點。實驗方法是隨機(jī)選取其中的9900句作為訓(xùn)練語料，剩余的1090句作為測試語料，詳細(xì)的實驗數(shù)據(jù)如表1所示。

表1 實驗數(shù)據(jù)

3.2 實驗結(jié)果

我們用加入lookahead學(xué)習(xí)機(jī)制的基于歷史模型的方法進(jìn)行了蒙古文自動詞性標(biāo)注實驗，工具為lapos［12]。為了評價蒙古文自動標(biāo)注系統(tǒng)性能，主要采用詞性標(biāo)注正確率進(jìn)行評價，如式（1）所示。

為了研究這種方法中搜索深度和邊緣對蒙古文自動詞性標(biāo)注準(zhǔn)確率的影響，我們進(jìn)行了多組交叉實驗，實驗中深度分別設(shè)定為1、2、3、4、5，邊緣分別設(shè)定為0、20、40、60、80、100、120。實驗的結(jié)果如圖3所示。

圖3 蒙古文自動詞性標(biāo)注準(zhǔn)確率實驗結(jié)果

分析圖3，我們可以得到幾個信息：（1）當(dāng)感知機(jī)邊緣小于等于60的時候，準(zhǔn)確率隨深度變化而變化的幅度較大，說明邊緣小時模型不穩(wěn)定，所以為使模型穩(wěn)定需要增大邊緣；（2）隨著邊緣的增大，模型趨于穩(wěn)定。但是當(dāng)大于等于80的時候，再增大邊緣對于準(zhǔn)確率的影響不大；（3）在邊緣適宜的時候，深度對于集內(nèi)詞和總體詞詞性標(biāo)注的準(zhǔn)確率的影響并不是很大，相比對于未登錄詞的影響要稍大些。從本文第2節(jié)我們知道增大深度會增加搜索時間的復(fù)雜度，綜合這些信息，深度為3、邊緣為100時，本文的模型表現(xiàn)最佳，此時未登錄詞、集內(nèi)詞、總體詞詞性自動標(biāo)注的準(zhǔn)確率分別達(dá)到了71.2766%、99.1482%、95.3010%。

為了將本文提出的加入lookahead學(xué)習(xí)機(jī)制的基于歷史的蒙古文自動詞性標(biāo)注方法與基于最大熵模型的蒙古文自動詞性標(biāo)注方法進(jìn)行比較，我們用相同的實驗數(shù)據(jù)做了一些基于最大熵模型的蒙古文自動詞性標(biāo)注實驗，采用工具是maxent［13]。實驗結(jié)果如表2所示。

從表2中可以看出，當(dāng)?shù)螖?shù)為60的時候，最大熵詞性標(biāo)注方法的準(zhǔn)確率達(dá)到最好的效果，此時未登錄詞、集內(nèi)詞、總體詞詞性自動標(biāo)注的準(zhǔn)確率分別達(dá)到了70.2128%、93.5264%、90.3084%。圖4中給出了這兩種方法在表現(xiàn)最佳的情況下的準(zhǔn)確率對比結(jié)果。從中可以看出加入lookahead學(xué)習(xí)機(jī)制的基于歷史模型的蒙古文自動詞性標(biāo)注的準(zhǔn)確率要高于基于最大熵模型的蒙古文自動詞性標(biāo)注的準(zhǔn)確率。

表2 基于最大熵模型蒙古文詞性自動標(biāo)注結(jié)果

圖4 本文方法與基于最大熵模型詞性標(biāo)注方法準(zhǔn)確率對比

4 結(jié)論

針對當(dāng)前蒙古文詞性自動標(biāo)注研究工作較少，制約了對蒙古文的機(jī)器翻譯、語法分析及語義分析等領(lǐng)域的深入研究這個問題，本文采用加入lookahead學(xué)習(xí)機(jī)制的基于歷史模型的方法對蒙古文自動詞性標(biāo)注進(jìn)行了研究。實驗結(jié)果表明在深度為3，邊緣為100時的未登錄詞、集內(nèi)詞、總體詞詞性自動標(biāo)注的準(zhǔn)確率分別達(dá)到了71.2766%、99.1482%、95.3010%。在相同的訓(xùn)練集和測試集下與基于最大熵模型的方法相比準(zhǔn)確率的提高比較顯著，說明本文的方法有一定的優(yōu)勢。雖然取得了一定的成績，但是我們訓(xùn)練的語料庫還是比較小，且包含的領(lǐng)域比較單一。未來我們將搜集更多的蒙古文語料庫進(jìn)行詞性標(biāo)注，以此來提高并驗證模型的健壯性。另一個問題是我們與其他自動詞性標(biāo)注的方法對比實驗還較少，需要做進(jìn)一步的研究工作。

［1]Brill E.Transformation based error driven learning and natural language processing：a case study in part of speech tagging［J].Computational Linguistics，1995，21（4）：543－565.

［2]Brants T.TnT：a statistical part of speech tagger［C]／／Proceedings of the 6th Conference on Applied Natural Language Processing.Stroudsburg，Association for Computational Linguistics，2000：224－231.

［3]Gimenez J，Marquez I.Fast and accurate part of speech tagging：The SVM approach［C]／／Proceedings of the 4th International Conference on Recent Advances in Natural Language Processing.2003：158－165.

［4]Ratnaparkhi A.A maximum entropy model of part of speech tagging［C]／／Proceedings of EMNLP.Computational Linguistics，Cambridge，MIT Press，1996：133－141.

［5]胡冠龍，張建，李淼.改進(jìn)的基于轉(zhuǎn)換方法的拉丁蒙文詞性標(biāo)注［J].計算機(jī)應(yīng)用，2007，27（4）：963－965.

［6]艷紅，王斯日古楞.基于HMM的蒙古文自動詞性標(biāo)注研究［J].內(nèi)蒙古師范大學(xué)學(xué)報（自然科學(xué)版），2010，39（2）：206－209.

［7]張貫紅，斯·勞格勞，烏達(dá)巴拉.融合形態(tài)特征的最大熵蒙古文詞性標(biāo)注模型.計算機(jī)研究與發(fā)展，2011，48（12）：2385－2390.

［8]Andrew McCallum，Dayne Freitag，F(xiàn)ernando Pereira.Maximum entropy markov models for information extraction and segmentation［C]／／Proceedings of ICML.San Francisco，Morgan Kaufmann Publishers，2000：591－598.

［9]Yoshimasa Tsuruoka，Yusuke Miyao，Jun'ichi Kazama.Learning with Lookahead：Can History－Base Models Rival Globally Optimized Models？［C]／／Proceedings of the 15th Conference on Computational Natural Language Learning.Stroudsburg，Association for Computational Linguistics，2011：238－246.

［10]W Krauth，M Mezard.Learning algorithms with optimal stability in neural networks［J].Journal of Physics A，1987，20（11）：L745－L752.

［11]Michael Collins.Discriminative training methods for hidden markov models：theory and experiments with perceptron algorithms［C]／／Proceedings of EMNLP.Stroudsburg，Association for Computational Linguistics，2002：1－8.

［12]Yoshimasa Tsuruoka， Lookahead Part－Of－Speech Tagger［CP]，2012，http：／／www.logos.ic.i.u－tokyo.ac.jp／～tsuruoka／lapos／.

［13]Zhang Le，Maximum Entropy Modeling Toolkit for Python and C＋＋ ［CP]，2011，http：／／homepages.inf.ed.ac.uk／lzhang10／maxent＿toolkit.html.