中文分詞演算法簡介

04-30

本文原文發布在我的個人博客 >>

什麼是中文分詞

與大部分印歐語系的語言不同，中文在詞與詞之間沒有任何空格之類的顯示標誌指示詞的邊界。因此，中文分詞是很多自然語言處理系統中的基礎模塊和首要環節。

下面以jieba的示例給讀者一個對分詞的感性認識。

【全模式】: 我/ 來到/ 北京/ 清華/ 清華大學/ 華大/ 大學【精確模式】: 我/ 來到/ 北京/ 清華大學【新詞識別】：他, 來到, 了, 網易, 杭研, 大廈【搜索引擎模式】：小明, 碩士, 畢業, 於, 中國, 科學, 學院, 科學院, 中國科學院, 計算, 計算所, 後, 在, 日本, 京都, 大學, 日本京都大學, 深造

中文分詞的方法和評價指標

從20世紀80年代或更早的時候起，學者們研究了很多的分詞方法，這些方法大致可以分為三大類：

基於詞表的分詞方法

正向最大匹配法(forward maximum matching method, FMM)
逆向最大匹配法(backward maximum matching method, BMM)
N-最短路徑方法

基於統計模型的分詞方法

基於N-gram語言模型的分詞方法

基於序列標註的分詞方法

基於HMM的分詞方法
基於CRF的分詞方法
基於詞感知機的分詞方法
基於深度學習的端到端的分詞方法

在中文分詞領域，比較權威且影響深遠的評測有 SIGHAN - 2nd International Chinese Word Segmentation Bakeoff。它提供了2份簡體中文和2份繁體中文的分詞評測語料。

Sighan中採用的評價指標包括：

準確率(Precision)
召回率(Recall)
F-測度(F-measure)
未登錄詞的召回率(ROOV)
詞典詞的召回率(RIV)

各指標計算公式如下:

$Precision=frac{WordCount(CorrectResults)}{WordCount(TrainSet)}$

$Recall==frac{WordCount(CorrectResults)}{WordCount(TestSet)}$

$F1=frac{2*P*R}{P+R}$

各分詞方法的細節

正向最大匹配法(FMM)

正向最大匹配法，顧名思義，對於輸入的一段文本從左至右、以貪心的方式切分出當前位置上長度最大的詞。正向最大匹配法是基於詞典的分詞方法，其分詞原理是：單詞的顆粒度越大，所能表示的含義越確切。

負向最大匹配法(BMM)

反向最大匹配法的基本原理與正向最大匹配法類似，只是分詞順序變為從右至左。容易看出，FMM或BMM對於一些有歧義的詞處理能力一般。舉個例子：結婚的和尚未結婚的，使用FMM很可能分成結婚/的/和尚/未/結婚/的；為人民辦公益,使用BMM可能會分成為人/民辦/公益。

雖然在部分文獻和軟體實現中指出，由於中文的性質，反向最大匹配法優於正向最大匹配法。在成熟的工業界應用上幾乎不會直接使用FMM、BMM作為分詞模塊的實現方法。

基於N-gram語言模型的分詞方法

由於歧義的存在，一段文本存在多種可能的切分結果（切分路徑），FMM、BMM使用機械規則的方法選擇最優路徑，而N-gram語言模型分詞方法則是利用統計信息找出一條概率最大的路徑。

上圖為南京市長江大橋的全切分有向無環圖(DAG)。可以看到，可能的切分路徑有：

南京/市/長江/大橋
南京/市/長江大橋
南京市/長江/大橋
南京市/長江大橋
南京/市長/江/大橋
南京/市長/江大橋
南京市長/江/大橋
南京市長/江大橋
…

假設隨機變數S為一個漢字序列，W是S上所有可能的切分路徑。對於分詞，實際上就是求解使條件概率P(W∣S)最大的切分路徑W?，即

$W^{*}=argmax_W P(W|S)$

根據貝葉斯公式，

$W^{*}=argmax_W frac{P(W)P(S|W)}{P(S)}$

由於P(S)為歸一化因子，P(S∣W)恆為1，因此只需要求解P(W)。

P(W)使用N-gram語言模型建模，定義如下(以Bi-gram為例)：

$P(W)=P(w_{1}w_{2}cdots w_{T})= P(w_{1})*P(w_{2}|w_{1})cdots *P(w_{T}|w_{T-1}) =prod_{t=1}^{T}widehat{P}(w_{t}|w_{1}^{t-1})$

至此，各切分路徑的好壞程度(條件概率P(W∣S))可以求解。簡單的，可以根據DAG枚舉全路徑，暴力求解最優路徑；也可以使用動態規劃的方法求解，jieba中不帶HMM新詞發現的分詞，就是DAG + Uni-gram的語言模型 + 後向DP的方式進行的。

基於HMM的分詞方法

接下來介紹的幾種分詞方法都屬於由字構詞的分詞方法，由字構詞的分詞方法思想並不複雜，它是將分詞問題轉化為字的分類問題（序列標註問題）。從某些層面講，由字構詞的方法並不依賴於事先編製好的詞表，但仍然需要分好詞的訓練語料。

規定每個字有4個詞位：

詞首 B
詞中 M
詞尾 E
單字成詞 S

由於HMM是一個生成式模型，X為觀測序列，Y為隱序列。

$P(X , Y)=prod_{t=1}^{T} P(y_{t}|y_{t-1})*P(x_{t}|y_{t})$

熟悉HMM的同學都知道，HMM有三類基本問題：

預測(filter)：已知模型參數和某一特定輸出序列，求最後時刻各個隱含狀態的概率分布，即求 P(x(t) ∣ y(1),?,y(t))。通常使用前向演算法解決.
平滑(smoothing)：已知模型參數和某一特定輸出序列，求中間時刻各個隱含狀態的概率分布，即求 P(x(k) ∣ y(1),?,y(t)),k<t。通常使用forward-backward 演算法解決.
解碼(most likely explanation): 已知模型參數，尋找最可能的能產生某一特定輸出序列的隱含狀態的序列. 即求 P([x(1)?x(t)] ∣ [y(1)?,y(t)]), 通常使用Viterbi演算法解決.

分詞就對應著HMM的解碼問題，模型參數(轉移矩陣，發射矩陣)可以使用統計方法計算得到，原始文本為輸出序列，詞位是隱狀態序列，使用Viterbi演算法求解即可。具體方法請參照參考資料#2。

jieba的新詞模式就是使用HMM識別未登錄詞的，具體做法是：針對不在詞表中的一段子文本，使用HMM分詞，並把HMM的分詞結果加入到原始分詞結果中。

基於CRF的分詞方法

與HMM不同，CRF是一種判別式模型，CRF通過定義條件概率P(Y∣X)來描述模型。基於CRF的分詞方法與傳統的分類模型求解很相似，即給定feature(字級別的各種信息)輸出label(詞位)。

$score(l | s) = sum_{j = 1}^m sum_{i = 1}^n lambda_j f_j(s, i, l_i, l_{i-1})$

簡單來說，分詞所使用的是Linear-CRF，它由一組特徵函數組成，包括權重λ和特徵函數f，特徵函數f的輸入是整個句子s、當前posi、前一個詞位li?1，當前詞位li。

引自參考資料#3，以CRF在詞性標註上的應用，給大家一個特徵函數的感性認識。

f1(s,i,li,li?1)=1，如果li是副詞且第i個單詞以"-ly"結尾；否則f1=0。該特徵函數實際上描述了英語中副詞「常常以-ly結尾」的特點，對應的權重λ1應該是個較大的正數。
f4(s,i,li,li?1)=1，如果li?1是介詞且li也是介詞，否則f4=0。對應的權重λ4是個較大的負數，表明英語語法中介詞一般不連續出現。

感性地說，CRF的一組特徵函數其實就對應著一組判別規則(特徵函數)，並且該判別規則有不同的重要度(權重)。在CRF的實現中，特徵函數一般為二值函數，其量綱由權重決定。在開源實現CRF++中，使用者需要規定一系列特徵模板，然後CRF++會自動生成特徵函數並訓練、收斂權重。

與HMM比，CRF存在以下優點：

CRF可以使用輸入文本的全局特徵，而HMM只能看到輸入文本在當前位置的局部特徵
CRF是判別式模型，直接對序列標註建模；HMM則引入了不必要的先驗信息

基於深度學習的端到端的分詞方法

最近，基於深度神經網路的序列標註演算法在詞性標註、命名實體識別問題上取得了優秀的進展。詞性標註、命名實體識別都屬於序列標註問題，這些端到端的方法可以遷移到分詞問題上，免去CRF的特徵模板配置問題。但與所有深度學習的方法一樣，它需要較大的訓練語料才能體現優勢。

BiLSTM-CRF(參考資料#4)的網路結構如上圖所示，輸入層是一個embedding層，經過雙向LSTM網路編碼，輸出層是一個CRF層。下圖是BiLSTM-CRF各層的物理含義，可以看見經過雙向LSTM網路輸出的實際上是當前位置對於各詞性的得分，CRF層的意義是對詞性得分加上前一位置的詞性概率轉移的約束，其好處是引入一些語法規則的先驗信息。

從數學公式的角度上看：

$S(X, y)=sum_{i=0}^{n}A_{y_i,y_{i+1}}+sum_{i=1}^{n}P_{i,y_i}$

其中，A是詞性的轉移矩陣，P是BiLSTM網路的判別得分。

$P(y|X)=frac{e^{s(X,y)}}{sum_{widetilde{y}in Y_{x}}e^{s(X,y)}}$

因此，訓練過程就是最大化正確詞性序列的條件概率P(y∣X)。

類似的工作還有LSTM-CNNs-CRF(參考資料#5)。

更多精彩內容，請關注我的個人博客。

參考資料

成慶, 宗. 統計自然語言處理[M]. 清華大學出版社, 2008.
Itenyh版-用HMM做中文分詞
Introduction to Conditional Random Fields
Lample G, Ballesteros M, Subramanian S, et al. Neural Architectures for Named Entity Recognition[J]. 2016:260-270.
Ma X, Hovy E. End-to-end sequence labeling via bi-directional lstm-cnns-crf[J]. arXiv preprint arXiv:1603.01354, 2016.