蒙古語有向圖形態(tài)分析器的判別式詞干詞綴切分

姜文斌, 吳金星,烏日力嘎,那順烏日圖,劉 群

(1. 中國科學院 計算技術研究所,中國科學院 智能信息處理重點實驗室，北京 100190；2. 內蒙古大學 蒙古學學院,內蒙古 呼和浩特 010021)

1 引言

形態(tài)分析對于黏著語來說，是大多數(shù)自然語言處理任務的基礎。漢語的詞形較為簡單，當前的詞法分析已經做到實際可用的水平[1-4]，而對于形態(tài)復雜的民族語言如蒙古語和維吾爾語，形態(tài)分析的準確率仍有較大的提升空間[5-11]。這一方面是因為這些語言的研究起步較晚，另一方面更是因為黏著語本身構詞規(guī)律的復雜性。

與漢語的字符順次拼接的構詞方式相比，蒙古語和維吾爾語等形態(tài)豐富的語言構詞規(guī)律更加復雜。這類語言的詞語通常由詞干和若干起修飾作用詞綴組成樹狀結構，形態(tài)分析任務需要解析出詞語的詞干和詞綴構成。我們之前提出了一種針對蒙古語構詞特性的形態(tài)分析模型。該模型將蒙古語語句的詞法分析結果描述為有向圖結構，圖中節(jié)點表示分析結果中的詞干、詞綴及其相應標注，而邊則表示節(jié)點之間的轉移或生成關系。為這些轉移或生成關系賦以合適的概率形式，則形態(tài)分析的過程就是尋找其所有概率乘積最大的有向圖。該模型取得了較高的性能，但它存在致命的缺點。模型依據(jù)從人工語料庫中抽取出的詞干表和詞綴表，通過遞歸搜索為每個詞枚舉所有可能的切分標注候選。顯然，該方式無法處理含有未登錄詞干的詞語。

我們?yōu)槊晒耪Z形態(tài)分析的有向圖模型提出了一種新穎的詞干詞綴切分策略。該方法以判別式分類的思路，將詞語的詞干詞綴切分建模為詞中字母的標注問題。這可以和基于字符分類原理的判別式漢語分詞進行類比，詞中字母串對應到漢語分詞的句中字串，詞干詞綴的切分對應到漢語詞語的切分。對每個字母進行分類所依據(jù)的特征，是取自鄰近窗口內的字母子序列。這使得詞干詞綴切分模塊具有了泛化能力，能夠處理詞中含有未登錄詞干的問題。

我們在內蒙古大學開發(fā)的20萬詞規(guī)模的三級標注人工語料庫(內蒙古大學拉丁語料)上進行實驗。我們隨機分割出5%和5%的句子分別作為開發(fā)集和測試集，剩余的90%的句子全部作為訓練集。在整個測試集上，采用判別式詞干詞綴切分的最終模型取得了95.2%的詞級切分標注正確率，與采用基于詞干表和詞綴表的簡單枚舉方法的情形持平。而對于測試集中含有未登錄詞干的詞，詞級切分標注正確率比采用簡單枚舉的情形提高了7個百分點。

在本文的剩余章節(jié)，我們首先介紹之前提出的生成式有向圖形態(tài)分析模型，然后描述基于判別式分類的詞干詞綴切分方法，在展示該系統(tǒng)實驗結果并進行相應的分析說明后，我們對本文工作給出總結。

2 有向圖形態(tài)分析模型

2.1 單純切分的模型結構

同詞語形態(tài)簡單的漢語或者英語相比，詞語形態(tài)豐富的蒙古語的詞法分析更像是一個對樹結構進行選擇并對樹中節(jié)點進行標注的過程，而不是一個簡單的線性序列標注問題。這里，我們先從較為簡單的任務說起，即單純切分的有向圖模型。

有向圖模型把語句中各詞的分析結果定義為鏈狀結構：

這里，S(stem)表示詞干，A(adjoin)表示連寫詞綴，D(disjoint)表示分寫詞綴。我們用虛線連接的兩個A(或D)表示0或多個連寫詞綴(或分寫詞綴)。在詞干到詞綴之間以及詞綴到后續(xù)詞綴之間，箭頭表示生成或者轉移關系。對于整個語句，分析結果則可描述為樹狀結構：

與單個詞的分析結果結構相比，整句分析結構中增加了相鄰詞的詞干之間的生成或轉移關系，從而在所有詞干和詞綴之間形成一個拓撲有序的樹結構。樹中節(jié)點即表示詞干或者詞綴，而節(jié)點之間的邊則表示詞干到詞干、詞干到詞綴以及詞綴到詞綴的生成或轉移關系。

有向圖模型為樹中的各種不同的邊設計相應的權重，這些權重的度量反映了節(jié)點之間生成或轉移規(guī)律的強弱。這樣，求解整句詞法切分結果的過程，即為在所有可能的候選樹中尋找權重之和最高的樹的過程。有向圖模型用類似于隱馬模型使用中的轉移概率來描述樹中邊的權重。根據(jù)邊指向對象的不同有如下兩種轉移概率：

a)P(S|Sngram) 詞干到詞干的轉移概率，類似于ngram語言模型。

b)P(X|S/Xngram) 其他詞綴的生成概率，X代表詞綴，即A或者D。S/Xngram指當前詞綴之前的詞干或詞綴組成的ngram歷史。

給定一個候選樹T，有向圖模型用這些概率的乘積表示該候選的整體生成概率：

為簡潔起見，公式中隱藏了兩個條件概率的歷史條件。容易看出，這可以理解為傳統(tǒng)的N-gram語法模型向樹結構的拓展。

2.2 聯(lián)合切分標注的模型結構

對聯(lián)合切分和標注進行建模的關鍵，在于如何讓標注信息有效地參與描述句中各詞的形態(tài)結構生成過程。對應于單純切分的模型結構，有向圖模型為標注信息設計了一個同步樹狀結構以描述詞干和詞綴標注之間的生成和轉換關系。所謂同步是指樹的結構和單純切分模型的樹結構完全一致，只不過樹中對應節(jié)點，對后者而言是詞干或詞綴，對前者而言是相應的標注。另外，有向圖模型設計兩項概率描述兩個平行的樹結構中節(jié)點之間的映射關系：

a)P(X|t(X))X代表詞干或詞綴，t(X)代表其標注。此概率類似于隱馬模型中狀態(tài)到觀察的生成概率。

b)P(t(X) |X) 此項概率代表詞干或詞綴X被賦予標注t(X) 的概率。此項概率參與建模使得模型傾向于為選擇常見的標注。

這兩項條件概率在平行樹結構的節(jié)點之間可表示為不同方向的有邊，從而建立起平行樹結構之間的映射關系，構建描述能力更強的有向圖模型：

求解切分和標注結果的過程，即為在候選有向圖中尋找概率最大的有向圖。有向圖G的概率定義為：

P(G)=P(T)×P(t(T))×P(T,t(T))

其中，P(t(T))表示標注樹t(T)的概率，它和P(T)的定義一樣，只需把詞干和詞綴換成相應的標注。P(T,t(T))表示平行樹結構T和t(T)的映射概率，它定義為平行樹中所有節(jié)點對的條件概率的乘積：

理論上，P(G)的三項乘子概率對于候選有向圖的優(yōu)選可能具有不同的決策力，故為它們賦以合適的相對加權有望提升模型性能。但在本工作中暫不考慮乘子加權問題，這相當于所有加權均為1。

2.3 訓練與解碼

出現(xiàn)在單純切分模型和聯(lián)合切分與標注模型的各項概率，均可以用極大似然估計的方式從人工標注的詞法分析語料庫中統(tǒng)計得來。其中對于詞干到詞干轉移概率、詞綴到詞綴轉移概率、詞干到詞綴生成概率、相應的標注之間的三種轉移或生成概率，可以借助成熟的工具包如SRI語言模型工具來實現(xiàn)[15]。

解碼過程首先枚舉各詞的可能分析結果候選，并緊接著進行動態(tài)規(guī)劃搜索確定各詞的最優(yōu)候選。需要注意的是，蒙古語詞的某些字符在特定情境下會發(fā)生變形?；趯τ柧氄Z料的觀察和分析，我們對之前工作所用的變形規(guī)則進行了更改和擴充：

a) 詞干詞綴劃分過程中，字母串AYI、EYI、OYI、VYI、OYI和UYI中間的字符Y在特定情形下會丟掉。

b) 詞干詞綴劃分過程中，字母串GA、HA、YA、RA、MA、YE、RE和OS在特定情形下，需在中間添加下劃線。

實際解碼過程中我們采用簡單枚舉的方案，在每一處可以應用變形規(guī)則的地方，我們分別嘗試應用和不應用兩種選擇，從而為待分析詞枚舉出所有可能的變形狀態(tài)。每個變形狀態(tài)都將用于候選分析結果的生成，這些候選分析結果由接下來的動態(tài)規(guī)劃解碼過程進行排歧。動態(tài)規(guī)劃的解碼就是自左到右的viterbi搜索，考慮到文章篇幅的限制，這里不再詳述。

3 判別式詞干詞綴切分

接下來我們介紹基于判別式分類的詞干詞綴切分策略。詞干詞綴切分用于詞法分析器解碼過程的第一階段，即詞語的候選分析結果枚舉。

對于給定的待分析蒙古文詞或者其變形形態(tài)：

W=C1C2…Cn

其中Ci(1<=i<=n)是W中的第i個字母，n為字母序列的長度。詞干詞綴切分即為字母序列的劃分問題：

C1C2…Cn→C1:e1Ce1+1:e2…Cem-1+1:em

其中，em=n，字母序列C1:n劃分為m個子序列。第一個子序列C1:e1是詞干，剩余的字母序列是連寫詞綴或分寫詞綴。

這是典型的序列劃分問題，可以用序列標注的方式進行建模。我們將其與基于判別式字符分類的漢語分詞進行類比，將每個蒙古文字母Ci分類為如下四種類別之一：

b： 詞干或詞綴的開始字母

m： 詞干或詞綴的中間字母

e： 詞干或詞綴的結束字母

s： 單字母作為詞干或詞綴

當對整個蒙古文詞字母序列完成標注之后，標注為bm*e或者s的字母子序列即為詞干或者詞綴，相應地我們得到一個候選的詞干詞綴切分結果。對字符分類所采用的特征，是以該字符為中心的特定長度窗口中的字符元組。我們所用的特征模板列在下面表格中。其中，C0表示當前考察的字母，C_i/Ci表示C0左邊/右邊的第i個字母。借助這些特征模板，我們從訓練語料中抽取字母分類實例，然后用張樂開發(fā)的最大熵工具包*http://homepages.inf.ed.ac.uk/s0450736/maxent-toolkit.html.訓練字符分類器。

表1 字符分類采用的特征模板

考慮到詞干詞綴切分的歧義性，我們?yōu)榇治稣Z句中的每個詞及其變形形態(tài)都生成N個最佳的切分方案。通過為N選擇合適的值，可以在保證分析速度的同時取得較高的分析精度。N最佳切分方案可以采用類似于立方體剪枝[16]的策略高效地求得。借助詞干和詞綴的詞性列表，我們可以為每一個詞干詞綴切分候選枚舉出所有可能的詞性標注方案，從而得到待切分蒙古文詞可能的候選分析結果集。

4 實驗

我們在內蒙古大學蒙古學學院開發(fā)的20萬詞規(guī)模詞法分析語料庫上進行實驗。該語料庫共包括14 115個完整的句子，我們從中隨機抽取出各5%的語句分別用做開發(fā)集和測試集，各含705句，剩余90%的語句用作訓練集，含12 705句。模型各項概率均從訓練集中以極大似然估計法統(tǒng)計得來。其中，詞干到詞干轉移概率、詞綴到詞綴轉移概率、詞干到詞綴生成概率、相應的標注之間的三種轉移或生成概率，我們直接借助成熟的語言模型工具包SRILM，以WB平滑方式訓練三元模型。我們沿用之前工作所用的評測指標，包括：

a) 詞級正確率Pw。

以詞為單位計量，僅當詞內詞干、詞綴及其標注均正確時，該詞才是分析正確的。

b) 詞干詞綴級正確率Psa，召回率Rsa和Fsa值。

以詞干和詞綴為單位計量，僅當詞干或詞綴及相應標注正確時，該詞干或詞綴才是分析正確的。因此，詞干和詞綴可類比為漢語詞法分析中的詞。此評價標準引自文獻[7]。

c) 相應的不考慮標注信息的評測指標：Pw-t，Psa-t，Rsa-t和Fsa-t。

表2 變形規(guī)則改進和判別式詞干詞綴切分帶來的整體性能提升/%

對比表2的第1、2行，變形規(guī)則的改進帶來了大幅度的整體性能提升*之前工作中我們不對分寫詞綴和連寫詞綴進行區(qū)分。本文的形態(tài)分析器則區(qū)分兩種詞綴，但仍沿用之前的評測標準。。這說明，通過增加有用的變形規(guī)則模板和改變變形規(guī)則的應用模式，我們更有可能為待分析蒙古文詞找到其正確的變形形態(tài)，雖然這將產生更多的變形形態(tài)候選并進而導致更大的候選分析結果集，但后續(xù)的排歧過程仍能有效地找出最佳候選分析結果。然而，在改進變形規(guī)則的基礎上進一步采用判別式的詞干詞綴切分，分析精度的提升并不明顯，如表2的2、3行所示。

表3 判別式詞干詞綴切分對于詞干未登錄情形的性能提升/%

我們認為，采用判別式詞干詞綴切分策略，其優(yōu)勢更加體現(xiàn)在詞中含有未登錄詞干的情形。當待分析詞的詞干和詞綴都在訓練語料中出現(xiàn)時，基于詞干表和詞綴表的簡單枚舉方法就能找到正確的分析結果候選。對于蒙古語來說，詞綴的數(shù)目是有限的，訓練語料的數(shù)據(jù)可以輕易地覆蓋全部詞綴。詞干的情況則復雜得多，新生詞和外來詞隨著社會發(fā)展會不斷涌現(xiàn)。當待分析詞的詞干在訓練語料中不存在時，簡單枚舉方式無法找到正確的分析結果候選。而判別式的詞干詞綴切分策略則可能具有良好的泛化能力，如同漢語分詞中的情形。表3的實驗數(shù)據(jù)驗證了我們的假設。對于含有未登錄詞干的詞，判別式的詞干詞綴切分策略帶來了大幅度的性能提升。

5 總結

本文為蒙古語形態(tài)分析的有向圖模型提出了一種新穎的詞干詞綴切分策略。該方法以判別式分類的思路，將詞語的詞干詞綴切分建模為詞中字母的標注問題。與基于詞干表和詞綴表的簡單枚舉方式相比，基于判別式分類的詞干詞綴切分策略具有良好的泛化能力，能夠有效處理詞中含有未登錄詞干的問題。我們在內蒙古大學開發(fā)的20萬詞規(guī)模的三級標注人工語料庫(內蒙古大學拉丁語料)上進行實驗。對于測試集中含有未登錄詞干的詞，判別式詞干詞綴切分策略使得詞級切分標注正確率提高了7個百分點。

[1] Hwee Tou Ng and Jin Kiat Low. Chinese part-of-speech tagging: One-at-a-time or all-at-once? Wordbased or character-based?[C]//Proceedings of EMNLP, 2004:277-284.

[2] Wenbin Jiang, Liang Huang, Yajuan Lv, and Qun Liu. A cascaded linear model for joint Chinese word segmentation and part-of-speech tagging[C]//Proceedings of the 46th ACL, 2008:897-904.

[3] Huaping Zhang, Qun Liu, Xueqi Cheng, Hao Zhang and Hongkui Yu. Chinese Lexical Analysis Using Hierarchical Hidden Markov Model[C]//Preceedings of Second SIGHAN workshop affiliated with 41th ACL, 2003:63-70.

[4] 米海濤, 熊德意, 劉群. 中文詞法分析與句法分析融合策略研究[J]. 中文信息學報，2008:22(2):10-17.

[5] 那順烏日圖, 雪艷, 葉嘉明. 現(xiàn)代蒙古語語料庫加工技術的新進展—新一代蒙古語詞語自動切分與標注系統(tǒng)[C]//第十屆全國少數(shù)民族語言文字信息處理學術研討會，2005.

[6] 那順烏日圖, 淑琴. 面向信息處理的蒙古語規(guī)范化探究[J]. 中央民族大學學報(哲學社會科學版), 2007.

[7] 侯宏旭, 劉群, 那順烏日圖, 等. 基于統(tǒng)計語言模型的蒙古文詞切分[J]. 模式識別與人工智能，2009，22:108-112.

[8] 趙偉，侯宏旭，從偉，宋美娜. 基于條件隨機場的蒙古語詞切分研究[J]. 中文信息學報， 2010,24(5):31-35.

[9] 叢偉. 基于層疊隱馬爾科夫模型的蒙古語詞切分系統(tǒng)的研究[D]. 內蒙古大學碩士畢業(yè)論文，2009.

[10] 艷紅, 王斯日古楞. 基于HMM的蒙古文自動詞性標注研究[J]. 內蒙古師范大學學報(自然科學漢文版)，2010.

[11] 古麗拉·阿東別克，米吉提·阿布力米提. 維吾爾語詞切分方法初探[J]. 中文信息學報，2004,18(6):61-65.

[12] Lawrence. R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition[C]//Proceedings of IEEE, 1989:257-286.

[13] John Lafferty and AndrewMcCallum and Fernando Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data[C]//Proceedings of the 18th ICML, 2001:282-289.

[14] McCallum, A., Freitag, D. and Pereira, F. Maximum entropy Markov models for information extraction and segmentation[C]//Proc. ICML, 2000:591-598.

[15] Stolcke and Andreas. Srilm - an extensible language modeling toolkit[C]//Proceedings of the International Conference on Spoken Language Processing, 2002:311-318.

[16] Huang Liang and David Chiang. 2005. Better k-best parsing [C]//Proceedings of the IWPT, 2005: 53-64.