趙建東，高光來(lái)，飛 龍

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

1 引言

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

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

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

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

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

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

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

2.2 “移進(jìn)—?dú)w納”分析器

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

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

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

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

2.3.1 搜索算法

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

3 蒙古文自動(dòng)詞性標(biāo)注實(shí)驗(yàn)

圖1 搜索算法

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

為了優(yōu)化lookahead搜索算法中的權(quán)值，我們采用了邊緣感知機(jī)的學(xué)習(xí)算法［10]。邊緣感知機(jī)和支持向量機(jī)類(lèi)似，與沒(méi)有采用邊緣的感知機(jī)相比，它能夠產(chǎn)生更加精確的模型。圖2給出了我們采用的學(xué)習(xí)算法的偽代碼。這個(gè)學(xué)習(xí)算法與標(biāo)準(zhǔn)的邊緣感知機(jī)的訓(xùn)練算法相似，即當(dāng)感知機(jī)出現(xiàn)錯(cuò)誤時(shí)，我們用兩個(gè)不同的特征向量來(lái)更新權(quán)值，一個(gè)特征向量對(duì)應(yīng)正確的操作；另一個(gè)特征向量對(duì)應(yīng)得分最高的操作，當(dāng)邊緣不足夠大的時(shí)候，也可以對(duì)應(yīng)為得分次最高的操作。需要注意的是次最優(yōu)操作向量可以用正確操作的得分減去邊緣距離這樣一個(gè)簡(jiǎn)單的技巧而自動(dòng)選擇，即圖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 語(yǔ)料庫(kù)的構(gòu)建

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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