任惠,林鴻飛,楊志豪

(大連理工大學計算機科學與技術學院,遼寧大連116024)

1 引言

自動分詞是中文信息處理的基礎,歧義切分問題是分詞過程中需要解決的難點之一(另一難點是未登錄詞識別)[1],它直接影響分詞系統(tǒng)的精度。從歧義字段的構成上看,分詞歧義可以分為兩種類型：即交集型歧義和組合型歧義。其中交集型歧義是文本中主要切分歧義類型,約占全部歧義的 85%以上,有關它的定義可以參考文獻[2-3]。近年來,交集型歧義的切分問題吸引了眾多研究者目光,迄今為止,多種方法被提出,這些方法大體可分為三類：基于規(guī)則的方法、基于實例的方法和基于統(tǒng)計的方法。

基于規(guī)則的方法利用人工編寫的語法規(guī)則消解交集型歧義,取得了一定的效果[4]。但人工編寫不可避免會遇到系統(tǒng)性、有效性、一致性和可維護性等規(guī)則系統(tǒng)的“天然”問題困擾[5],如今面對互聯(lián)網上大規(guī)模真實文本處理的壓力,純規(guī)則的方法基本被拋棄。

基于實例的方法事先搜集歧義字段及其正確的切分形式形成實例庫[6-7],文獻[3,8]在庫中還存儲實例的上下文信息,歧義消解通過庫檢索即可實現(xiàn)?；趯嵗椒ê唵斡行?但其消歧能力依賴于庫中實例的數量,泛化能力弱,常常作為其他方法的補充。

為克服上述兩類方法的缺陷,研究人員嘗試了多種統(tǒng)計的方法。有指導的概率統(tǒng)計方法通過計算待消歧字段所有可能的切分路徑的概率,并把概率最大者作為消歧字段的消解結果[9-10];無指導的統(tǒng)計方法利用互信息和 t-測試差解決歧義切分問題[11];有些研究人員將歧義消解問題轉化為分類問題,通過分類模型來消解歧義[2,12-13]。上述方法均取得了較好效果,但也存在一些問題,主要集中在消歧知識不足、消歧對象受限、消歧精度有待提高和模型特征難以獲取四個方面。

近年來,最大熵模型被廣泛用來解決各種自然語言處理問題,如：分詞[14]、詞性標注[15]、實體識別[16]、Chunk識別[17]、句法分析[18]和機器翻譯[19]等,對上述問題都達到或超過了其他方法的最好結果。與其他統(tǒng)計機器學習方法相比,最大熵方法能夠將各種不同的知識融合在統(tǒng)一的算法框架中,且獨立于特定的任務,具有模型簡潔、通用和易移植的優(yōu)點。鑒于該方法在上述諸多自然語言處理題上都取得了相當優(yōu)異的性能,我們也采用它來解決交集型歧義。我們首先將交集型歧義的消解問題轉化為一個二分問題,然后利用融合豐富字特征的最大熵模型來解決該分類問題。此外,為了克服建模時的數據稀疏問題,我們引入了不等式平滑技術[20]和高斯平滑技術[21],它們都是通過放松標準最大熵建模時的特征期望等式約束來改善數據稀疏問題。本文的另一大特色是我們選擇基于字的特征而不是基于詞的特征作為消歧知識。我們這樣做基于如下理由：首先基于字的特征可以直接從未切分文本中獲取,這使得本文的算法可以在任何自然語言處理應用中直接應用,大大降低了本算法的應用難度?；谠~特征的消歧算法在應用時另外需要一個單獨的分詞程序。其次,基于字的特征比基于詞的特征更加緊湊,這是因為中文詞是一個開放集,真實文本中未登錄詞的比例比生字要高得多。第三,我們觀察到在分詞任務上,字特征比詞特征更加有效[14]。我們相信在組合型歧義消解問題上依然有效,因為在解決這兩個分類任務時都需要相同的知識源。最后,基于字的特征可以產生豐富的單字、雙字、多字這樣交疊性特征,而最大熵模型最大的優(yōu)點就是能夠將各種特征融合到一個統(tǒng)一的框架,通過逐步增加特征來提高性能。

本文提出的方法較好地彌補了前人工作的一些不足。首先,模型特征融合了豐富的消歧特征,這些特征不僅包含歧義字段及其上下文信息,還包含歧義字段與其上下文相混合信息。以前的方法僅僅利用歧義字段及其前后詞、詞性和互信息作為消歧知識源[2,12-13],消歧知識的不足使消歧對象受限,也制約了消歧性能。文獻[13]僅能消解三字長偽歧義,而文獻[12]僅能消解三字長偽歧義和部分三字長真歧義,而本文不僅能處理偽歧義,也能處理真歧義;不僅能消解三字長歧義,也能消解其他長度的歧義,同時使消歧性能也大幅度的提高。其次,我們使用基于字的特征,這些特征無需統(tǒng)計、分詞及詞性標注等深層處理,可直接從文本中抽取,大大降低了算法應用難度。而以前的方法或需要統(tǒng)計信息,或需要詞匯和詞性信息作為特征[12-13],在歧義消解時需要詞匯詞性等深層信息,分詞和詞性標注的錯誤不可避免地傳播到歧義消解階段。最后,以前的方法[2,12-13]都沒有采取平滑措施緩解數據稀疏問題,而本文通過采用平滑措施來放松模型中的特征期望約束,有效緩解數據稀疏問題,使得消歧性能得到進一步提高。

我們在第三屆國際分詞競賽的四個數據集上進行了測試,分別獲得了96.27%、96.83%、96.56%、96.52%的消歧正確率,對比實驗表明：豐富的特征使消歧性能分別提高了5.87%、5.64%、5.00%、5.00%,平滑技術使消歧性能分別提高了0.99%、0.93%、1.02%、1.37%,不等式平滑使分類模型分別壓縮了38.7、19.9、44.6、9.7。我們的方法在四個不同的數據集上獲得了相同的結論,證明了我們方法在不同數據集上的一致性。

2 利用不等式最大熵模型消解交集型歧義

2.1 問題定義

本文將交集型歧義消解問題轉化為分類問題,分類空間定義在歧義字段的FMM和BMM切分結果Of和Ob中。這樣交集型消解問題可以轉化為一個二分問題：

其中,Seg(Seg∈{Of,Ob})是歧義字段的消歧結果,P(O f|C)表示在條件C下歧義字段切分結果為Of的概率,P(Ob|C)表示在條件C下歧義字段切分結果為Ob的概率。這樣,消歧過程就是根據公式(1)選擇較大概率的過程。

2.2 最大熵模型

最大熵原理要求建模時擬合所有已知事實,而對未知事實不做任何附加假設。與其他的統(tǒng)計機器學習方法相比,最大熵模型能夠方便將各種不同的知識(特征)融合在一個統(tǒng)一的算法框架而不需要在這些特征之間存在任何獨立性假設。最大熵模型能夠應用于任何分類問題,對于交集型歧義消解任務而言,它為歧義字段的每種分類結果(Of,Ob)產生一個條件概率,該條件概率可以通過公式(2)計算得到：

其中C表示了歧義字段擁有的特征集,Seg是歧義字段的分類結果,Zλ(x)是正規(guī)化常數。fi表示了第i個特征,k是該歧義字段擁有的特征總數,最大熵建模時要求每個特征的經驗期望值與模型估計期望值相等。即：

前者為 fi在訓練樣本中的經驗期望值,后者是fi在模型估計時的模型期望值。

2.4 模型平滑與特征選擇

從某種程度上講,最大熵模型也是一種最大似然對數模型,同其他最大似然估計方法一樣,當訓練數據比較稀疏時,模型也會過度擬合訓練數據,這說明應用最大熵法解決NLP任務也需要進行平滑。當前各種平滑算法被引入最大熵模型[21]。文獻[21]在多個NLP任務上,考察了高斯平滑技術與其他平滑技術,測試結果表明：高斯平滑技術在所有NLP任務上都獲得同等或者優(yōu)于其他其他方法的性能。該方法本質上是利用高斯先驗分布通過公式(4)來懲罰那些正值或負值很大的權重,使模型更少擬合訓練數據。

最近文獻[20]提出一種稱為不等式平滑技術的胖約束,通過賦予期望約束一定寬度的滑動范圍來放松該公式(3)所規(guī)定的特征期望約束：

公式中Ai,Bi是第i個特征的寬度滑動范圍,通過該滑動范圍,可以放松每個特征的期望相等約束(傳統(tǒng)最大熵模型規(guī)定每個特征的理論期望值應該與通過訓練語料計算得到的該特征的期望相等),使得模型不會過度擬合訓練數據。

文獻[20]在兩個文本分類任務上比較了不等式平滑技術和高斯平滑技術,測試結果表明采用不等式平滑技術比結合頻度折扣的高斯平滑技術更優(yōu),本文也通過實驗對各平滑技術在緩解模型數據稀疏問題上的效果進行了對比。

2.5 特征選擇

特征選擇的任務是從訓練樣本所有特征中挑出期望值能被可靠估計的特征,不是所有的特征對分類能力都有貢獻,太多的特征不僅會增加模型的訓練時間,而且導致模型過度擬合訓練樣本。常用的特征選擇方法有：基于信息增益的方法及其近似算法[22]和基于頻度折扣的方法[15,17]。基于信息增益的方法每次選擇使模型熵增加最多的特征,使得每次特征選擇階段都要計算所有特征的信息增益,因此耗時較多;基于信息增益的近似算法認為加入一個特征后的模型僅依賴于原來的模型和參數λ,該方法比較快,但是不能保證每次加入模型的特征都是最好的;基于頻度折扣的方法事先根據經驗設定或者根據開發(fā)集來調節(jié)折扣閾值K,特征選擇時認為頻度小于或等于K的特征都不可靠,只挑選那些頻次大于 K的特征,但是 Walter Daelemans et al.[23]指出低頻特征也包含對分類有貢獻的信息。所以,我們在采用基于頻度折扣的特征選擇方法時,不是事先設定一個固定的閥值,而是在一定范圍內窮舉所有可能的閥值,根據開發(fā)集來確定最佳閥值。另外,不等式平滑技術能夠將特征選擇與參數估計無縫結合在一起,從模型中除去那些權重為零的特征而不會影響模型的分類行為。Kazam a和Tsujii[20]演示了不等式平滑技術在特征選擇上比頻度折扣方法更優(yōu),我們在實驗中采用該方法。

2.6 參數估計

參數估計用來求解公式(2)中參數λ,參數估計常用的方法有：通用迭代算法(GIS)[24]、改進的迭代算法(IIS)[22]、梯度法和變度量法及其變體等。文獻[25]在四個NLP任務上考察了 GIS、IIS、梯度法和有限存儲變量尺度法(LMVM)(變度量法的一種變體),結果顯示：對于NLP分類問題,LMVM性能最好。文獻[20]測試了限界約束有限存儲變量尺度法(BLMVM)(LMVM 一種變體)[26]也證實了類似結論,并指出,在真實NLP數據集上,BLMVM能在更短的時間達到收斂,而且分類性能有所提高,因此我們在實驗中使用BLMVM進行參數估計。

3 特征表示

3.1 利用臨界切分法切分文本

歧義檢測是消解歧義的前提。目前歧義檢測的主要方法有：雙向最大匹配法[27]、最小分詞法[28]、全切分法[29]和臨界切分法[30]等。前兩種方法都存在檢測盲點,全切分法雖然無檢測盲點,但它的切分路徑隨文本長度成指數增長,而臨界切分法不僅能檢測出所有歧義,而且其切分路徑只隨文本長度成線性增長。文獻[3]詳細介紹了上述每種方法優(yōu)劣并給出了相應的檢測實例。

本文中,我們利用臨界切分法切分文本,并將切分得到的臨界段作為部分消歧知識源。文獻[30]給出了臨界切分法的定義并證明：給定詞表,對于任意文本,無論該文本怎樣被切分,臨界點都是文本中所有非歧義的切分邊界,相鄰兩臨界點間字符構成一個臨界段。臨界切分法的示例見圖1。

圖1 臨界切分法示例

算法先逐字正向最大匹配待切分文本,再檢查匹配得到的詞之間是否相互交叉覆蓋關系,并將交叉覆蓋的詞凝聚成更長的串,如：“地產”、“產”和“房地產”被凝聚成“房地產”;“從前”、“前所未有”、“所”、“未”、“有的”、“的”被凝聚成“從前所未有的”,直到所有串之間不存在任何交叉覆蓋關系。臨界切分法將文本分割成臨界段序列,不同臨界段中的字符不相關,而所有相關的字符都必然包含在同一臨界段內。

3.2 特征模板

最大熵模型分類能力取決于是否選擇合適足夠的模板,為此我們設計了豐富的基于字的特征模板。并把它們分為歧義字段上下文信息模板,歧義字段自身信息模板和混合信息模板。這些模板詳細定義見表1。

這些模板中,C表示文本中的字符。模板1表示歧義字段周圍六個字符,模板4中Cs表示歧義字段的第一個字符,Ce表示歧義字段最后一個字符。模板2表示歧義字段周圍三個臨界段,我們用CF0表示歧義字段自身,這些臨界段可以通過3.1中臨界切分法獲得。模板6表示歧義字段自身包含的漢字體個數。模板1、3、4、6、7獨立于具體語言,因為這些模板能夠應用于任何語言,并且當它們作用于具體的訓練數據時,特征值能從模板中自動獲取。而模板2和5依賴于具體語言。

表1 交集型歧義消解用的模板特征定義

4 實驗

4.1 實驗數據準備和歧義字段分布

實驗數據來自第三屆國際分詞競賽提供的四個訓練語料和測試語料。我們從四個訓練語料中分別抽取交集型歧義字段及其特征(特征模板見表1)形成樣本空間作為訓練集,從四個測試語料中抽取交集型歧義字段及其特征作為測試集。歧義檢測采用臨界切分法,臨界切分法所用的詞表直接從各自訓練語料中獲取。因為本文主要考察最大熵模型的分類能力,對于那些切分結果不在分類空間(O f或Ob)中的歧義字段,我們將它們從樣本中剔除出去。表2顯示了各個訓練集、開發(fā)集和測試集中的交集型歧義分布情況。

表2 訓練集、開發(fā)集和測試集中的交集型歧義分布情況

4.2 模型訓練和控制參數調節(jié)

在實驗中,我們比較了結合頻度折扣的標準最大熵模型(Cut-off)、高斯最大熵模型(Gaussian)和不等式最大熵模型(Inequality)三種平滑技術,模型中的參數λ采用BLM VM[26]進行估計,最大熵模型軟件包來自互聯(lián)網[31],實驗中所使用的版本為1.3.2。該軟件包提供了這三種模型的訓練和測試接口,這樣我們能夠在同等基礎上比較這些模型的性能。實驗中我們來計算消歧正確率(消歧正確率=(利用最大熵算法正確消歧的個數)/(測試語料中交集型歧義的個數))。由于最大熵模型中需要事先確定某些控制參數,我們利用開發(fā)集在一定范圍內以窮舉的方式搜索最好的控制參數,也就是說,當模型在開發(fā)集上達到最佳性能時,即可得到最佳控制參數。標準最大熵模型的控制參數是頻度閾值cthr,

我們在[0,5]范圍內以步長為1的遞增方式進行窮舉式搜索;高斯最大熵模型的控制參數是方差σ,雖然公式(4)允許我們?yōu)槊糠N不同的特征采用不同的方差,在實驗中我們使用相同的方差,并在[100,1 000]范圍內以步長為100的遞增方式進行窮舉式搜索;不等式最大熵模型的控制參數是寬度因子W,雖然公式(5)允許每種特征的寬度因子可以不同,實驗中我們?yōu)樗刑卣髟O置相同的寬度因子W,并分別在[10-5,10-1]區(qū)間中以10倍遞增方式和[0.1,1]區(qū)間以步長為0.1的遞增方式進行窮舉式搜索。實驗中我們采用公式(6)來計算每個寬度值：

表3給出了各種模型在各個開發(fā)集上的最優(yōu)控制參數值。

表3 最優(yōu)控制參數一覽表

4.3 測試

利用得到的各種最優(yōu)模型對測試集進行測試。表5顯示了不等式平滑技術的特征選擇能力,相比最優(yōu)Cut-off模型,不等式平滑技術能有效壓縮模型規(guī)模。

表5 不等式平滑技術的特征選擇能力

為了考察豐富的語言知識對消歧能力的貢獻,我們僅僅采用CFn(n=-3,-2,-1,1,2,3)作為消歧使用的特征,采用最優(yōu)Inequality模型上對4個測試語料進行了測試,結果如表6所示。

表6 簡單特征和豐富特征不同消歧能力的比較

可以看出,豐富的語言特征對于消歧性能有顯著的影響,在各個測試子集上,后者比前者至少提高5%。

5 結論和未來的工作

我們采用最大熵法消解中文文本中交集型歧義,取得了優(yōu)異的性能,使用最大熵法消解在訓練集中未出現(xiàn)的交集型歧義字段,也達到很高的性能,說明模型具有很強的泛化能力,實驗還驗證了高斯平滑和不等式平滑技術比單純的頻度折扣具有更強的分類能力,而高斯平滑和不等式平滑技術之間不分伯仲,同時還揭示出豐富的語言知識對消歧性能有顯著的影響。實驗所采用的高斯模型和不等式模型的控制參數比較簡單,每種特征使用相同的控制參數,沒有體現(xiàn)出模型的優(yōu)勢,所以在更大規(guī)模語料上采用更復雜的控制參數是有待深入的工作。另外本文與其他基于分類的方法[2,12-13]一樣,分類空間限制在Of和Ob,遺漏了切分結果不是Of和Ob的歧義字段,我們可以采用其他方法如基于實例的方法來處理這些歧義,或者將這些歧義字段單獨作為一類,這也是今后需要嘗試的工作。

致謝 感謝Jun'ichi Tsujii提供最大熵軟件開發(fā)包。

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

[2] Mu Li,Jianfeng Gao,Chang-Ning H uang and Jianfeng Li.Unsupervised training for overlapping ambiguity resolution in Chinese w ord segmentation[C]//Proceedings of the Second SIGHAN Workshop on Chinese Language Processing,Sapporo,2003：1-7.

[3] Qinan Hu,H aihua Pan and Chunyu Kit.2004.An examp le-based study on Chinese word segmentation using critical fragments[C]//Proceedings of the First International Joint Conference on Natural Language Processing(IJCNLP-04),Sanya,Hainan,2004,505-511.

[4] Bing Sw en and Shiwen Yu.A Graded Approach for the Efficient Reso lution of Chinese W ord Segmentation Ambiguities[C]//Proceedings o f 5th Natural Language Processing Pacific Rim Symposium.Beijing,Nov,1999：19-24.

[5] 孫茂松,鄒嘉彥.中文自動分詞研究評述[J].當代語言學,2001,3(1)：22-32.

[6] 孫茂松,左正平.消解中文三字長交集型分詞歧義的算法[J].清華大學學報(自然科學版),1999,5：101-103.

[7] Jin Guo.One Tokenization per Source[C]//ACL-98,M ontreal,Canada,1998：457-463.

[8] Chunyu Kit and Xiaoyue Liu.An Example-Based Chinese Word Segmentation System for CWSB-2[C]//Proceedings of the Fourth SIGHAN Workshop on Chinese Language Processing,Jeju Island,2005：146-149.

[9] 孫茂松,左正平,鄒嘉彥.高頻最大交集型歧義切分字段在漢語自動分詞中的作用[J].中文信息學報,1999,13(1)：27-34.

[10] 陳小荷.用基于詞的二元模型消解交集型分詞歧義[J].南京師大學報(社會科學版),2005,6：109-113.

[11] 孫茂松,黃昌寧,等.利用漢字二元語法關系解決漢語自動分詞中的交集型歧義[J].計算機研究與發(fā)展,1997,5：332-339.

[12] 張鋒,樊孝忠.基于最大熵模型的交集型切分歧義消解[J].北京理工大學學報(自然科學版),2005,25(7)：590-593.

[13] 李蓉,劉少輝,葉世偉,史忠植.基于SVM 和k-NN結合的漢語交集型歧義切分方法[J].中文信息學報,2001,15(6)：13-18.

[14] Nianw en Xue.ChineseWord Segmentation as Character Tagging[J].International Journal of Computational Linguistics and Chinese Language Processing,2003,8(1)：29-48.

[15] Adwait Ratnaparkhi.A Maximum Entropy Part-Of-Speech Tagger[C]// Proceedings o f the Empirical M ethods in Natural Language Processing Conference,University of Pennsylvania,1996.

[16] Hai Leong Chieu and Hw ee Tou Ng.Named Entity Recognition with a Maximum Entropy Approach[C]//Proceedings of H LT-NAACL,2003,4：160-163.

[17] Rob Koeling.Chunking w ith Maximum Entropy M ode ls[C]//Proceedings of CoNLL-2000 and LLL-2000.Lisbon,Portugal.

[18] Xiaoqiang Luo.A maximum entropy Chinese character-based parser[C]//EMNLP-2003.2003：192-199.

[19] Franz Josef Och and H ermann Ney.Discrim inative T raining and Maximum Entropy M odels for StatisticalMachine Translation[C]//ACL-2002.

[20] Jun'ichi Kazama and Jun'ichi Tsujii..Maximum Entropy Models with Inequality Constraints：A case study on text categorization[J].M achine Learning Journal special issue on Learning in Speech and Language Technologies.2005,60(1-3)：169-194.

[21] Stan ley Chen and Ronald Rosen feld.A survey o f smoothing techniques for M E models[J].IEEE T ransactions on Speech and Audio Processing,2000,2：37-50.

[22] Stephen Della Pietra,Vincent Della Pietra,and John Lafferty.Inducing features of random fields[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(4)：380-393.

[23] Wa lter Daelemans,Antal van den Bosch and Jakub Zav rel.Forgetting Excep tions is Harm ful in Language Learning[J].Machine Learning,1999,34(1-3)：11-41.

[24] J.N.Darroch and D.Ratcliff.Generalized Iterative Scaling for Log-Linear M odels[J].The Annals of Mathematical Statistics,1972,43(5)：1470-1480.

[25] Robert Malouf.A comparison ofalgorithm s formaximum entropy parameter estimation[C]//Proceedings of CoNLL-2002,Taipei,2002：49-55.

[26] Steven J.Benson and Jorge J.M or′e A limitedmemory variab lemetric method for bound constrained optim ization[R].Technical Report ANL/MCS-P909-0901,A rgonne National Laboratory,2001.

[27] 劉源,梁南元.漢語處理的基礎工程-現(xiàn)代漢語詞頻統(tǒng)計[J].中文信息學報,1986,1(1)：17-25.

[28] 王曉龍,王開鑄,李仲榮,白小華.最少分詞問題及其解法[J].科學通報,1989,13：1030-1032.

[29] 馬晏.基于評價的漢語自動分詞系統(tǒng)的研究與實現(xiàn),語言信息處理專論[M].北京：清華大學出版社,2-36.

[30] Jin Guo.Critical tokenization and its p roperties[J].Computational Linguistics,1997,23(4)：569-596.

[31] Jun'ichi Tsujii.http：//www-tsujii.is.s.u-tokyo.ac.jp/～tsuruoka/maxent/.A simp le Maxent Toolkit[DB/OL].