基于實際工作經驗和網絡、書籍資料查詢，記錄的學習筆記。主要關于中文分詞中HMM(隐馬爾可夫模型)、Viterbi算法及其在中文分詞中的應用。
前言
在處理題庫去重采用了關鍵詞提取+simhash的辦法。而提取關鍵詞之前，需要先進行中文分詞。一種基本方法是基于詞庫進行分詞，但顯然詞庫是不可能齊全的，這時，為了确認對于未被記入詞庫的詞（未登入詞）如别被處理，就需要有一定了解，才能準确應對意外的分詞情況。本文為作者在進行題庫去重過程中，對中文分詞的學習經驗總結，在此積累，以期未後來者參考學習、彼此交流。
本篇介紹HMM(隐馬爾可夫模型)和Viterbi(維特必)算法，主要面向對機率論不熟悉而希望對中文分詞工具有更進一步了解的同學，期待忘為讀者深入了解其他相關算法提供學習方式思路。同時，也期待專業人士能提供更進一步的意見或建議。
同時，希望數學不好的同學對此也不必有恐懼心理。因為作者也不是對此特别熟悉，會結合個人的學習過程和執行個體，盡可能簡單的介紹HMM、Viterbi，以及它們與中文分詞三者之間的關系。
正文
在正式介紹HMM之前，我們有必要先了解馬爾可夫過程和馬爾可夫鍊。
Markov process(馬爾可夫過程)
一個性質： 當一個随機過程在給定現在狀态及所有過去狀态情況下，其未來狀态的條件機率分布僅依賴于目前狀态；換句話說，在給定現在狀态時，它與過去狀态（即該過程的曆史路徑）是條件獨立的，那麼此随機過程即具有馬爾可夫性質
一個定義： 滿足馬爾可夫性質的過程稱為馬爾可夫過程
DTMC(離散馬爾可夫鍊)
一個定義： 時間和狀态都是離散的馬爾可夫過程。
一個重要特性： 已知系統目前狀态，則未來的演變不依賴于過去的演變。
一個泛化描述： 假設，目前時間是T，則T+1等于某個值的機率，僅與T相關，而與[0, T-1]中的所有值都無關（一階馬爾可夫鍊）。
P { X n + 1 = i n + 1 ∣ X 0 , X 1 , . . . , X n = i n } = P { X n + 1 ∣ X n = i n } P\{X_{n+1}=i_{n+1}\ |\ X_0,X_1,...,X_n=i_n\} = P\{X_{n+1}\ |\ X_n = i_n\} P{Xn+1=in+1 ∣ X0,X1,...,Xn=in}=P{Xn+1 ∣ Xn=in}
一個矩陣： 這個是其實是n步轉移機率矩陣，詳細講解較為複雜，可以自行百度，不影響後文了解。
P = [ P 11 P 12 … P 1 n … P 21 P 22 … P 2 n … P 31 P 32 … P 3 n … ] P\ =\ \left[ \begin{array}{ccc} P_{11} & P_{12} & … & P_{1n} & … \\ P_{21} & P_{22} & … & P_{2n} & … \\ P_{31} & P_{32} & … & P_{3n} & … \end{array} \right ] P = ⎣⎡P11P21P31P12P22P32………P1nP2nP3n………⎦⎤
如此，先記住什麼是馬爾可夫過程和DTMC，後續再了解什麼是HMM(隐馬爾可夫模型)就容易了。
HMM(隐馬爾可夫模型)
在正式介紹之前，我們先由一個句子作為執行個體。我們直接給定一個文本，按HMM給這個文本分詞。
接下來我們按照HMM的過程進行分析。
- 對于句子中的字，我們定義起包含四種狀态（隐含狀态空間S）：
- B——begin。表示該字為詞的起始字
- M——middle。表示該字為詞的中間字
- E——end。表示詞語中的結束字
- S——single。表示單字成詞
- 我們定義句子中，所有的字共同組成了一個觀測值集合（觀察狀态），即：O = { 我, 愛, 梅, 沙 }。
- 當我們看到一個字（觀察狀态）時，它是BMES中某一個的機率，組成一個初始的機率矩陣（矩陣值已經基于海量文本統計求得）。對于任何字，轉移到BMES中的機率都是一緻的，是以該矩陣是1x4的機率矩陣（π向量/初始機率矩陣），在這裡，矩陣如下：
{ "B": -0.26268660809250016, "E": -3.14e+100, "M": -3.14e+100, "S": -1.4652633398537678 } - 已經存在一個機率矩陣，是目前字分别為BMES時，下一個字為BMES的機率（4x4的狀态轉移機率矩陣，矩陣中的值已經基于海量文本統計求得），即： [ A b b A b m A b e A b s A m b A m m A m e A m s A e b A e m A e e A e s A s b A s m A s e A s s ] \left[ \begin{array}{ccc} A_{bb} & A_{bm} & A_{be} & A_{bs}\\ A_{mb} & A_{mm} & A_{me} & A_{ms}\\ A_{eb} & A_{em} & A_{ee} & A_{es}\\ A_{sb} & A_{sm} & A_{se} & A_{ss}\\ \end{array} \right ] ⎣⎢⎢⎡AbbAmbAebAsbAbmAmmAemAsmAbeAmeAeeAseAbsAmsAesAss⎦⎥⎥⎤，實際，這裡很多情況機率為0，是以，實際矩陣如下：
{ "B": { "E": -0.510825623765990, "M": -0.916290731874155 }, "E": { "B": -0.5897149736854513, "S": -0.8085250474669937 }, "M": { "E": -0.33344856811948514, "M": -1.2603623820268226 }, "S": { "B": -0.7211965654669841, "S": -0.6658631448798212 } } - 已經存在一個機率矩陣，每個字分别為BMES各個狀态時的機率（發射機率矩陣/混淆矩陣，矩陣中的值已經基于海量文本統計求得），即：{ Bij | i ∈ [0x4E00, 9FA5] , j ∈ (B, M, E, S) }，在這裡，發射矩陣如下：
{ "B": { "我": 1.4614045662995514, "愛": 1.968025153941063, "梅": 2.237194588185915, "沙": 1.983966134924789 }, "E": { "我": 2.8844153800921876e+101, "愛": 2.5467388205842573e+101, "梅": 2.5483227218706336e+101, "沙": 2.6413544826999272e+101 }, "M": { "我": 2.6778005616524882e+101, "愛": 2.2547330469174095e+101, "梅": 2.5528428570784386e+101, "沙": 2.321741847245321e+101 }, "S": { "我": 6.611019698336738, "愛": 11.146923368528606, "梅": 14.546547456418994, "沙": 13.526900849382743 } }
如此，我們得到了HMM的五元組 ( S , O , Π , A , B ) (S, O, \Pi, A, B) (S,O,Π,A,B)（兩組狀态集合和三組機率集合）：
- 隐狀态S：由馬爾科夫過程描述，是隐狀态集合
- 觀察狀态O：是顯示/直接觀測而得的狀态集合
- (隐)狀态轉移矩陣A：隐狀态之間互相轉移的機率矩陣
- 初始化機率向量 Π ( π i ) \Pi(\pi_i) Π(πi)：每個觀察狀态，初始時分别為各個隐狀态的機率集合。是一個1xN（N是隐狀态空間大小）的矩陣
- 混淆矩陣/發射機率矩陣B：每個觀察狀态轉移至各個隐狀态的機率集合（發射機率）
确定好模型各個部分，接下來就可以按步驟處理。大緻思路是
- 計算初始狀态
- 一次計算第二次、第三次、第四次的轉移機率
- 找出最大機率路徑（動态規劃）
為什麼上文中統計求得的機率結果都是負數？
這涉及到計算機中的下溢問題，對于一般運算，下溢帶來的誤差并不明顯，但在中文分詞中，字庫非常大 [0x4E00, 9FA5]，而機率總是屬于區間[0, 1]的，這時，一點點的下溢問題，都有可能導緻整個模型計算錯誤。是以，推薦使用對數處理實際應用中的高精度機率計算問題。通過簡單檢視對數函數圖像，我們即可了解為什麼存儲的機率都是負數了。但為什麼是對數而不是其他函數？ 個人認為主要因素有以下兩點，但或許未能描述清楚，歡迎同學補充：
浮點數乘除運算可以轉為對數和差運算，減少溢出精度和誤差累積：
log α M N = log α M + log α N \log_{\alpha }MN\ =\ \log_{\alpha }\!M+\log_{\alpha }\!N logαMN = logαM+logαN
log α M N = log α M − log α N \log_{\alpha }\frac{M}{N}\ =\ \log_{\alpha }\!M -\log_{\alpha }\!N logαNM = logαM−logαN
- x趨近于0時，對數是無限大的，對于無限小的機率也能表示
- 對于任意的x ∈ [0, 1]，x任何一點變化都會導緻其對數結果變化明顯
計算初始狀态
按照上述HMM五元組，結合該公式 a i ( j ) = π ( j ) b j k i , i ∈ N , j ∈ ( B , E , M , S ) , k ∈ ( 我 , 愛 , 梅 , 沙 ) a_i(j) = \pi(j)b_{jk_i}, i \in N, j \in (B, E, M, S), k \in (我, 愛, 梅, 沙) ai(j)=π(j)bjki,i∈N,j∈(B,E,M,S),k∈(我,愛,梅,沙)，計算即可得。
{
"B": {
"我":1.1851974272161176,
"愛":1.9983762718297673,
"梅":2.388164278255412,
"沙":2.5132210235744683
},
"E":{
"我":1.4167147493671037e+101,
"愛":2.388740537292971e+101,
"梅":2.854670014651611e+101,
"沙":3.004155434998415e+101
},
"M":{
"我":1.4167147493671037e+101,
"愛":2.388740537292971e+101,
"梅":2.854670014651611e+101,
"沙":3.004155434998415e+101
},
"S":{
"我":6.611019698336738,
"愛":11.146923368528606,
"梅":13.321157069582242,
"沙":14.018722376196262
}
}
計算狀态轉移機率矩陣
得到上述初始狀态後，可以結合前文所述的HMM五元組，疊代求得如下關系圖中所有弧的機率。t次疊代公式如下（這其實也可以泛化為馬爾可夫n步轉移矩陣疊代公式）。
P t + 1 ( s ) = b s o t + 1 ∑ i = 0 n a t ( s ) a s i s ∈ P_{t+1}(s)\ =\ b_{so_{t+1}}\sum_{i=0}^{n}{a_{t}(s)a_{si}}\\ s \in Pt+1(s) = bsot+1i=0∑nat(s)asis∈
将弧的機率作為權值，尋找最大權值路徑，即可求得。由于計算過程過于複雜，在這裡不列出。經過代碼測試，案例分詞結果為『我/愛梅沙』。
不是所有預測性問題都能使用HMM解決。實際上，HMM有三個重要假設（個人了解，三個假設即為滿足這三個假設的問題，都可以使用HMM解決）。
馬爾可夫假設——即上文所述一階馬爾可夫鍊，目前為某狀态的機率僅與上一次的狀态有關，而與更早的狀态無關
P { X n + 1 = i n + 1 ∣ X 0 , X 1 , . . . , X n = i n } = P { X n + 1 ∣ X n = i n } P\{X_{n+1}=i_{n+1}\ |\ X_0,X_1,...,X_n=i_n\} = P\{X_{n+1}\ |\ X_n = i_n\} P{Xn+1=in+1 ∣ X0,X1,...,Xn=in}=P{Xn+1 ∣ Xn=in}
不動性假設——狀态與時間/時序無關
P ( X i + 1 ∣ X i ) = P ( X j + 1 ∣ X j ) ， 對 于 任 意 i , j 成 立 P(X_{i+1}|X_i)\ =\ P(X_{j+1} | X_j)，對于任意i, j成立 P(Xi+1∣Xi) = P(Xj+1∣Xj)，對于任意i,j成立
輸出獨立性假設——輸出狀态僅與目前狀态有關，即目前輸入狀态得到确定的輸出狀态，這個過程不随更早的輸入、輸出或時間而被改變
P ( O 1 , . . . , O T ∣ X 1 , . . . , X T ) = Π ( O T ∣ X T ) P(O_1,...,O_T | X_1, ..., X_T) = \Pi(O_T\ |\ X_T) P(O1,...,OT∣X1,...,XT)=Π(OT ∣ XT)
Viterbi——HMM的優化實作
HMM有三個機率矩陣，對于UTF-8編碼，中文字的數量也是龐大的。這時候，随着運算（待分詞的句子長度）增加，混淆矩陣和狀态轉移機率矩陣都會指數增長，再基于動态規劃求最大機率路徑，這個過程的不論是時間複雜度還是空間複雜度都可能指數增長。這時，使用Viterbi算法就是為了解決這個問題——當滿足某些限制條件時，我們不需要求解DAG中，所有弧的機率（權值）。限制條件如下（該限制條件為個人總結，不知是否準确。歡迎同學修正或補充）：
- 求解網絡中的最長路徑
- 所有節點的選擇僅受上一層最大機率節點和目前節點輸入值影響
結合前文，關于HMM的三個假設，可以發現，Veterbi适用于求解HMM的最大機率路徑。具體過程不再這裡贅述，大體思路是初始機率計算與前文所述計算方式相同，後續所有狀态的計算，都隻取上一層計算中，最大機率節點。這是一個類似遞歸的過程，最後回溯可以得到分詞結果。可以感受到，使用Viterbi算法後的主要效果是，省去了其他無關路徑帶來的計算量（個人認為這有點像貪心，但貪心得到的不一定是最優解，而Viterbi算法結果是最優解）。
關于Viterbi算法
很多人都用隐馬爾科夫模型來回答viterbi算法，其實viterbi算法隻是解決隐馬第三個問題（求觀察序列的最可能的标注序列）的一種實作方式。這個問題可以用于viterbi算法實作，也可以用其他方式實作（如窮舉法）；而viterbi算法可以用于解決隐馬第三問題，也可以用于解決其他問題。是以千萬不要把viterbi算法和隐馬爾科夫模型等價了。
viterbi算法其實就是多步驟每步多選擇模型的最優選擇問題，其在每一步的所有選擇都儲存了前續所有步驟到目前步驟目前選擇的最小總代價（或者最大價值）以及目前代價的情況下前繼步驟的選擇。依次計算完所有步驟後，通過回溯的方法找到最優選擇路徑。符合這個模型的都可以用viterbi算法解決，隐馬模型的第三問題剛好符合這個模型，是以才采用了viterbi算法。
——引用知乎回答[4]
為什麼是Viterbi而不是拓撲排序？
個人了解是：拓撲排序解決的是單源點到多彙點的路徑選擇問題，而HMM中的網絡結構是多源的——初始顯狀态空間，此時每種情況都是一個起點，是以，拓撲排序對于HMM的計算是不适用的。但我也認為這個解釋不夠合适，歡迎各位優秀同學糾正。
此外，看到帶權、有向無環圖兩個關鍵字，很容易讓人聯想到AOE網。我們要明确，AOE網描述的是**單源點；單彙點；**帶權；有向無環圖。AOE網的關鍵路徑選擇過程在這裡是不适用的，二者不可混淆。
結巴分詞
通過上文所述，相信大家對未登入詞的解析方式有了一定概念，更多的資訊推薦直接閱讀文末參考文獻 [1] 。當然，這隻是對于未登入詞的常見處理方式。實際上，我們能擷取很龐大的詞典（ictclas提供包含3000萬詞的免費詞庫），也能基于已有資料和HMM統計一份自己的詞典。對于結巴分詞，會首先基于詞典檔案構造字首詞典；分詞時，基于字首詞典完全切分句子，再以每個詞的成詞機率為權值，構造DAG(有向無環圖)；最後，用動态規劃的辦法從後向前周遊，查找最大權值路徑。其中，未登入詞的成詞機率基于HMM模型，采用Viterbi算法計算。
關于這個基本過程，其實結巴分詞的README檔案中有描述。但對于不了解HMM的同學而言，看到『對于未登入詞，采用了基于漢字成詞能力的 HMM 模型，使用了 Viterbi 算法』這句話可能會比較懵逼。結合上文所述，再回歸到結巴分詞的README檔案中關于算法的說明及其具體代碼中，思路可能會清晰很多。
此外，結巴分詞關于DAG采用十字連結清單法（将每個詞看做一條弧，詞的起始字的位置為弧尾，結束字位置為弧頭）。在結巴分詞中，可以找到getDAG方法，嘗試列印其傳回值有助于更深刻了解這一存儲結構和後續周遊過程。
引用https://github.com/fxsjy/jieba/blob/master/README.md#算法
- 基于字首詞典實作高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖 (DAG)
- 采用了動态規劃查找最大機率路徑, 找出基于詞頻的最大切分組合
- 對于未登入詞，采用了基于漢字成詞能力的 HMM 模型，使用了 Viterbi 算法
在上文，我們提及，關于隐含狀态、隐含狀态機率矩陣已經通過統計得到。實際上，除此之外，還有很多參數都是如此。具體可以參見結巴分詞 issue#7 資料是如何生成的。需要注意的是，該issue的回答是2012年。于2013年(latest update)，作者還更新出了big版詞典。即目前資料來源比 issue #7 中作者回複的資料來源更全面。
垂直領域優化
在了解了HMM和結巴分詞的基本過程後，我們可以明白，盡管結巴分詞提供了HMM算法的實作，用于實作對未登入詞的解析，但為了在生産環境中實作更高的Precision和Recall，我們有必要擷取垂直領域的詞庫，并統計相應詞頻，并修改分詞規則。以期提高對垂直領域（尤其是僅該領域特有的文本特性，如數學、實體、計算機程式設計等）文本處理的精确度。
小結
對于HMM在分詞中的應用，個人了解為這是從機率統計的思路，簡化中文分詞問題。在學習過程中，我們不能認為是無理由或随機選擇了HMM實作對中文未登入詞的處理，這很容易導緻後續學習的思路混亂。更合理的，可能是因為中文文本的特性與HMM的三個假設恰好符合，是以，選擇了HMM。也即，是否有其他方法解決呢？也有，比如LSTM[1]。
通過了解曆史，我們可以知道，最初的自然語言處理是基于文法規則的（這也是為什麼最早的時候，我們使用翻譯工具都十分不通順，幾乎是簡單地詞到詞的映射），随着計算機性能的提升和相關技術發展，基于機率統計的系統性能更理想。但我們不能因為『實踐證明基于手工規則的分詞系統在評測中不敵基于統計學習的分詞系統』，就認為基于文法規則的系統是毫無前途的。實際上，目前有許多文獻資料都有提及，未來如果要實作更精确的自然語言處理，基于文法規則與基于機率統計的方法相結合是必然的趨勢（雖然沒有具體樣例，但是個人有印象，有系統使用文法規則對基于機率統計的分析結果做進一步糾錯的處理方式，有興趣的同學可以做進一步了解）。同時，個人建議感興趣的同學，了解基本語言發展曆史和中文分詞的發展曆程，有助于加深關于分詞系統或其它NLP系統的原理和發展趨勢，具體可以參見[2-3]。
由此前文可以了解，目前我們對于這一技術不能認為分詞工具和基于分詞工具的系統可以達到百分百正确。因而，在實際應用中，有必要基于實際業務設計測試用例并限定最低Precision、Recall、F-score。令系統完成所有測試用例，且各評分達到相應門檻值即可認為通過測試。
參考資料
- 基于LSTM網絡的序列标注中文分詞法[J]. 計算機應用研究, 2017(5).
- 鄭捷. nlp漢語自然語言處理原理與實踐[M]. 北京: 電子工業出版社, 2017.1
- 黃昌甯, 趙海. 中文分詞十年回顧[J]. 中文資訊學報, 2007, 21(3):8-19.
- https://www.zhihu.com/question/20136144
- https://github.com/fxsjy/jieba
- http://www.52nlp.cn/hmm
- https://www.cnblogs.com/zhbzz2007/p/6092313.html
![D. Ehab the Xorcist(構造+思維)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)