基于ＦＭＭ和ＣＲＦｓ雙層分詞模型的研究

摘要：中文分詞是眾多自然語言處理任務的基本工作。該文提出了一個用雙層模型進行中文分詞的方法。首先在低層利用前向最大匹配算法（FMM）進行粗分詞，并將切分結果傳至高層；在高層利用CRFs對文本重新進行標注，其中低層的識別結果作為 CRFs 的一項特征。最后將對每個字的標注結果轉換為相應的分詞結果。跟以前單獨利用CRF 進行分詞的模型相比，低層模型的加入對CRFs模型的標注起到了重要的輔助作用。在北京大學標注的1998年1月份的人民日報語料上進行了大量的實驗，取得了精確率93.31%，召回率92.75%的切分結果，證明該方法是切實可行的。

關鍵詞：前向最大匹配算法；條件隨機場；雙層模型；召回率

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)28-0166-03

Research on Two-level Word Segmentation Based on FMM CRFs

LU Qiang，JIN Wei-zu

(Tongji University，Shanghai 201804，China)

Abstract: Chinese word segmentation is the basic work of the many natural language processing tasks. This paper presents a two-level model of Chinese word segmentation. We first use the Former Max Matching algorithm (FMM) to generate rough segmentation results in the lower level， and send the rough results to the higher level. Then segment the text again based on CRFs， and set the rough results as one feature. Finally convert the label to the corresponding results of segmentation. Compared with the former model based on CRF separately， the cascaded model based on CRFs and FMM is more powerfully. Our approach is evaluated on large-scale corpus with open test method using People's Daily (1998). The results show that this approach based on FMM and CRFs is efficient in word segmentation， and the recalling rate achieves 92.75% and the precision rate achieves 93.31%.

Key words: former max matching algorithm; conditional random fields; two-level model; recalling rate

1 引言

中文分詞是中文信息處理的前提，是自然語言處理的一項基礎性工作。很多自然語言處理的任務都建立在分詞的基礎之上，分詞的準確程度直接影響到一系列后續處理的正確性，如自動索引、自動分類、信息檢索、信息抽取等。但由于漢語自身的復雜性，分詞問題一直是中文自然語言處理的難題。

人們已經提出了許多分詞方法，根據所使用的知識資源不同分為基于規則的方法，基于統計的方法。基于規則的方法一般都需要事先有人工建立好的分詞詞典和分詞規則庫。主要是基于字符串匹配的原理進行分詞，如最大匹配算法[1]，這一類的算法復雜度一般比較高，無法有效的解決歧義問題，而且在未登錄詞比較多的時候，無法達到較好的分詞效果。現階段基于統計的方法已經越來越多的應用到自然語言處理的眾多任務之中，主要應用的統計模型有：互信息、N元文法模型、神經網絡模型、隱馬爾可夫模型（HMM）和最大嫡模型（ME）等[2-4]。隱馬模型需要嚴格的獨立性假設，而大多數數據不可能表示成一系列獨立的數據；最大熵模型可以容納較多的上下文信息，但是由于局部歸一化而存在著標記偏置的缺陷。

CRFs（Conditional Random Fields）模型 [5] 是當今最先進的序列標注模型之一，它的使用使基于字的分詞方法有了更大的提高。Fuchun Peng等人已經做了一系列的實驗 [6] ，證明該模型的性能要優于其他的統計模型。但是該模型的標注效果和特征選擇是緊密相關的，因此仍有改進的余地。

本文分析了一個雙層分詞模型，首先在低層利用前向最大匹配算法（FMM）對文本進行粗切分，然后將切分結果傳至高層；在高層利用CRFs進行標注，并將低層的結果作為CRFs的特征之一。該特征的加入有效的提高了標注精度，取得了較好的分詞效果。

2 CRFs模型

John D.Lafferty等將CRFs（Conditional Random Fields）模型用在序列標注的問題上。其核心思想是利用無向圖理論使序列標注的結果達到在整個序列上全局最優。CRFs模型克服了傳統的隱馬爾可夫模型（Hidden Markov Model， HMM）和最大熵馬爾可夫模型（Maximum Entropy Markov Model， MEMM）的標記偏置等問題。

2.1 CRFs模型算法描述

CRF是無向圖模型的一種形式，在給定將要標記的觀測序列的情況下，無向圖模型可以被用來在標記序列上定義一個聯合概率分布。假設X，Y分別表示需要標記的觀察序列和它對應的標記序列的聯合分布隨機變量，條件隨機場（X，Y）就是一個以觀測序列X為全局條件的無向圖模型。

通常，我們定義G=(V，E)是一個無向圖，Y={Yv/v∈V}。即V中的每個結點對應著一個隨機變量所表示的標記序列的成分Yv。因而，整個圖和與圖相關的分布類別以X為條件，所以與G相關的聯合分布的類別的形式是P(y1，…，yn/X)，這里y和X分別是類別序列和觀測序列。如果每個隨機變量Yv滿足關于G的馬爾可夫屬性，給定X和Yv以外的所有隨機變量，則隨機變量Yv的概率式如下：

P(Yv/X，Yu，u≠v)=P(Yv/X，Yu，u ~ v)

其中。u ~ v，表示u與v在圖G中相鄰，那么(X，Y)就是一個條件隨機場。

理論上，圖G的結構可以是任意的，它描述標記序列中的條件獨立性。但在建立模型時，最簡單和最普遍的無向圖結構是線性鏈的結構，與Y的元素相對應的結點形成了一個簡單的一階鏈(First-order Chain)。我們將這種條件隨機場稱為線性鏈條件隨機場(CRFs)。

在給定觀測序列X的情況下，CRFs模型定義標記序列的概率可表示如下：

■

Z是歸一化因子：

■

其中每個fk(yi-1，yi，x)是觀察序列X中位置為i和i-1的輸出節點的特征，每個gk(yi，x)是位置為i的輸入節點和輸出節點的特征，λ和μ是特征函數的權重。我們分別為訓練數據中的每一個狀態-狀態對(y'，y)和狀態-觀察值對 (y，x) 定義特征如下：

■

■

現在我們用CRF建立了P(Y|X)的統計模型，求解序列標記任務就是求得Y*滿足P(Y|X)最大，可表示如下：

■

使用Viterbi等動態優化方法，即可求出最優解Y*。

2.2 標注集的選擇

本文將分詞任務轉換為序列標注任務，首先要定義適合該任務的標注集合，標注集合的選擇也直接影響到識別的效果。近幾年的基于序列標記的分詞系統中，廣泛的通過字在詞中的位置來定義標注集。最常用的是四字位的標注集；后來又出現了六字位的標注集；詳細信息如表1所示。下表給出了這兩種標注集的描述；我們通過實驗和分析，發現六字位的標注集能取得更好的效果，因此本文采用六字位的標注集。

表1四字位、六字位的詳細信息

■

3 基于FMM和CRFs的雙層分詞模型

模型的識別流程圖如圖1所示。

3.1 語料的預處理

由于語料中存在大量的數字、符號、時間詞即字母等，這些一般都是未登錄詞，一方面非常容易造成切分錯誤，另一方面又為切分提供了有用的信息，比如文本中有多個字母連續出現的情況時，即可得到一些潛藏的信息，這些連續的字母可以作為一個詞切分出來。因此本文將這些特殊的情況進行特殊處理。

我們將文本中的字分為五大類：1）普通漢字，如“我”“學”等，其類別標為1；2）數字，如0，1，二，三等，其類別標為2；3）符號，包括標點符號和其他的特殊符號，如“”“￥”等，其類別標為3；4）時間詞，如“年”“時”等，其類別標為4；5）字母，如“A”“b”等，其類別標為5。

首先根據上述分類對語料進行標注，使每一個字都屬于某一類。

3.2 FMM的粗切分模型

我們首先在模型的低層，采用正向最大匹配算法（FMM）對文本進行粗切分。FMM的具體算法可以描述如下：

設Maxlen表示最大詞長D為分詞詞典。

1) 從待切分語料中按正向取長度為Maxlen的字串str，令Len=Maxlen。

2) 把str與D中的詞相匹配。

3) 若匹配成功，則認為該字串為詞，指向待切分語料的指針向前移Len個漢字，返回到步驟（1）。

4) 若匹配不成功，如果Len大于1，則把Len減1，從待切分語料中取長度為Len的字串str，返回到（2）。否則，得到長度為1的單字詞，指向待切分語料的指針向前移動1個漢字，返回到（1）。

FMM方法原理簡單，易于在計算機上實現，時間復雜度也比較低，但是識別精度有限。我們將該粗分結果按照前面標記集的定義轉換成六字位的標記形式，以便于應用到高層的分詞模型中。

3.3 CRFs的標記模型

CRFs具有很強的推理能力，能夠使用復雜的、重疊性的和非獨立的特征進行訓練和推理，還可以任意地添加其他外部特征，同時解決了最大熵模型中的標記偏置問題和隱馬模型的獨立性假設，是一個優秀的序列標注器。因此本文在高層采用基于字的CRFs對文本進行重新標注。

采用CRFs進行標注時非常重要的一步是針對特定的任務選擇合適的特征集。原則上是選擇的特征越多越好，但特征過多又會產生冗余信息，反而降低識別精度。本文選擇兩類特征：原子特征和復合特征，以下分別做簡要介紹。

1）原子特征：為充分利用字的上下文信息、類別等影響分詞的因素，可以使用原子特征模板，我們需要從以下幾方面考慮：

首先，字本身包含的信息非常的豐富，而且是最容易得到的，因此這是必不可少的一類特征。

其次，通過前面的分析可以知道不同類型的字對切分的指導作用是不同的，因此字的類型也是非常有用的一類特征。

再次，低層的粗切分結果無疑可以帶給CRFs更多的上下文信息，這是一類非常重要的特征。

綜合上面的考慮，我們選定原子特征如下表2所示：

表2原子特征表

■

其中n為表示位置的變量，取值為-1，0，1。n=0表示當前位置，n=-1表示當前位置的前一位置，n=1表示當前位置的后一位置。

原子特征均用二值函數來表示，當特征函數取特定值時，特征模板被實例化，就可以得到具體的特征。

2）復合特征：由于在真實文本中，影響分詞的因素往往不只一類，若只考慮原子特征模板并不能很好的反映實際情況，因而需要同時考察多個因素。對上面表中所示的原子特征模板進行適當的組合，即得到表3所示的復合特征模板。由于復合特征多為原子特征組合而成。因此，通常條件下復合特征比原子特征更為復雜。如果使用復合特征過多還可能導致模型效率下降，通過實驗確定復合特征如表3所示：

表3復合特征表

■

在復合特征模板實例化過程中，首先將每個原子特征模板實例化，然后結合當前標注結果來構成復合特征。與原子特征的表示方法類似，復合特征也同樣用二值函數來表示。復合特征的加入更好的挖掘了有用的上下文信息，進一步提高了分詞的精度。

3.3 后續處理

由于不同的上下文環境會產生不同的識別結果，因此同一個詞在不同的環境中可能被切分為不同的結果，導致前后結果不一致的情況發生。我們將置信度大于某閾值的標注結果提取到一個詞典中，在最后進行一次二次掃描，，這樣可以修正一部分標注結果不一致的情況，在一定程度上提高了識別精度。

4 實驗與評估

4.1 評測標準與語料

選取的評價標準如下：

機構名識別精確率：■

機構名識別召回率： ■

機構名識別F值：■

本文選取的語料是北京大學標注的1998年1月份的人民日報。

4.2 實驗結果

我們一共設計了三個實驗，實驗一是只采用CRF進行分詞，實驗二將FMM與CRF結合進行分詞，實驗三增加后續處理，實驗結果如表4所示：

表4實驗結果表

■

通過上面的實驗結果可以看出，FMM的加入提高了0.3個百分點，后續處理對結果的影響較小，但也在一定程度上提高了分詞精度，達到了相對滿意的分詞效果。

5 本文總結以及今后工作

本文提出了一個有效的雙層分詞模型，把FMM與CRFs較好的結合在一起。首先在低層采用FMM進行粗切分，然后將該結果作為CRFs的特征之一，在高層對文本進行重新標注。我們在對CRFs的特征選擇上進行了深入的研究，加入了粗分結果和字的類型兩類非常有效的特征，提高了標注的精度。最后還進行了一個有效的后處理，解決了部分標注不一致的情況，進一步提高了分詞精度，實驗證明該方法是有效的。

如果在低層利用雙向最大匹配算法，則能進一步提高粗分的精度，這是下一步實驗的方向。另外對CRFs的特征選擇方面，沒有對一些領域知識進行考察，下一步可以從語言學角度進行分析，增加更有效的特征。

參考文獻：

[1] 陳力為，袁琦.中文信息處理應用平臺工程[M].北京:電子工業出版社，1995.

[2] 李家福，張亞非.基于EM算法的漢語自動分詞算法[J].情報學報，2002，21(3):269-272.

[3] 陳桂林，王永成.一種改進的快速分詞算法[J].計算機研究與發展，2000，37(4):418-424.

[4] 劉群，張華平，俞鴻魁，等.基于層疊隱馬模型的漢語詞法分析[J].計算機研究與發展，2004，41(8):1421-1429.

[5] Zhao H， Huang C N， Li M， et al. Effective tag set selection in Chinese word segmentation via conditional random field modeling[A]. In: PACLIC-20[C]，Wuhan，China，，2006:87-94.

[6] Peng F C， Feng F F， McCallum A. Chinese segmentation and new word detection using Conditional Random Fields[A].In: COLING 2004 [C]， Geneva， Switzerland，2004:562-568.