中文分詞演算法簡介
本文原文發布在我的個人博客 >>
什麼是中文分詞
與大部分印歐語系的語言不同，中文在詞與詞之間沒有任何空格之類的顯示標誌指示詞的邊界。因此，中文分詞是很多自然語言處理系統中的基礎模塊和首要環節。
下面以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)
各指標計算公式如下:
各分詞方法的細節
正向最大匹配法(FMM)
正向最大匹配法，顧名思義，對於輸入的一段文本從左至右、以貪心的方式切分出當前位置上長度最大的詞。正向最大匹配法是基於詞典的分詞方法，其分詞原理是：單詞的顆粒度越大，所能表示的含義越確切。
負向最大匹配法(BMM)
反向最大匹配法的基本原理與正向最大匹配法類似，只是分詞順序變為從右至左。容易看出，FMM或BMM對於一些有歧義的詞處理能力一般。舉個例子：結婚的和尚未結婚的，使用FMM很可能分成結婚/的/和尚/未/結婚/的；為人民辦公益,使用BMM可能會分成為人/民辦/公益。
雖然在部分文獻和軟體實現中指出，由於中文的性質，反向最大匹配法優於正向最大匹配法。在成熟的工業界應用上幾乎不會直接使用FMM、BMM作為分詞模塊的實現方法。
基於N-gram語言模型的分詞方法
由於歧義的存在，一段文本存在多種可能的切分結果（切分路徑），FMM、BMM使用機械規則的方法選擇最優路徑，而N-gram語言模型分詞方法則是利用統計信息找出一條概率最大的路徑。
上圖為南京市長江大橋的全切分有向無環圖(DAG)。可以看到，可能的切分路徑有：
- 南京/市/長江/大橋
- 南京/市/長江大橋
- 南京市/長江/大橋
- 南京市/長江大橋
- 南京/市長/江/大橋
- 南京/市長/江大橋
- 南京市長/江/大橋
- 南京市長/江大橋
- …
假設隨機變數S為一個漢字序列，W是S上所有可能的切分路徑。對於分詞，實際上就是求解使條件概率P(W∣S)最大的切分路徑W?，即
根據貝葉斯公式，
由於P(S)為歸一化因子，P(S∣W)恆為1，因此只需要求解P(W)。
P(W)使用N-gram語言模型建模，定義如下(以Bi-gram為例)：
至此，各切分路徑的好壞程度(條件概率P(W∣S))可以求解。簡單的，可以根據DAG枚舉全路徑，暴力求解最優路徑；也可以使用動態規劃的方法求解，jieba中不帶HMM新詞發現的分詞，就是DAG + Uni-gram的語言模型 + 後向DP的方式進行的。
基於HMM的分詞方法
接下來介紹的幾種分詞方法都屬於由字構詞的分詞方法，由字構詞的分詞方法思想並不複雜，它是將分詞問題轉化為字的分類問題（序列標註問題）。從某些層面講，由字構詞的方法並不依賴於事先編製好的詞表，但仍然需要分好詞的訓練語料。
規定每個字有4個詞位：
- 詞首 B
- 詞中 M
- 詞尾 E
- 單字成詞 S
由於HMM是一個生成式模型，X為觀測序列，Y為隱序列。
熟悉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(詞位)。
簡單來說，分詞所使用的是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層的意義是對詞性得分加上前一位置的詞性概率轉移的約束，其好處是引入一些語法規則的先驗信息。
從數學公式的角度上看：
其中，A是詞性的轉移矩陣，P是BiLSTM網路的判別得分。
因此，訓練過程就是最大化正確詞性序列的條件概率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.
推薦閱讀：
