基于最大間隔馬爾可夫網模型的漢語分詞方法

李月倫，常寶寶

(北京大學 計算語言學研究所，北京 100871)

1 引言

印歐語系的語言，句子中使用空格將詞分開，在中文文本中，句子是一串連續的中文字符。因此，在做漢語自然語言處理中，人們首先要做的工作就是自動分詞，在詞的邊界處做出標記。

長期以來，研究人員一直把未登錄詞和分詞歧義并列為影響分詞精度的兩大因素[1]。未登錄詞問題的提出是因為從訓練語料中提取出來的詞典不可能詳盡地列出漢語中的所有詞，所以在測試語料中出現但未在詞典中出現的詞會更難被切分正確。通常，未登錄詞的召回率是評價一個自動切分性能好壞的重要標志之一。歧義問題出現的原因是漢字可以出現在詞的不同位置，比如字符“文”可以作為“日文”一詞的詞尾，同時也可作為“文章”一詞的詞首，這樣，當切分程序遇到“日文章魚怎么說”這樣一個句子時，必須要判斷字符“文”是與字符“日”組成一個詞還是與字符“章”組成一個詞[2]。

在以往的研究中，研究人員對漢語分詞問題提出了很多不同的解決方法，根據這些方法是否使用了詞典可將它們分為基于詞典的方法與基于字標注的方法。

基于詞典的分詞方法需要一個提前編制好的詞典，將文本中的字符串與詞典中的詞條進行比較，如果匹配成功，則劃分出一個詞。在解決未登錄詞的問題上，基于詞典的分詞方法需要引入專門的未登錄詞識別模塊。因此，詞典構建在很大程度上決定了切分性能的好壞。

基于字標注的分詞方法的典型代表是Xue[2]提出的分詞方法。該方法對語料庫中每個漢字進行標注，根據漢字在詞中的不同位置，設置四種標志，分別為LL，RR，MM和LR。如果一個字出現在了一個詞的左邊界，則這個字被標記為LL；如果一個字出現在了一個詞的右邊界，則這個字被標記為RR；如果一個字出現在一個詞的中間部分，則這個字被標記為MM；如果一個字單獨組成了一個詞，則這個字被標記為LR。把被標注好的語料以及人工設置的特征模板作為機器學習工具的輸入，機器學習的結果將會輸出一套特征集，該特征集可對未被標記的文本進行標記，最后用得到的標記對該文本進行切分。鑒于多數漢字都有可能出現在不同詞的不同位置上，因此它們都會擁有多于一種的標記，二義性由此產生。為了解決二義性，機器學習的過程應該能根據該漢字的特征以及該漢字所處的上下文特征得出該字的正確標記。與基于詞典的分詞方法相比，非基于詞典的方法不需要預先編譯好的詞典，但需要大量的被標注好的訓練數據，字標注方法近年來得到了較多的采用。

目前常用于分詞的機器學習方法有最大熵模型[2]和條件隨機場模型[3、4]，尤其是條件隨機場模型，由于其考慮到分詞問題中的結構依存關系，取得了較好的分詞效果。

最大間隔馬爾可夫網模型(Max Margin Markov Networks，簡稱M3N模型),是由B.Taskar等[5]提出的一種新型結構學習的方法，該模型的優勢在于用最大間隔的思想訓練馬爾可夫網絡，保持了最大間隔方法的優勢，同時又具備處理具有結構的復雜輸入的能力。漢語分詞問題是典型的序列標注問題，本文將M3N模型用于解決漢語切分問題，考察這一方法在分詞問題中的可用性。

本文的組織方式如下：在第2節中，對最大間隔馬爾可夫模型進行簡單的介紹。第3節是特征的提取方法。在第4節中，詳細闡述每組實驗的做法，報告結果并做一些相應的分析。

2 最大間隔馬爾可夫網模型

與CRF模型類似，最大間隔馬爾可夫網模型(M3N)的基礎也是無向圖(馬爾可夫網)模型，與CRF模型不同的是，該方法把馬爾可夫網與最大間隔原則聯系起來，是對馬爾可夫網進行最大間隔訓練的一種非概率化模型。

傳統無向圖模型可以有效地表示出序列標注間的相互關系，但與最大間隔模型相比，推廣能力不佳，不支持核函數，因而無法用于高維特征空間。M3N模型將馬爾可夫網的學習過程視作尋找最大間隔決策函數的最優化問題，因而將最大間隔模型與無向圖模型的優點結合在一起，在改善推廣能力的同時也考慮到了序列標注間的相互聯系。

在無向圖中，我們在每條邊上定義基函數(特征函數)f(x,yi,yj)，其中(i,j)∈E，并且假定所有邊同質，即每條邊都具有相同的基函數。如果每條邊都具有n個基函數，那么我們可以定義如下一組特征：

其中，k∈[1,n]。即每個特征是每條邊上相應基函數的和。

M3N模型將序列標注問題視為如下的決策問題：

其中，x為觀察序列，y為標注序列。

M3N模型的參數為權值向量w，與支持向量機模型類似，需要通過間隔最大化的原則求解這些參數。在M3N模型中，函數間隔定義如下：

Δfx(y)=f(x,t(x))-f(x,y)

其中，t(x)為x的正確標注序列。

M3N模型擴展了傳統的0～1損失函數，提出使用逐標記損失函數，逐標記損失函數定義如下：

其中Δtx(yi)定義如下：

Δtx(yi)≡I(yi≠(t(x))i)

即Δtx(yi)是yi的0～1損失。

逐標記損失函數的引入，使得t(x)與y之間的間隔依賴于序列y的損失函數值，更好地照顧到序列標記的結構特性。

按照最大間隔原則，M3N模型參數訓練所對應的原始優化問題和對偶優化問題分別如下：

原始優化問題

對偶優化問題

3 文字標注及特征設置

3.1 用不同的標記集對文字進行標注

為了測試標記集對切分性能的影響，我們在實驗中采用了下面三種標記集：

(1) S:單字詞，B:詞的左邊界，M:詞的中間部分，E:詞的右邊界

(2) B:詞的左邊界，I:詞的后續部分

(3) I:詞的前續部分，E:詞的右邊界

給定如下一句話：

中國 共產黨 成功 地 召開 了 第十五 次 全國 代表大會 ，

用三種標記集標記的結果分別為：

中國 共產黨 成功 地 召開 了 第十五 次 全國 代表大會 ，

(1) BE BME BE S BE S BME S BE BMME S

(2) B I B I I B I B B I B B I I B B I B I I I B

(3) I E I I E I E E I E E I I E E I E I I I E E

3.2 特征設置

相關工作表明，使用當前字前后各兩個字(即5個字的窗口寬度)的特征是比較理想的[5]。因此，我們的特征模板設置如下：

第一組：基本特征

a.當前字符左鄰的第二個字符(C-2)

b.當前字符左鄰的第一個字符(C-1)

c.當前字符(C0)

d.當前字符右鄰的第一個字符(C1)

e.當前字符右鄰的第二個字符(C2)

f.當前字符，當前字符左鄰的第一個字符(C-1C0)

g.當前字符，當前字符右鄰的第一個字符(C0C1)

h.當前字符左鄰的第二個字符，當前字符左鄰的第一個字符(C-2C-1)

i.當前字符右鄰的第一個字符，當前字符右鄰的第二個字符(C1C2)

j.當前字符左鄰的第一個字符，當前字符右鄰的第一個字符(C-1C1)

第二組：可選特征組一

k.當前字符左鄰的第一個字符，當前字符左鄰的第一個字符的標記與當前字符(C-1C0T-1)

l.當前字符左鄰的第二個字符，當前字符左鄰的第一個字符，當前字符，當前字符左鄰的第二個字符的標記，當前字符左鄰的第一個字符的標記(C-2C-1C0T-2T-1)

第三組：可選特征組二

m.當前字符左鄰的第一個字符的標記(T-1)

n.當前字符左鄰的第二個字符的標記(T-2)

第四組：可選特征組三

o:當前字符左鄰的第二個字符的標記，當前字符左鄰的第一個字符的標記(T-2T-1)

從特征模板提供的信息來看，第一組特征為基本特征，為每次實驗的必選特征。第二組特征至第四組特征均為可選特征，我們將測試這些可選特征對分詞性能的影響。

4 實驗

我們選擇北京大學計算語言所開發的1998年1月份《人民日報》的部分語料作為訓練語料和測試語料，并進行切分實驗。該語料共有57萬詞左右，實驗4.5中1∶50的實驗所用的訓練語料為全部訓練語料。語料中包含切分和詞性標注信息，均經過人工校對。該語料中包含新聞題材、文學題材等。

我們一共進行了五組實驗，分別驗證不同的機器學習模型、不同的標記集、不同的特征模板集、不同的訓練迭代次數以及訓練不同規模的語料對漢語分詞效果的影響。

4.1 實驗一：用不同的機器學習模型對語料進行訓練

在這個實驗中，我們分別用最大熵模型，CRF模型和M3N模型對相同的語料進行訓練和測試，比較不同機器學習模型在詞語切分性能方面的差異。

(1) 語料設置

考慮到訓練效率的問題，我們選擇了20萬詞左右的語料作為訓練語料。為了保證訓練語料與測試語料劃分的合理性，我們把全部語料中的句子以每100句為單位劃分，其中第一句用來做測試語料，第2至21句用來做訓練語料。得出的訓練語料共有22.5萬詞，測試語料1.1萬詞左右。在測試語料中，共有未登錄詞568個，占測試語料的5%。

(2) 特征模板設置

此次實驗共用到13個特征模板，如3.2節中模板a～m所示。

(3) 標記集設置

使用3.1節中第(1)組標記集合，即4個切分標記。

(4) 實驗結果(表1)

表1 使用不同機器學習模型得到的分詞結果

從結果中可以看出，結構化模型要明顯好于非結構化模型，因為結構化模型考慮了句子內部標記之間的相關性。最大熵模型因為沒有考慮到這一點，因而產生了“標記偏見”問題[3]，因此切分精度較低。

從CRF和M3N得出的結果中可以看出，M3N得到的F值比CRF高1%，但在OOV_recall方面卻有下降?？偟膩碚f，將M3N模型運用到漢語分詞中取得了不錯的效果，基于M3N模型的性能略優于CRF模型。

為了更直觀地比較M3N模型與CRF模型性能上的差異，我們隨機選擇了一些被M3N模型切分正確但被CRF模型切分錯誤的語句進行對比(錯誤切分指的是與人工標注的標準答案不一致)?；谑欠駥儆谖吹卿浽~，可將它們分為已登錄詞(IV)和未登錄詞(OOV)兩組，分別如表2及表3所示。

表2顯示，針對已登錄詞，M3N表現出了較好的切分歧義消解能力。在未登錄詞識別方面，雖然實驗結果表明M3N模型得到的未登錄詞召回率略低于CRF模型，但通過隨機抽取的一些錯誤樣例(如表3所示)可以發現，M3N模型對長詞的捆綁能力似乎優于CRF模型，M3N模型似乎可以更好地利用上下文語境信息。

當然，在實驗結果中，也存在被CRF模型正確處理，但被M3N模型錯誤處理的句子，表4列出了一些這樣的切分實例。

表2 M3N模型與CRF模型切分結果的對比1(已登錄詞)

表3 M3N模型與CRF模型切分結果的對比2(未登錄詞)

表4 M3N模型與CRF模型切分結果的對比3

4.2 實驗二：用不同的標記集對語料進行訓練

在這個實驗中，我們用到的訓練語料、測試語料以及特征模板與實驗一相同，基于M3N模型進行訓練和測試。

我們用三種不同的標記集對訓練語料進行標記，如3.1節所示。

實驗結果如表5所示。

表5 使用不同標記集合得到的分詞結果

從實驗結果可以看出，三個實驗的結果依次遞減，說明SBME標記集使分詞結果達到最好。IE標記集得到的OOV_recall也較低。

4.3 實驗三：用不同的特征模板集對語料進行訓練

在這個實驗中，我們用到的語料與實驗一相同，使用四個標記的標記集(SBME標記)，基于M3N模型進行訓練和測試。

我們需要用到的15個特征模板如3.2節中a～o所示。

4.3.1 特征模板選擇原則

在3.2節中已經提到，第一組特征模板為基本特征，在訓練過程中必不可少，第二組特征至第四組特征可以起到相似的作用，均是要得到當前字符之前字符的標記信息。但第二組特征與第三、四組特征的區別在于第二組特征中包含了當前字以及左鄰第一、第二個字的信息。

我們要對上述特征模板集中那些效果相似的模板進行排列組合，與必須包括的模板a～j合并構成若干個特征模板集，找出效果最好的特征模板集合，并對其中的模板進行一些分析。

具體而言，在每次實驗中，我們都必須要得到當前字符左鄰第一個字以及第二個字的標注信息，要得到該信息可以對特征模板k～o進行如下組合：

4.3.2 實驗結果

我們一共進行了12組實驗，實驗所用的模板以及實驗結果如表6所示。

表6 使用不同特征模板集合得到的分詞結果

從實驗結果可以看出，用第(8)組模板得到了最高的F值。

通過不同實驗之間的對比，可以大致總結出如下結論：

(1) 11_1與11_2，12_1與12_2比較均表明：特征模板m，o似比特征模板k，l更加有效。尤其在OOV_recall方面，特征模板l，k對召回率影響較大。因為特征模板l需要知道該字符左鄰字符的信息，因此該特征具有稀疏性，而特征模板o只需知道該字符左鄰字符的標記，不具有稀疏性。

(2) 11_1與12_2比較表明：特征模板l易造成OOV_recall降低，因為對于未登錄詞來說，提供更多的字符標記信息比提供字符信息更加有用。

(3) 11_2與12_1比較表明：特征模板o與特征模板m，n相比，前者對f值有貢獻，后者對OOV_recall有貢獻。

(4) 13_2與14_1比較表明：f值越高并不意味OOV_recall也越高。

(5) 整體來說，在特征模板給定合理的情況下，特征模板的數量越多，訓練效果越好。

(6) 每個特征模板都有存在的必要，缺少一個都會使F值下降。

(7) 特征模板o對OOV_recall的貢獻比較大。

4.4 實驗四：用不同的迭代次數對語料進行訓練

在這個實驗中，我們用到的語料與實驗一相同，使用四個標記的標記集(SBME標記)，在M3N工具上進行訓練和測試，使用3.2節中的特征模板 a～m(即可以使F值達到最大的特征模板集)。通過進行不同迭代次數的實驗，檢驗其對分詞結果的影響。得到的實驗結果如表7所示：

表7 使用不同迭代次數得到的分詞結果

為了更直觀地對實驗結果進行分析，得到該結果的線狀圖如圖1所示。

圖1 不同迭代次數與分詞精度的關系

從圖中可以看出，F值并沒有隨著迭代次數的增加而增加，其中F值在21次迭代處達到最大值，對應表4可以看出，OOV_recall在15和21次迭代處達到最大值，說明OOV_recall不會隨F值的增大而增大。

此外，隨著迭代次數的不斷增加，訓練時間增加的幅度也比較大，但時間的代價并沒有得到效果的提升。

4.5 實驗五：用不同規模的語料進行訓練

在這個實驗中，我們使用四個標記的標記集(SBME標記)，使用3.2節中的特征模板a～m，在M3N工具上進行訓練和測試。保持測試語料規模不變，每次增加5%的訓練語料(在最后一組實驗(1∶50)中，我們增加了20%的實驗數據)。

得到的訓練語料與測試語料的相關信息如表8所示：

表8 測試語料與不同規模訓練語料的相關結果

實驗結果如表9所示：

表9 使用不同訓練語料規模得到的分詞結果

在實驗1∶50中，F值達到了0.992 851，這是因為在該實驗中，OOV_rate非常小，只有0.000 126(71個詞)。

為了更直觀地對實驗結果進行分析，得到該結果的線狀圖如圖2所示。

圖2 不同規模訓練語料與分詞精度的關系

從圖中可以看出，當訓練數據集合較小時，F值較低(實驗1∶5)。F值大體上隨著訓練語料規模的增大而增大，但實驗 1∶15 得出的結果比實驗 1∶20 得到的結果略高。

從表9中可以看出，OOV_recall在整個實驗中變化幅度不大。

該實驗同時說明，字符標注的方法比較好地解決了未登錄詞的識別問題，且解決能力在訓練集較小時也很有效。這是因為字標注的過程能夠平衡地看待詞表詞和未登錄詞的識別問題[1]。

根據實驗的結果，我們也可以看出未登錄詞識別問題仍然是困擾漢語切分問題的瓶頸。隨著訓練語料規模的逐步增大，切分精度穩步上升，但未登錄詞召回率卻一直維持在70%的水平。分詞精度之所以提升，是因為測試語料中未登錄詞的數量越來越少。在實際應用中，未登錄詞的數量往往是不可控制的，需要切分的實際語料規模常常會多于切分系統的訓練語料，因此如何加強未登錄詞的處理能力就值得認真考慮。為此，我們的初步考慮如下：一是引入專門的未登錄詞處理識別預處理模塊，并將識別結果以特征函數形式納入基于M3N模型的分詞程序；二是探索半指導的學習技術，使得在面向特定的切分任務時，能以補充任務中語料的方式增加切分系統的適應性。

5 結束語

最大間隔馬爾可夫網模型是一種將最大間隔原則與無向圖模型結合所提出的一種結構學習模型，理論上該模型具有較好的推廣能力，本文將該模型用于漢語分詞任務并進行了相關實驗驗證，總體來看，基于最大間隔馬爾可夫網模型的分詞性能較好，與基于CRF模型的分詞系統性能具有可比性，甚至略為領先。

不過，與CRF模型類似，M3N模型訓練的時間代價也是相當大的，訓練算法的優化應是結構化學習模型需要關心的問題。此外，M3N模型支持核函數，我們也將在未來的工作中考察核函數的引入是否會引起分詞性能的改善。

[1] 黃昌寧，趙海. 中文分詞十年回顧[J]. 中文信息學報，2007，21(3)：8-19.

[2] N. Xue. Chinese Word Segmentation as Character Tagging[J]. Computational Linguistics and Chinese Language Processing, 2003, 8(1), 29-48.

[3] 李雙龍，劉群，王成耀. 基于條件隨機場的漢語分詞系統[J]. 微計算機信息，2006，22，(10-1): 178-200.

[4] 遲程英，于長遠，戰學剛. 基于條件隨機場的中文分詞方法[J]. 情報雜志，2008，(5)：79-81.

[5] Ben Taskar, Carlos Guestrin，Daphne Koller. Max-Margin Markov Networks[C]//Proceedings of Neural Information Processing Systems Conference(NIPS), 2003.

[6] Huang Chu-Ren, Yo Ting-Shuo, Petr Simon and Hsieh Shu-Kai. A Realistic and Robust Model for Chinese Word Segmentation[C]//Proceedings of the 20th Conference on Computational Linguistics and Speech Processing(ROCLING), 2008.

[7] 孫茂松，肖明，鄒嘉彥. 基于無指導學習策略的無詞表條件下的漢語自動分詞[J]. 計算機學報，2004,27(6):736-742.