基于詞邊界分類的中文分詞方法

李壽山，黃居仁

(香港理工大學 中文及雙語學系，香港)

1 引言

自動分詞是中文計算機處理中的一個基本任務[1]。該技術是實現眾多中文應用系統的前期基礎，例如：中英(英中)機器翻譯、信息檢索、文本自動分類等。由于中文詞邊界本身的歧義性，加上大量新詞的不斷涌現，中文自動分詞一直是中文信息處理中的一個長期且艱巨的任務。針對該任務，中文信息處理研究領域先后出現了大量的自動分詞方法。

長期以來，分詞的方法都是基于詞(或詞典)的[2]。例如基于規則的最大匹配方法[3]或者基于統計的詞的N元語法方法[4]。 在大規模詞典的幫助下，基于詞的分詞方法取得了比較好的效果。但是該方法在識別未登錄詞(OOV)時，結果并不理想，然而未登錄詞的識別在分詞系統的應用中是不可避免的問題。近幾年來，基于字的分詞方法漸漸得到相當的關注，在這幾次的Sighan評測中占主導地位。該方法將分詞問題轉化為字的分類問題，即判斷文本的字是否為某詞的開始或者結束[5]。相對于基于詞的分詞方法，基于字的分詞方法的最大優點就是能夠取得令人滿意的OOV識別率。盡管如此，由于基于字的分詞方法需要構建高維的向量空間，而且分類的樣本非常龐大，這使得該方法訓練和測試的時間復雜度和空間復雜度都非常高。因此，該方法還不能滿足一些真正實用的實時分詞系統。我們認為一個優秀的實時分詞系統不僅僅需要快速對新樣本進行分詞，還需要能夠迅速學習新的標注樣本(該特性我們稱之為在線學習能力[6])。而目前基于字的分詞方法訓練需要時間太長，很難滿足以上的要求。

文獻[7]首先提出一種基于詞邊界分類的分詞方法(Word Boundary Decision，以下簡稱該方法為WBD)。該方法直接對分詞的任務建模，判斷字同字之間的邊界是否為詞的邊界。換言之，該方法視分詞為一個兩類分類問題。相對于一般的基于字的分類方法，類別的數目有所減少，從而降低了分類的復雜度。本文將介紹該分詞方法并進一步完善該方法，使得它能夠獲得接近目前主流方法的分詞效果。在此基礎上，我們將提出一種基于WBD的在線學習分詞方法，能夠快速學習新標注樣本。鑒于WBD方法的時間復雜度和空間復雜度遠遠小于基于字的分詞方法，我們能夠利用它構建一個更實用的分詞系統。

本文其他部分安排如下：第2部分詳細介紹基于詞邊界分類的分詞方法并提出我們的一些改進；第3部分提出基于WBD的在線學習分詞方法；第4部分給出實驗結果及分析；第5部分給出相關結論。

2 基于詞邊界分類的分詞方法(WBD)

2.1 WBD方法

自動分詞的基本任務是將一段由字串組成的文本切割成由詞組成的詞序列。舉例來說，一段分詞前的字序列為“共同創造美好的新世紀”，而分詞后的詞序列為：“共同 創造 美好 的 新 世紀”。這樣做是便于計算機識別和處理比較完整的一些語義單位，如“創造”、“美好”等，從而有利于進一步的文本處理，如自動翻譯、信息檢索等。

WBD方法的目標是判斷每兩個字之間的邊界是否為詞邊界。我們形式化表示一段文本為：

c1I1c2I2,...,ciIi,...,cn-1In-1cn

其中ci表示一個中文字符，Ii表示任意兩個字之間的字邊界。在原始的中文文本中，這些字邊界沒有明顯的顯示出是否為詞邊界。我們設定如果該字邊界為詞邊界，則記為Ii=1，否則Ii=0。WBD的方法就是直接判斷某個字邊界是否為詞邊界。因此，在WBD中，分詞任務被轉化為一個兩類分類問題。然而在基于字的分詞方法中，一般會把字的類別數目定義為“開始”、 “中間” 、“結束”和“單字”。在類別數目上面來說，WBD方法要比基于字的分詞方法更簡單。

WBD方法大致分為兩個步驟：N-gram概率信息統計和邊界的向量表示。下面分別介紹這兩個步驟。

在第一個步驟中，該方法通過收集訓練樣本中的詞邊界信息，即N-gram字串關于詞邊界的統計信息。文獻[7]中給出了5種不同的unigram和bigram特征的統計信息，它們分別為PCB、PBC、PCCB、PCBC和PBCC。這些統計信息具體是指N-gram字串相對于詞邊界的出現概率。其中PCB定義如下：

其中C(ci,Ii=1) 表示在訓練語料中字符ci出現在詞邊界前面的次數。而C(ci)表示字符ci在訓練語料中出現的總次數。

另外，PCCB的定義如下：

其中C(ci-1,ci,Ii=1)表示在訓練語料中二元字符串ci-1,ci出現在詞邊界前面的次數。而C(ci-1,ci)是二元字符串ci-1,ci在訓練語料中出現的總次數。

其他三個概率信息,PBC(Ii=1|ci+1)，PCBC(Ii=1|ci,ci+1)和PBCC(Ii=1|ci-2,ci-1) 具有類似的定義。為了簡單起見，下面我們分別用PCCB(Ii),PCBC(Ii),PBCC(Ii),PCB(Ii),PBC(Ii)表示這5個概率信息統計量。一旦獲得了所有N-gram字符串的概率信息，我們將這些數據保存在一個字典中，供以后構建向量使用。我們命名這個包含統計信息的字典為“N-gram數據源”。

在第二個步驟中，WBD方法將所有的字邊界表示為下面的向量：

WBD的訓練過程和測試過程都會將所有字邊界表示為這種向量。剩下的就是一個典型的模式分類問題。我們可以采用各種不同的統計分類方法去訓練和測試。由于該向量的維度很低，僅僅需要幾千個樣本就足夠訓練出一個比較好的分類器[8]。這一點與基于字的分詞方法不同，基于字的分詞方法需要訓練大量的樣本向量。因此，WBD方法大大降低了訓練時間。為了更清晰的了解WBD方法，我們給出文本“共I1同I2創I3造I4美I5好”中每個字邊界的向量實例，如表1所示。其中，在N-gram數據源中未出現的字串概率一律賦值為0.50。

表1 一段字串的字邊界向量實例

2.2 WBD方法的進一步完善

在已有的WBD方法的框架基礎上，我們提出一系列進一步完善的措施，包括概率估計的平滑、新N-gram的引入和數字英文字符的預處理。

在估計概率的時候，往往會出現某些字符在語料中出現次數很少的情況，利用上面的統計公式統計概率會帶來很大的誤差。為了減小這些誤差給分類帶來的影響，我們盡量使頻率出現很少的概率趨向于0.5。以PCB為例，我們改寫概率估計函數如下：

另外，上面介紹的WBD方法僅僅考慮到了unigram和bigram字符串的統計信息。在實際分詞任務中，為了捕捉更遠的分詞信息，從而更好地識別多字符的詞，我們引入trigram字符串的統計信息。trigram字符串包括CCCB、CCBC、CBCC和BCCC，對應的概率值分別為PCCCB(Ii)、PCCBC(Ii)、PCBCC(Ii)和PBCCC(Ii)。我們將在實驗部分測試這些新特征對分詞效果的影響。

為了進一步提高WBD方法的分詞效果，我們在進行統計N-gram字符串概率之前利用正則表達式進行所有數字和英文字符的識別和替換。

3 基于WBD方法的在線學習分詞方法

優秀的實時分詞系統不僅僅需要快速對新樣本進行分詞，還需要能夠迅速學習新的標注樣本，只有這樣，才能讓系統能夠快速引入不斷涌現的新詞。換言之，系統應該具備在線學習的能力。在線學習(Online Learning)是指系統在輸入新的標注樣本后，不需要重新學習原始的訓練樣本，只是針對新來的標注樣本學習就可以了。目前，在線學習本身作為機器學習的一個重要的研究問題，備受模式識別，機器學習，自然語言處理等學術屆的重視。

需要強調的是WBD方法的核心部分是N-gram數據源，如果加入新的標注樣本，只需要更新N-gram數據源，就相當于更新了訓練數據。以其中一個概率PCCB(Ii)為例，更新的概率公式如下：

其中C(ci-1,ci,Ii=1)和C(ci-1,ci)是N-gram數據源里面字符串ci-1ci的詞頻信息。這些數據都是已經有的，不需要重新學習。Cnew(ci-1,ci,Ii=1)和Cnew(ci-1,ci)則是新標注樣本里面字串ci-1ci的統計信息。Cnew(ci-1,ci,I=1)表示在新訓練語料中二元字符串ci-1,ci出現在詞邊界前面的次數，而Cnew(ci-1,ci) 是二元字符串ci-1,ci在新訓練語料中出現的總次數。其他幾種N-gram的更新公式同上式類似。在實際應用中，如果待測樣本和新標注樣本比較接近的話，可以通過提高新樣本里面統計詞頻的權重來加重新標注樣本對后期分詞的影響。

除了更新N-gram數據源之外，訓練階段不需要任何其他的操作。因此，基于WBD的在線學習方法，需要再學習的代價非常小，可以滿足實時系統中的分詞需要。

4 實驗

在本實驗中，我們將首先詳細給出WBD的分詞效果，其次，我們將測試上面提出的基于WBD的在線學習方法。

我們使用第二屆國際分詞競賽(Bakeoff-2005)中的四組語料對WBD分詞方法進行測試。每組語料中的訓練語料用于生成各自的N-gram數據源，并隨機生成訓練樣本中的1 000個字邊界的向量訓練一個SVM(Support Vector Machine)分類器。在測試過程中，測試語料中的所有字邊界由該組的N-gram數據源生成向量。然后用訓練好的SVM分類器進行測試。

我們使用基于詞的F值作為評估標準，它是準確率P和召回率R的調和平均值：F=2RP/(R+P)。為了和相關工作比較，我們也列出了未登錄詞的召回率(OOV recall)。表2～表5分別給出了WBD方法及其一些改進方法在四組測試語料上面的分詞結果。其中，基準的實現過程完全按照文獻[7]里面的描述，只用了5個N-gram的字符串特征。

表2 WBD及其改進方法在Pku語料測試語料上的結果

表3 WBD及其改進方法在Cityu語料測試語料上的結果

表4 WBD及其改進方法在Msr語料測試語料上的結果

表5 WBD及其改進方法在As語料測試語料上的結果

在改進的方法中，我們只報告了CCBC和CBCC的結果，這是因為CCCB和BCCC字串的加入對結果基本沒有影響。從這些表中可以看出，平滑在兩個語料上都有較好的表現，在另外兩個語料中基本保持原來的分詞效果。其他兩個改進在所有的語料中都有不同程度的提高。

為了便于比較WBD同基于字的分詞方法，我們利用Porket CRF[9]工具實現了基于字的分詞方法，實驗使用了字符的四種標識類別[10]。表6中給出該方法在Pku和Msr兩個語料上面的封閉測試結果(沒有用到數字英文字符識別)。相對于CRF實現的基于字的分詞方法，雖然WBD的分詞效果要稍微差一點，但是WBD所需要的訓練時間(包括N-gram字符串概率的搜集和SVM分類器的訓練)要遠遠小于CRF的訓練時間(我們用python實現的WBD方法)。

在實際分詞系統的應用中，訓練樣本和測試樣本并不能像分詞競賽那樣限制為來自相同來源。為了模擬實際分詞無法預知測試語料來源的狀況，我們交換了Pku和Msr的測試語料。也就是說，我們讓CRF和WBD在Pku的訓練語料上面訓練，但是在Msr的測試語料上面測試，這樣分詞的F值結果會大大減低到0.856和0.850(Pku→Msr)。在這個時候，CRF和WBD方法的差異已經小到沒有統計上的相關性了。

表6 WBD與CRF實現的基于字標注的分詞方法的比較結果

最后，我們利用WBD方法構建一個真正實用的分詞系統，該系統使用Sinica研究院平衡語料產生N-gram數據源。該語料是來自中國臺灣研究員的繁體語料，由于Sinica語料在各個領域的分布比較均勻，我們認為該語料庫能夠比較好的反映各種字符串同詞邊界的關系[11]。為了測試我們系統的效果以及上面提到的基于WBD的在線學習方法，我們使用部分Cityu的訓練樣本用作我們系統新的標注樣本。圖1給出了我們系統在Cityu測試語料上面的F值結果，橫坐標表示加入新樣本的規模。從圖中可以看出，在不使用任何Cityu訓練樣本的情況下，我們的系統已經取得了近88%的F值。如果利用我們的在線學習方法，漸漸融入少量Cityu的訓練樣本，系統的表現會越來越好。

圖1 系統在Cityu測試語料上面的F值

圖2 系統在Cityu測試語料上面的OOV Recall值

圖2給出系統在引入新語料后的OOV Recall值的變化曲線。從該圖可以看出，系統性能提高的一個重要原因就是新的語料給系統帶來了許多新詞，例如：“海陸空”、“社工”等詞，使得系統能夠更好的分好這些新詞。通過對比在線學習前后的分詞結果，我們還發現另外一個提高系統性能的重要原因：Cityu測試語料和Sinica語料的分詞標準在某些詞方面不一致，而加入Cityu的少量訓練語料，能夠有效的校正不同的分詞標準。例如：在Sinica訓練語料里面，“有 些”被認為是兩個詞，而在Cityu里面“有些”被認為是一個詞。另一個出現比較多的例子是，在Sinica訓練語料里面，“x月x日”分詞為“x月 x 日”(其中“x”代表數字，“x”和“日”是分開的)，而在Cityu里面被分為“x月 x日”(“x”和“日”是不分開的)。

5 結論

本文研究了一種基于詞邊界分類的分詞方法并提出改進方法。在此基礎上， 我們實現了一種在線學習的分詞方法。實驗結果表明，這種新的分詞方法能夠獲得接近目前主流方法的分詞效果，但只需要很少的訓練時間。同時，我們利用提出的在線學習分詞方法和Sinica研究院平衡語料庫構建了我們的分詞系統，該系統能夠在來自不同地方的語料中獲得比較滿意的分詞效果，并且能夠很迅速地學習新的樣本，使我們的系統具備很好的更新能力。

[1] 黃昌寧. 中文信息處理的分詞問題[J]. 語言文字應用, 1997, 11(1):72-78.

[2] 黃昌寧, 趙海. 中文分詞十年回顧[J]. 中文信息學報, 2007, 21(3):8-20.

[3] 駱正清, 陳增武, 胡上序. 一種改進的MM分詞方法的算法設計[J]. 中文信息學報, 1996，10(3): 30-36.

[4] 吳春穎, 王士同. 基于二元語法的N-最大概率中文粗分模型[J]. 計算機應用, 2007, 27(12): 332-339.

[5] Xue N. and L. Shen. Chinese word segmentation as LMR tagging[C]//Proceedings of the Second SIGHAN Workshop on Chinese Language Processing. 2003.

[6] Crammer K., O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms[J]. Journal of Machine Learning Research, 2006(7): 551-585.

[9] http://sourceforge.net/project/showfiles.php?group_id=201943[OL].

[10] Ng H. and J. Low. Chinese part-of-speech tagging: one-at-a-time or all-at-once? Word-based or character-based?[C]//Proceedings of EMNLP. 2004.

[11] CKIP. Academia Sinica Balanced Corpus of Modern Chinese[OL]. http://www.sinica.edu.tw/SinicaCorpus/. 2001.