基於隱馬爾科夫（HMM）模型的中文分詞實踐

一、中文分詞問題

中文分詞是自然語言處理中一個最基礎的問題，就是一段話怎麼切分。比如：

今天的天氣怎麼樣

可以按如下方式分詞

今天天氣怎麼樣

這樣一個任務交給機器自動切分，很容易想到基於詞典的匹配，但是匹配會面臨如下問題：

1. 詞典需要人工不停錄入，否則沒法識別新詞。這也就是機器學習中一直強調的泛化能力；

2. 不同場景下分詞方式不一樣，比如：

南京市長是個好同志

而下面這句話就不能把「市長」分到一起了：

南京市長江大橋

今天要介紹一種基於統計的分詞方式。首先我們轉換下思維，把分詞問題做個轉換：分詞問題就是對句子中的每個字打標註，標註要麼是一個詞的開始（B），要麼是一個詞的中間位置（M），要麼是一個詞的結束位置（E），還有單個字的詞，用S表示。比如下面的句子可以這樣標註：

我S想S去S烏B魯M木M齊E

思維的轉換很重要，下面對中文分詞進行形式化描述：

設觀察集合為;狀態集合為

問題：已知輸入的觀察序列為:.

求對應的狀態序列：

可以直接進行求解

二、隱馬爾科夫假設

遍歷狀態Y的所有可能性，條件概率最大的則為對應的狀態序列。

由於P(X)都一樣，而我們只關心哪個最大，所以只需求$P(X|Y)P(Y)$即可。

下面需要引入馬爾科夫假設了：

假設1： 齊次馬爾科夫假設：狀態序列只和前一個狀態有關係，與其他狀態及觀察值無關，即：

假設2： 觀察獨立性假設。即假設任意時刻的觀察值僅與當前的狀態值有關，即：

有了以上假設就容易計算$P(X|Y)P(Y)$了

其中表示第一個狀態為的概率。一般我們會對上式取對數，因為取對數不會改變大小關係，但可以簡化計算：

這樣直接計算時間複雜度是：

這個指數級複雜度顯然太高了，所以有以下優化的演算法。

三、維特比（Viterbi）演算法

其實這個問題和剛才求條件概率最大值是同一個問題。可以採用動態規劃的方法來解決：

設就是第一列第個頂點出發的初始值。設表示到達第i列第j個頂點時能獲得的最大金幣值，表示走第列第個定點到第列第個頂點的邊能獲得的金幣值。則有如下遞推公式：

從上面的公式計算最大值，時間複雜度降為：

求得最大值後，反推即可知道每列走的是哪個頂點，也就是分詞中的標註序列。

四、分詞實踐

基本上搞明白上面的原理後動手實現就很容易了，需要說明有以下幾點：

• 訓練集。 訓練數據可以從這裡獲取，關於這個數據集的介紹可以看這裡

• 平滑處理。對於沒有在訓練集中出現的字，或者轉移概率為零的情況，可以給個無限小的數，比如-3.14e+100

我用python簡單實現了下，可以在github看到。

五、分詞效果的評測

模型訓練好了之後就需要對模型做評測了，那麼如何評測模型呢？

因為分詞方案並不是唯一的，每個人都會有自己的見解。所以有了gold方案，就是找一個測試集，然後給出相應的分詞方案作為標準答案。假設標準答案分出詞的個數是，你的模型給出結果和標準答案相同的分詞個數是，你的模型給出的其他單詞個數是，也就是分錯的個數，那麼：

準確率（Precision）：

召回率（Recall）：

F1值：

以上值當然越大越好，但是準確率和召回率會有一定製約關係，要想兩者都大，是一件比較困難的事情。當然，還有個指標:

錯誤率：

六、參考資料

1. 李航，機器學習方法，第十一章，清華大學出版社
2. 隱馬爾可夫模型及其應用（1）簡介&解碼問題 | bitJoy

3. 編碼無悔 / Intent & Focused

推薦閱讀：