基于判別式分類和重排序技術(shù)的藏文分詞

孫 萌，華卻才讓，才智杰，姜文斌，呂雅娟，劉 群

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院智能信息處理重點(diǎn)實(shí)驗(yàn)室,北京 100190; 2. 中國(guó)科學(xué)院大學(xué)，北京，100049; 3. 青海師范大學(xué) 藏文信息研究中心,青海 西寧 810008)

1 前言

藏文分詞是藏文信息處理的基礎(chǔ)。在藏文中，詞與詞之間缺乏間隔標(biāo)記，和漢語(yǔ)類似都是字符或字的序列，因此藏文信息處理面臨和漢語(yǔ)同樣的問(wèn)題，即如何將字符序列切分成合理的詞語(yǔ)序列。而現(xiàn)有的藏文分詞技術(shù)切分的準(zhǔn)確率和實(shí)用性還有較大提升空間。這一方面是因?yàn)椴匚木幋a方案較多并且藏文研究起步較晚，另一方面更是由于藏文本身構(gòu)詞規(guī)律的復(fù)雜性。

研究者在藏文分詞方面提出了很多有效的算法，這些方案大體可以分為兩類。第一類是基于藏文特有的語(yǔ)言學(xué)知識(shí)的規(guī)則方法。陳玉忠[1-2]從藏文的字切分特征、詞切分特征和句切分特征三個(gè)方面深入研究藏文特有的語(yǔ)法接續(xù)規(guī)則，提出了基于格助詞和接續(xù)特征的藏文分詞方法。祈坤鈺[3]分別用格切分、邊界符判定和模式匹配算法實(shí)現(xiàn)對(duì)藏文的三級(jí)切分。才智杰[4-5]首先識(shí)別格助詞，然后將其作為分隔符對(duì)句子進(jìn)行切分，采用最大匹配的算法依次對(duì)切分之后的塊分詞。孫媛[6]在格助詞分塊的基礎(chǔ)上，引入詞頻信息改進(jìn)分詞質(zhì)量。劉匯丹[7]提出臨界詞識(shí)別方法和詞頻消歧方法有效地提高分詞正確率。基于規(guī)則的藏文分詞算法通常需要一個(gè)規(guī)模足夠大的詞典，采用最大匹配算法，即以在詞典中查到的最長(zhǎng)的詞條作為句子的切分，算法實(shí)現(xiàn)簡(jiǎn)單，效率較高。這種方法不能很好的處理切分歧義問(wèn)題，另外對(duì)于未登錄詞的識(shí)別能力不強(qiáng)。第二類是基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)方法，用到的統(tǒng)計(jì)模型主要是隱馬爾科夫模型[8-9]，然而相對(duì)復(fù)雜的藏文構(gòu)詞現(xiàn)象，隱馬模型仍然略顯簡(jiǎn)單。而其他統(tǒng)計(jì)模型的研究，如最大熵、感知機(jī)和條件隨機(jī)場(chǎng)等模型的應(yīng)用已經(jīng)成為漢語(yǔ)分詞的主流方向，目前此類模型應(yīng)用于藏文分詞的研究較少，一方面因?yàn)椴匚姆衷~標(biāo)注語(yǔ)料庫(kù)的規(guī)模限制，另一方面由于藏文不僅具有與漢語(yǔ)類似的字符順次拼接的構(gòu)詞方式，在時(shí)態(tài)上還具有曲折變化，是一種具有邏輯格語(yǔ)法體系的拼音文字。

在漢語(yǔ)分詞領(lǐng)域，Xue[10]提出了基于最大熵的漢語(yǔ)分詞方法，將分詞過(guò)程看作對(duì)每個(gè)字的分類，從而將分詞轉(zhuǎn)換成序列標(biāo)注問(wèn)題，即對(duì)每個(gè)字的判別式分類的過(guò)程。Collins[11]采用基于感知機(jī)的方法進(jìn)行詞性標(biāo)注，也獲得了較高的測(cè)試效果。采用基于字標(biāo)注方法的優(yōu)勢(shì)在于： (1)可以融入任何特征以改善分詞效果；(2)識(shí)別未登錄詞的能力較強(qiáng)。在基于統(tǒng)計(jì)的藏文分詞領(lǐng)域，Liu[12]根據(jù)藏文構(gòu)詞特點(diǎn)，提出基于條件隨機(jī)場(chǎng)的藏文分詞，然而由于藏文構(gòu)詞規(guī)律的復(fù)雜性，在漢語(yǔ)上效果良好的序列標(biāo)注模型不適合直接用于藏文分詞。因此本文提出一種基于格助詞規(guī)則與字符序列標(biāo)注模型相結(jié)合的分詞模型，用以精確刻畫(huà)藏文的構(gòu)詞方式。

藏文的詞語(yǔ)通常由一個(gè)或者若干音節(jié)組成，但是在有些情況下，需要將一個(gè)音節(jié)切分，和此音節(jié)之前或者之后的音節(jié)組成詞語(yǔ)。本文深入討論了以藏文字丁、藏文字丁-音節(jié)點(diǎn)、音節(jié)作為序列標(biāo)注的基本單位對(duì)分詞效果的影響。基于字標(biāo)注方法的分詞算法通常采用局部特征，即字級(jí)別的特征。非局部特征，比如詞語(yǔ)級(jí)別的特征，也能顯著提高分詞效果，但是卻很難融入到現(xiàn)有的解碼算法中。Jiang[13]提出一種基于詞圖的重排序算法，融入非局部特征，分詞精確率得到較大提升。本文在基于詞圖的重排序方法上，提出了基于詞典懲罰的最短路徑算法，用以提高藏文分詞的性能。

2 藏文分詞框架

針對(duì)藏文分詞各個(gè)層面的處理對(duì)象以及問(wèn)題特點(diǎn)，我們將原子切分、基于感知機(jī)解碼和構(gòu)建最短路徑這三個(gè)模型有機(jī)的融合在一個(gè)統(tǒng)一的框架下，如圖1所示。

圖1 藏文分詞框架

首先，根據(jù)藏文特有的構(gòu)詞規(guī)律將句子切分成最小粒度的序列，稱之為單元序列；隨后，根據(jù)感知機(jī)模型提供的判別式分類的權(quán)重，在單元序列上進(jìn)行維特比解碼，從而生成有向圖，并通過(guò)查詢?cè)~典為邊賦予不同的權(quán)重；最后，通過(guò)動(dòng)態(tài)規(guī)劃算法求解加權(quán)有向圖中的最短路徑，生成最終分詞結(jié)果。

3 藏文最小構(gòu)詞粒度切分

一個(gè)或多個(gè)藏文字丁組成一個(gè)音節(jié)，一個(gè)或者多個(gè)音節(jié)組成詞，音節(jié)之間由音節(jié)點(diǎn)分隔。如圖2所示的藏文片段，其中文含義是“處在某一個(gè)級(jí)別”。

圖2 藏文片段

基于序列標(biāo)注模型的漢語(yǔ)分詞過(guò)程可以視為在字層面上的組合，而藏文分詞的復(fù)雜性在于，不能在直接音節(jié)層面上進(jìn)行組合，在有些情況下需要將某個(gè)音節(jié)拆分，和左邊或者右邊音節(jié)組合，或者獨(dú)立成詞。由于這種組合的靈活性，對(duì)于藏文的標(biāo)注序列的最小構(gòu)詞粒度必須是小于音節(jié)的單位。本文設(shè)計(jì)三種構(gòu)詞粒度的方案以描述其構(gòu)詞規(guī)律，如圖3所示。

方案1： 藏文字丁。對(duì)句子按照每個(gè)字丁進(jìn)行切分，如圖3中的切分a。

方案2： 藏文字丁-音節(jié)點(diǎn)。不將音節(jié)點(diǎn)單獨(dú)切分出來(lái)，而是將其與左邊字丁組合，如圖3中的切分b。

方案3： 音節(jié)。定義特殊格助詞表，先按照音節(jié)掃描切分句子，一旦音節(jié)中含有特殊格助詞則匹配相對(duì)應(yīng)的規(guī)則切分此音節(jié)，如圖3中c所示。

圖3 三種構(gòu)詞粒度切分方案舉例

選擇藏文的最小構(gòu)詞粒度的關(guān)鍵，在于將原始句子切分為分詞的原子序列。分詞的原子指的是分詞的最小處理單元，在分詞過(guò)程中，可以組合成詞，但內(nèi)部不能做進(jìn)一步拆分。a方案沒(méi)有考慮任何構(gòu)詞規(guī)律，在分詞標(biāo)注語(yǔ)料有限，藏文字丁構(gòu)詞規(guī)律較為復(fù)雜的情況下，統(tǒng)計(jì)模型缺乏足夠的知識(shí)進(jìn)行標(biāo)注學(xué)習(xí)；b方案在a方案的基礎(chǔ)上考慮音節(jié)規(guī)律，減小了分詞時(shí)的解碼搜索空間；而方案c則最大程度保存了音節(jié)的內(nèi)部結(jié)構(gòu)，卻又不會(huì)破壞構(gòu)詞粒度的原子性。本文實(shí)驗(yàn)部分探討了在同樣規(guī)模標(biāo)注語(yǔ)料庫(kù)下，采用以上不同的切分策略對(duì)最終分詞效果的影響。

4 基于感知機(jī)的藏文粗切分

對(duì)原子序列通過(guò)維特比算法進(jìn)行序列標(biāo)注，而序列標(biāo)注的權(quán)重由感知機(jī)模型訓(xùn)練得到，其中感知機(jī)模型是判別式分類模型的一種。Collin[11]提出的基于感知機(jī)的序列標(biāo)注方法是一種在線的學(xué)習(xí)方法。感知機(jī)模型的訓(xùn)練速度快，分類效果好。本文采用平均感知機(jī)算法[6]進(jìn)行句子的粗切分，該算法記錄每一次權(quán)重的改變，以提高分詞系統(tǒng)的穩(wěn)定性，如算法1所示。

設(shè)輸入句子的原子序列xi∈X，輸出標(biāo)注序列yi∈Y，X表示訓(xùn)練語(yǔ)料中的所有句子，Y表示對(duì)應(yīng)的標(biāo)注，其中{b,m,e,s}是標(biāo)注的符號(hào)集合。b表示詞的開(kāi)始，m表示詞的內(nèi)部，e表示詞的結(jié)尾，s表示單獨(dú)成詞。

算法1 平均感知機(jī)算法

1: 輸入： 訓(xùn)練實(shí)例(xi,yi)

3: Fort← 1…T,i← 1…Ndo

為了盡可能的擬合數(shù)據(jù)，本文將Jiang[13]設(shè)計(jì)的特征模板的窗口擴(kuò)展為4，如表1所示。

表1 特征模板

5 基于詞圖的重排序

對(duì)于基于感知機(jī)的分詞，除了通常使用的局部特征，非局部特征的引入也會(huì)提升分詞的性能。但是，非局部特征要在解碼的過(guò)程中動(dòng)態(tài)的生成，很難直接將其加入到分類器中，并且引入非局部特征也會(huì)影響訓(xùn)練過(guò)程中對(duì)應(yīng)特征的調(diào)節(jié)。在自然語(yǔ)言處理的其他領(lǐng)域也面臨著類似的問(wèn)題，一般的解決方案是使用重排序的方法引入非局部特征。然而，傳統(tǒng)方法是在n-best結(jié)果基礎(chǔ)上進(jìn)行重排序，n-best所能表示的搜索空間較小，并且儲(chǔ)存冗余。感知機(jī)模型進(jìn)行藏文粗切分的過(guò)程中保存分詞的候選，并將候選分詞結(jié)果壓縮為詞圖，最后采用基于詞圖的重排序算法尋找最合適的分詞結(jié)果。

本文針對(duì)藏文本身的特點(diǎn)，提出了基于最短路徑的詞典懲罰算法，快速?gòu)脑~圖中選擇一條最優(yōu)路徑。

5.1 詞圖的生成與剪枝

可以將詞圖看作一個(gè)有向無(wú)環(huán)圖，如圖3所示。以構(gòu)詞單元之間的空隙作為圖的頂點(diǎn)，頂點(diǎn)之間的連線表示頂點(diǎn)之間的字符組合成詞。每條邊通過(guò)詞典獲得相應(yīng)的權(quán)重，在詞圖上尋找一條最短路徑，例如： <1,4>,<4,7>。

圖3 詞圖

按照詞圖頂點(diǎn)的拓?fù)漤樞颍瑢?duì)每個(gè)節(jié)點(diǎn)保存以此節(jié)點(diǎn)為終點(diǎn)的所有邊，可以生成詞圖。例如，對(duì)于頂點(diǎn)3，保存邊<2,3>和<1,3>；對(duì)于頂點(diǎn)4，保存邊<1,4>、<2,4>和<3,4>。

如果保存解碼過(guò)程中的所有邊，則詞圖中會(huì)包含過(guò)多的無(wú)用路徑，在一定程度上會(huì)影響最短路徑的生成。本文通過(guò)限制每個(gè)節(jié)點(diǎn)的入度，只保存得分最高的n條邊，實(shí)現(xiàn)詞圖的簡(jiǎn)單剪枝。由于詞圖結(jié)構(gòu)的特點(diǎn)，即使限制節(jié)點(diǎn)入度，同樣會(huì)包含很多路徑信息。

5.2 詞典懲罰策略

可能有如下三種切分：

5.3 基于詞圖的重排序算法

壓縮詞圖經(jīng)由詞典懲罰策略轉(zhuǎn)換為加權(quán)有向圖，所求的最終分詞結(jié)果就是從初始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的最短路徑?；趩卧从邢驘o(wú)環(huán)圖的最短路徑問(wèn)題，可以采用Dijkstra貪心算法求解。 Dijkstra算法的時(shí)間復(fù)雜度為O(V2)，其中V表示圖中的頂點(diǎn)數(shù)，求解的是單源點(diǎn)到圖中所有點(diǎn)的最短路徑，而求解基于加權(quán)有向圖的最短路徑問(wèn)題具有兩個(gè)不同之處： 首先有向邊的源點(diǎn)編號(hào)均小于終點(diǎn)編號(hào)，有向邊的方向具有一致性；其次，只需求解首尾兩點(diǎn)的最短路徑。因此，本文提出的最短路徑算法可以視為Dijkstra算法的簡(jiǎn)化。算法從左到右依次計(jì)算每個(gè)節(jié)點(diǎn)與源點(diǎn)之間的最短路徑，時(shí)間復(fù)雜度為O(E)，其中E表示圖中的邊，對(duì)每個(gè)頂點(diǎn)，其每條入邊僅被檢測(cè)一次，所以算法實(shí)際總共迭代|E|次。

如算法2所示，v表示詞圖中的頂點(diǎn)，E表示頂點(diǎn)的連線，即邊。其中邊的權(quán)重是通過(guò)查詢?cè)~典獲取，Path記錄最短路徑的信息，Path[v].previous表示以頂點(diǎn)v為終點(diǎn)的邊的起始頂點(diǎn)v′。 每個(gè)節(jié)點(diǎn)均存儲(chǔ)其上一個(gè)節(jié)點(diǎn)的信息，因此，在求解出最短路徑后，可以通過(guò)回溯算法快速生成最終的分詞結(jié)果。

算法2 生成最短路徑

1: 輸入： 詞圖L

2:Path← 0

3: Forv∈L.V按照拓?fù)漤樞?do

4: Forv′ 按照拓?fù)漤樞蛟趘之前 do

5:E←

6: IfPath[v].score>Path[v′].score+E.weight

7:Path[v].score←Path[v′].score+E.weight

8:Path[v].previous←v′

9: 輸出： 最短路徑Path

6 實(shí)驗(yàn)及分析

我們現(xiàn)有由青海師范大學(xué)提供的12 942條人工分詞的藏文句子，共110K詞語(yǔ)，語(yǔ)料的領(lǐng)域較為廣泛，從一定程度上能夠檢驗(yàn)系統(tǒng)的魯棒性和可移植性。從中隨機(jī)選擇500句作為測(cè)試集，剩余的作為訓(xùn)練集。

為了研究構(gòu)詞粒度對(duì)于基于感知機(jī)的藏文分詞性能的影響，以基本字丁、基本字丁-音節(jié)點(diǎn)和音節(jié)為切分單位，本文設(shè)計(jì)3組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 藏文分詞系統(tǒng)的性能

我們發(fā)現(xiàn)，構(gòu)詞粒度增大，分詞結(jié)果的性能也在提升，基于音節(jié)的感知機(jī)藏文分詞系統(tǒng)的F值比基于基本字丁的系統(tǒng)提高了3.3個(gè)百分點(diǎn)?？梢詫⒉匚姆衷~看作序列標(biāo)注的過(guò)程，增大構(gòu)詞粒度，則序列變短，分類器決策的次數(shù)將減少，減少了搜索空間，準(zhǔn)確率提高。

但是基于音節(jié)的感知機(jī)藏文分詞系統(tǒng)所達(dá)到的F值91.21%仍低于現(xiàn)有的基于規(guī)則的藏文分詞系統(tǒng)(基線系統(tǒng))的F值94.87%。我們將以上三組實(shí)驗(yàn)看作是基于感知機(jī)模型的粗切分，分詞結(jié)果中往往會(huì)出現(xiàn)不成詞的切分。我們?cè)诨谝艄?jié)的分詞系統(tǒng)上加入基于詞圖的重排序模塊，通過(guò)查詢?cè)~典賦予每條邊不同的權(quán)重，從而搜索最短路徑。最終分詞的F值達(dá)到96.25%，比基于規(guī)則的分詞系統(tǒng)提高了1.38個(gè)百分點(diǎn)，比基于音節(jié)的分詞系統(tǒng)提高了5.04個(gè)百分點(diǎn)。

7 結(jié)論及未來(lái)工作

本文提出一種基于判別式模型的藏文分詞方法，并探究構(gòu)詞粒度的大小對(duì)分詞性能的影響，從而確定藏文分詞的基本切分粒度。然而，由于非局部特征不能直接用于感知機(jī)，我們采用基于詞圖的重排序算法引入非局部特征，并運(yùn)用最短路徑算法產(chǎn)生最優(yōu)的分詞結(jié)果。

在基于統(tǒng)計(jì)的漢語(yǔ)分詞領(lǐng)域，最大熵和條件隨機(jī)場(chǎng)也獲得了較好的分詞效果， 未來(lái)我們將對(duì)比在同樣特征集合下，哪個(gè)模型更適于藏文分詞。另外，在重排序中我們僅考慮當(dāng)前詞的詞典特征，沒(méi)有考慮到當(dāng)前詞的上下文信息。下一步的工作將研究語(yǔ)言模型在重排序中的作用。

[1] 陳玉忠，李保利，俞士汶，等. 基于格助詞和接續(xù)特征的藏文自動(dòng)分詞方案[J].語(yǔ)言文字應(yīng)用，2003(1):75-82.

[2] 陳玉忠，李保利，俞士汶. 藏文自動(dòng)分詞系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].中文信息學(xué)報(bào), 2003,17(03):15-20.

[3] 祁坤鈺.信息處理用藏文自動(dòng)分詞研究[J]. 西北民族大學(xué)學(xué)報(bào)(哲學(xué)社會(huì)科學(xué)版), 2006,(4):92-97.

[4] 才智杰. 藏文自動(dòng)分詞系統(tǒng)中緊縮詞的識(shí)別[J]. 中文信息學(xué)報(bào), 2009,23(1):35-37.

[5] 才智杰. 班智達(dá)藏文自動(dòng)分詞系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 青海師范大學(xué)民族師范學(xué)報(bào)，2010,21(2):75-77.

[6] 孫媛，羅桑強(qiáng)巴，楊銳，等.藏語(yǔ)交集型歧義字段切分方法研究[C]//第十二屆中國(guó)少數(shù)民族語(yǔ)言文字信息處理學(xué)術(shù)研討會(huì)論文集,2009.

[7] 劉匯丹，諾明花，趙維納，等. SegT： 一個(gè)實(shí)用的藏文分詞系統(tǒng)[J]. 中文信息學(xué)報(bào), 2012, 26(1):97-103.

[8] 蘇俊峰，祁坤鈺，本太. 基于HMM 的藏語(yǔ)語(yǔ)料庫(kù)詞性自動(dòng)標(biāo)注研究[J]. 西北民族大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 30(1): 42-45.

[9] 史曉東，盧亞軍. 央金藏文分詞系統(tǒng)[J]. 中文信息學(xué)報(bào)，2011,25(4):54-56.

[10] Nianwen Xue, Libin Shen. Chinese word segmentation as LMR tagging[C]//Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing, in conjunction with ACL’03, Sapporo, Japan, 2003: 176-179.

[11] Collins,Michael. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms[C]//Proceedings of the Empirical Methods in Natural Language processing Conference, Philadelphia, America, 2002: 1-8.

[12] Huidan Liu, Minghua Nuo, Longlong Ma, et al. Tibetan Word Segmentation as Syllable Tagging Using Conditional Random Fields[C]//Proceedings of the 25th Pacific Asia Conference on Language, Information and Computation, Singapore, 2011:168-177.

[13] Wenbin Jiang, Haitao Mi, QunLiu. Word lattice reranking for Chinese Word Segmentation and Part-of-Speech Tagging[C]//Proceedings of 22nd International Conference on Comtutational Linguistics, Manchester, UK, 2008:385-392.