趙建東，高光來，飛 龍

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

1 引言

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

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

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

2 基于歷史模型的詞性標注方法

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

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

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

2.2 “移進—歸納”分析器

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

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

2.3 Lookahead學習機制

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

2.3.1 搜索算法

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

3 蒙古文自動詞性標注實驗

圖1 搜索算法

2.3.2 訓練一個邊緣感知機

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

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

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

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

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

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

3.2 實驗結(jié)果

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

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

圖3 蒙古文自動詞性標注準確率實驗結(jié)果

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

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

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

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

圖4 本文方法與基于最大熵模型詞性標注方法準確率對比

4 結(jié)論

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

［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]胡冠龍，張建，李淼.改進的基于轉(zhuǎn)換方法的拉丁蒙文詞性標注［J].計算機應用，2007，27（4）：963－965.

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

［7]張貫紅，斯·勞格勞，烏達巴拉.融合形態(tài)特征的最大熵蒙古文詞性標注模型.計算機研究與發(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.