歸一化的鄰接變化數方法在中文分詞中的應用

何賽克，王小捷，董 遠,3，張韜政，白 雪

(1. 北京郵電大學 信息與通信工程學院，北京 100876；

2. 北京郵電大學 計算機科學與技術學院，北京 100876；

3. 法國電信北京研發中心，北京 100190)

1 前言

詞是自然語言處理(NLP)中的基本單元，因為它為進一步進行處理提供了詞匯層面的基礎。由于中文文本中缺少定界符，如空格，這使得中文分詞(CWS)變成一項有趣而又具有挑戰性的任務。

目前，機器學習方法已被成功應用于自然語言處理的各個領域。由于中文分詞可被看作一個簡單而有效的序列標注問題，條件隨機場(CRFs)[1]成為中文分詞的一個主流方法。雖然，條件隨機場對已登錄詞(Known Words，在測試語料和訓練語料中均出現的詞)有著較高的準確率，但是，中文分詞系統的性能在很大程度上受制于其對未登錄詞(Unknown Words，在測試語料中出現，而未在訓練語料中出現)的處理能力。因此，如何對未登錄詞進行切分，成為中文分詞中的一個亟待解決的問題。

本文基于我們在第四屆國際中文自然語言處理(Bakeoff-4)*第一屆中國中文信息學會漢語處理評測(CIPS-CLPE)暨第四屆國際中文自然語言處理Bakeoff (Bakeoff-4)http://www.china-language.gov.cn/bakeoff08/參賽的中文分詞系統，引入了一種無監督的學習方法(Unsupervised Learning)。這種方法最初源于對語音流的切分[2]，并且已被成功的用于分詞[3]及詞語提取[4]任務。針對這種無監督方法在訓練數據過少時的不足，本文提出了一種改進的方法。最后給出實驗數據及結果分析。

2 中文分詞系統(CWS)的架構

在自然語言處理領域，CRFs是用于中文分詞的一項主流技術。根據前人的工作[5]，本文使用一階線性鏈式CRFs作為中文分詞系統的基本架構。

2．1 條件隨機場(CRFs)

對于序列標注問題，條件隨機場較產生式模型(如HMMs)及判別式模型(如MEMM) 有著明顯的優勢。CRFs基于一個無向圖：G=(V,E)，其中V是隨機變量集合：Y={Yi|1≤i≤n}，代表輸入文本序列中的每個字符。E是邊集合：E={(Yi-1,Yi) |1≤i≤n}，這些邊組成一條線性鏈。在給定輸入序列：(o1,o2，…，on) 的條件下，狀態序列：(s1,s2，…，sn) 的條件概率定義如下：

(1)

其中，fk為特征函數；λk為其對應特征函數的權重；Z0是個歸一化因子，用于保證概率的歸一性?，F在，原問題可被看作是一個最優化問題：使用迭代算法，如L-BFGS[6]，使得整個句子的條件概率PΛ(s|o)最大化。

2．2 標記集

前人的工作[3-4]表明，6-tag 標記集能夠使CRFs達到更好的性能。因此，本文中的CWS系統也采用此種標記集，即：B，B2，B3，M，E 以及S。

表1 6-tag范例

2．3 特征模板

表2描述了CWS系統中使用的特征，其中C代表字符，下標n代表特征相對于當前字符的位置。Pun指示當前字符是否為標點符號。T為當前字符的類別屬性：數字為第一類；時間和日期為第二類；英文字符為第三類；標點符號為第四類；其他字符為第五類。

表2 CWS系統中使用的特征集

3 無監督的分詞

除了上面的N元語法特征外，本文還將使用一種稱為鄰接變化數的無監督分詞(Unsupervised Segmentation)結果作為輔助特征，這樣可以從統計上捕獲更多的關于詞的邊界信息，從而進一步提升系統的性能。

3．1 鄰接變化數方法(Accessor Variety)

在中文文本中，句子中的每一個字串都可以成為一個潛在的詞，然而只有那些能夠表達特定含義的子串可以形成一個真正意義上的詞。鄰接變化數方法(AV)[4]反映子串在上下文語境中的靈活程度。如果子串的靈活性越強，那么它就更加有可能是一個詞。一個字串s的鄰接變化數定義如下：

AV(s)=min{Lav(s),Rav(s)}

(2)

其中， Lav(s) 是子串s的左鄰接變化數，它被定義為子串s的不同前驅字符的數目，加上它在不同句首出現的次數； Rav(s) 為子串s右鄰接變化數，它被定義為子串s的不同后繼字符的數目，加上它在不同句尾出現的次數。

在本文中，針對鄰接變化數方法在訓練數據過少時表現出的不足(Bakeoff-4中的數據就是如此)，提出了一種改進的方法。在此將采用一種改進版本的鄰接類別方法——歸一化的鄰接變化數(Normalized Accessor Variety, NAV)來作為無監督的分詞標準，下面將做詳細介紹。

3．2 目標函數

給定句子中某個特定字串的鄰接變化數計算公式，分詞問題就可被看作是一個優化問題，即：使得定義在一個句子上所有子串AV值的目標函數(target function)最大化。一個由n個中文字符構成的句子s，其切分結果S可表示為由m個詞構成的詞串：

s=c1c2c3…ci…cnS=w1w2w3…wi…wm

(3)

其中ci代表字符，wi代表切分后的一個詞。此時，目標函數F的定義為：

(4)

其中，f(wi)為AV函數，其定義為：

f(w)=|w|c×ACd(w)

(5)

|w|為子串w的字符數，參數c取值為整數。盡管AV函數有很多種定義方式，但是，在此我們采用多項式形式的AV函數，這在前人的工作[4]中被證實十分的有效。通常情況下，可獲得的訓練數據十分有限，因此對于那些具有較多字符的字串和具有極少字符的字串，在使用公式(5)計算子串w的AV值時，就會存在一些波動，進而導致AV值不具有很強的統計意義。比如：僅由單個漢字構成的子串，如助詞“的”，或疑問詞“嗎”往往會被賦予較低的AV值，從而使得它們與其臨近詞造成“粘連”，盡管它們被當做單個詞來看可能會更好一些；而對于那些由較多漢字構成的子串，雖然它們不能表達任何的實際意義，僅僅由于它們的共現頻率很高，往往會被賦予一個較高的AV值。因此，我們有必要對上述兩種子串進行區別對待。然而，公式(5)中隱含的這個潛在問題，在過去的研究[3-4]中均被忽略了(至少沒有被詳細的闡述過)。為了解決這個問題，我們提出了一種歸一化的AV函數f(Normalized Accessor Variety, NAV)來減弱在AV值計算時產生的波動，歸一化的AV函數f*的定義如下：

(6)

在公式(5)的基礎上，我們引入了一個實值的歸一化因子Norm。公式(6)是基于這樣的考慮：一方面，當子串w中包含的字符足夠多時，除非其按(5)計算出的AV值很高，否則我們將不認為w為一個詞，在公式(6)的計算標準下，w將會得到一個較低的AV值；另一方面，當子串w中包含的字符過少時，除非其按公式(5)計算出的AV值也很低，否則，在公式(6)的計算標準下，w仍然會得到一個較高的AV值。這個度量標準不需要對單字詞和多字詞進行分別處理，并且在一定程度上緩和了由于訓練數據過少而造成的AV值計算上的波動，因此能夠更加真實的反映子串在上下文中的靈活程度。

有了上述定義，就可以計算一個句子s的目標函數F(S)了。由于切分后句子中的每個詞wi可以被獨立的計算，因此F(S)可以通過動態規劃的方法來計算求得，這種方法的時間復雜度與句子長度呈線性關系。令fi為每個子句c1c2…ci的目標函數值，wj…i代表詞cj+1cj+2…ci(j≤i)，那么可以得到下面的動態規劃公式：

f0=0;

f1=f(w1…1=c1);

f(S)=fn

(7)

值得注意的是，在每次迭代過程中，最多有N個可能的選擇詞(我們的實驗中最大詞長N=6)。

3．3 AV特征

在確定了AV值的計算公式及目標函數的形式后，如何利用AV值有兩種選擇：(1)將基于AV值的無監督的分詞結果(即6-tag標記集)作為CRFs模型的輔助特征。(2)直接將每個字串的AV值作為其特征。在后一種方式中，我們需要定義一個特征函數來對AV值的連續取值空間進行量化，以得到離散的AV值，從而避免數據稀疏(Data Sparsity)的問題。在這里，我們采用如下定義的特征函數[3]：

fn(s)=t, if 2t≤AV(s)<2t+1

(8)

其中，t是一個正整數，用它來對AV值取對數。因為前人研究工作中沒有任何證據表明上述兩種使用特征的方式中，哪種效果更好一些，因此我們在實驗部分做了一組實驗來對此給出一個明確的回答。

4 實驗結果

本文的實驗基于Bakeoff-4中提供的中文分詞數據，共來自5個數據集：CITYU, CKIP, CTB, NCC 和 SXU。其中CITYU的數據是繁體中文，而其他數據則是簡體中文。

在Baseline CWS系統(僅僅使用有監督的學習)架構中，首先使用三重交叉驗證來訓練初始的CRFs模型，并用這3個訓練好的模型來測試剩下的一份語料，之后transformation-based error-driven learning (TBL)通過比較訓練語料和三個初始的CRFs的測試結果來完成訓練。表 3 列出了我們在開放測試中分別用于訓練CRFs和TBL的語料。

表3 分別用于訓練CRFs和TBL的語料

在這個基本架構的基礎上，我們引入了NAV來進一步提升分詞系統的性能。為了深入的分析NAV對分詞系統性能的影響，我們做了一組對比試驗，這將在后續的實驗中見到。

在后面的實驗中，無監督方法中最大的分詞長度設為6，因為中文文本中長度大于6的詞比較少見；公式(6)中的兩個參數c和d分別取值為1和2(這是沿用了在實驗中的最佳參數設置)。值得一提的是，所有子串的AV值都是基于全部語料計算得到的，即：全部訓練語料和測試語料。

為了得到一種更好的AV值的使用方式，表4中給出一組對比試驗的實驗結果。其中“Auxiliary Seg”是指將基于AV值的無監督的分詞結果，即標記集：B，B2，B3，M，E以及S，作為CRFs模型的輔助特征?！癗AV value” 是指直接將每個字串的AV值(通過特征函數離散化后)作為其特征。在NAV方式下， 公式(6)中的參數Norm取值為2.5， 這在本文之前的實驗中取得了最好的效果。表4中的實驗結果表明：采用“NAV”方式的效果較好。這個結論可以解釋為 “Auxiliary Seg”中的標記錯誤在一定程度上干擾了CRFs的學習過程。因此，在后面的實驗中，我們將采用“NAV”值賦值的方式來使用AV特征。

為了證實NAV在封閉集上的有效性，表5列出了四種系統在CWS的性能比較。其中“BaseLine”代表我們參加Bakeoff-4的基準系統，它僅僅利用了表2中定義的特征，在后處理階段，僅僅使用了一致性檢測；“+AV”表示在“BaseLine”系統的基礎上加入了AV特征；“+NAV”表示在“BaseLine”系統的基礎上加入了NAV特征；“Best”代表在相應的封閉測試集上當時最好系統的性能。實驗結果表明鄰接變化數方法(AV)能夠提升基于CRFs架構的CWS系統的性能，而基于NAV的CRFs性能最好。這正是由于NAV緩和了AV值的波動，從而使性能有了進一步的提升。然而，值得指出的是，NAV在CTB數據集上的性能較AV方式略有下降，但仍然高于“BaseLine”系統的性能。一個合理的解釋是Norm取2.5對于CTB數據來說可能并不是最佳的參數設置。

表5 四個系統在CWS封閉測試集上的性能比較(未使用TBL)*官方結果可以從以下網址下載：http://www.china-language.gov.cn/bakeoff08/bakeoff-08_basic_chs.html。

表7 列出了四個系統在開放測試集合上的性能比較(Norm=2.5)。在此實驗組中引入額外數據訓練TBL，此時要驗證NAV是否還會帶來性能的進一步提升。在開放測試中，由于沒有額外的訓練數據，因此未對NCC和SXU進行實驗。通過比較表5和表6中“BaseLine”系統的性能可以發現，在表6中引入的TBL大幅度地提升了CWS系統的性能，這是因為大量的額外信息被加入到了系統中，從而為系統提供更加豐富的語言學知識。與此同時，這導致AV和NAV能夠挖掘的額外的上下文信息變得更加少了，從而使得在開放測試中的性能提升不如封閉測試中那么明顯。

表6 四個系統在CWS開放測試集上的性能比較(使用了TBL)

從表7中可以看出，當公式(6)中的參數Norm設為2.5時，NAV的性能較好。另外值得注意的是，當Norm參數取值在[2，3]之間的時候，NAV的性能良好。但是，在本文的實驗過程中，當Norm取值超過此范圍時，性能會有不同程度的惡化，這是個需要進一步改進的地方。

表7 不同Norm設置下，NAV在 CWS封閉測試任務中的性能

5 結語

在自然語言處理中，中文分詞系統的性能在很大程度上受制于其對未登錄詞的處理能力，而僅僅依靠有監督的學習是無法解決這個問題的。本文提出了一種無監督和有監督相結合的中文分詞方法，即：將鄰接變化數方法引入基于條件隨機場的中文分詞系統中，并對鄰接變化數方法固有的缺陷進行了改進。實驗結果表明：NAV的性能在原有AV方法的基礎上，又有了進一步的提升。最后，AV函數的選取及參數的設置對無監督學習部分的性能有著直接影響，這將是NAV方法需要進一步改進的地方。

[1] J. Lafferty, A. McCallum, and F. Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data [C]//Proceedings of the 18th ICML, San Francisco, CA. 2001: 282-289.

[2] Zellig Sabbetai Harris. Morpheme within words [C]//Papers in Structural and boundaries Transformational Linguistics, 1970: 68-77.

[3] Hai Zhao and Chunyu Kit. Unsupervised Segmentation Helps Supervised Learning of Character Tagging for Word Segmentation and Named Entity Recognition [C]//The Sixth SIGHAN Workshop on Chinese Language Processing (SIGHAN-6), Hyderabad, India, 2008: 106-111.

[4] Haodi Feng, Kang Chen, Chunyu Kit, and Xiaotie Deng. Unsupervised segmentation of Chinese corpus using accessor variety [C]//K.-Y. Su, J. Tsujii, J. H. Lee, and O. Y. Kwong, editors, Natural Language Processing- IJCNLP 2004, volume 3248 of Lecture Notes in Computer Science, Springer Berlin/Heidelberg. Sanya, Hainan Island, China. 2005: 694-703.

[5] Xinnian Mao, Yuan Dong, Saike He, Sencheng Bao and Haila Wang, Chinese Word Segmentation and Name Entity Recognition Based on Condition Random Fields [C]//The Sixth SIGHAN Workshop on Chinese Language Processing (SIGHAN-6), Hyderabad, India. 2008.

[6] R.H. Byrd, J. Nocedal and R.B. Schnabel. Representations of quasi-Newton matrices and their use in limited memory methods [J]. Mathematical Programming, 1994,(63): 129-156.