大家好，我是半虹，這篇文章來講分詞算法
1 概述
分詞是自然語言處理領域中的基礎任務，是文本預處理的重要步驟
簡單來說，就是将文本段落分解為基本語言機關，亦可稱之為詞元 ( token \text{token} token )
按照粒度的不同，可以細分為：字、詞、子詞等
我們知道，自然語言是十分典型的非結構化資料，機器是無法直接識别出來的
通過分詞，自然語言可以轉化為有限的詞元組合，結合詞表就可以将其表示為結構化的資料
這樣機器才可以接收自然語言為輸入，才有後續的各種模型的處理
對于分詞的研究目前已經十分地成熟，按照類型的不同可以細分為：詞典比對、統計模型、深度學習等
雖然這些方法都可以達到很好的效果，但是仍然有一些難點要考慮：
-
分詞粒度：分詞沒有唯一的标準，不同場景對分詞粒度的要求也不同
例如蘋果手機，既可以将其切分為蘋果和手機兩個詞，也可以将其作為一個詞
-
歧義切分：有些時候不同的切分會導緻不同的含義，而且有可能都是合理的
例如這文章我寫不好，既可以是這文章 / 我寫不好，也可以是這文章 / 我寫 / 不好
-
未登入詞：在這資訊爆炸的時代，網際網路上很經常會出現一些新的詞
例如不明覺厲，怎麼才能識别出這些新興詞語也是個難點
下面我們将會從不同的類型來講一些目前常用的分詞算法
下篇文章才會從不同的粒度去将另外一些常用的分詞算法（由于篇幅原因，不得不分開兩篇文章
2 按類型劃分
分詞算法按照類型可以分為以下三類：
- 基于詞典比對的分詞算法，例如：最大比對算法、最短路徑算法
- 基于統計模型的分詞算法，例如： N-gram model \text{N-gram model} N-gram model、 HMM \text{HMM} HMM、 CRF \text{CRF} CRF
- 基于深度學習的分詞算法，例如： LSTM + CRF \text{LSTM + CRF} LSTM + CRF
2.1 基于詞典比對
基于詞典比對的分詞算法，其目标為：根據輸入的文本和給定的詞典，傳回對文本分詞後的結果
所謂詞典實際上就是常用詞元的集合，算法通過将輸入的文本與詞典來比對進而将其切分為詞元
此類方法必須要事先準備好一個詞典，至于詞典怎麼來和詞典怎麼用，正是需要考慮的關鍵問題
先說詞典怎麼來，這對分詞算法的最終效果影響很大，因為對輸入文本切分得到的詞元必定是在詞典中的
但是詞典怎麼來并不是此類方法的研究重點，較常見的做法是用簡單的工具從大規模訓練語料中提取得到
再說詞典怎麼用，基于詞典比對的分詞算法，顧名思義，就是用特定的規則，将輸入文本與詞典進行比對
進而将輸入文本切分為詞典當中的詞元達到分詞的目标，目前經過長時間的研究已有很多成熟的比對方法
基于其基本設計，這類方法有直覺的優缺點：
-
從一方面說，可以很友善通過增删詞典内容來調整分詞結果
另一方面說，太過于依賴詞典導緻其對未登陸詞的處理欠佳
- 如果詞典中的詞元有公共子串，可能會出現歧義切分的問題
下面會具體介紹，各種基于詞典比對的算法
2.1.1 最大比對算法
該算法的核心思想如下：對于輸入文本，從左端或右端開始，以貪心的思想，比對詞典中可比對的最長詞元
- 若從文本左端開始進行比對，則稱為正向最大比對算法
- 若從文本右端開始進行比對，則稱為逆向最大比對算法
- 若同時從兩端開始進行比對，則稱為雙向最大比對算法
大家有沒有想過為什麼比對方式是最大比對，而非最小比對呢
這是因為一般來說越長的詞語所表達的語義是越明确且豐富的
正向最大比對算法的步驟如下：
- 給定一段輸入文本，找到以文本左端第一個字為開頭的且存在于詞典中的最長比對文本
- 将該文本切分出來，并将剩餘文本作為新的輸入文本，重複上述步驟，直到輸入文本被全部切分
逆向最大比對算法的步驟如下：
- 給定一段輸入文本，找到以文本右端第一個字為結尾的且存在于詞典中的最長比對文本
- 将該文本切分出來，并将剩餘文本作為新的輸入文本，重複上述步驟，直到輸入文本被全部切分
那麼怎麼找到最長比對文本呢？最簡單的方法就是純暴力搜尋，下面通過一個例子進行說明
假設輸入文本如下：南京市長江大橋
假設給定詞典如下：南、京、市、長、江、大、橋、南京、市長、長江、大橋、南京市、江大橋（人名）
正向比對算法如下：
-
未比對文本為 南京市長江大橋 是以要找以南字開頭的最長比對詞元
第一步，判斷 南京市長江大橋 是否存在于詞典，顯然不在
第二步，判斷 南京市長江大 是否存在于詞典，顯然不在
第三步，判斷 南京市長江 是否存在于詞典，顯然不在
第四步，判斷 南京市長 是否存在于詞典，顯然不在
第五步，判斷 南京市 是否存在于詞典，此時符合，是以将該文段切分作為詞元
-
未比對文本為 長江大橋 是以要找以長字開頭的最長比對詞元
第一步，判斷 長江大橋 是否存在于詞典，顯然不在
第二步，判斷 長江大 是否存在于詞典，顯然不在
第三步，判斷 長江 是否存在于詞典，此時符合，是以将該文段切分作為詞元
-
未比對文本為 大橋 是以要找以大字開頭的最長比對詞元
第一步，判斷 大橋 是否存在于詞典，此時符合，是以将該文段切分作為詞元
- 故分詞結果為 南京市 / 長江 / 大橋
逆向比對算法如下：
-
未比對文本為 南京市長江大橋 是以要找以橋字結尾的最長比對詞元
第一步，判斷 南京市長江大橋 是否存在于詞典，顯然不在
第二步，判斷 京市長江大橋 是否存在于詞典，顯然不在
第三步，判斷 市長江大橋 是否存在于詞典，顯然不在
第四步，判斷 長江大橋 是否存在于詞典，顯然不在
第五步，判斷 江大橋 是否存在于詞典，此時符合，是以将該文段切分作為詞元
-
未比對文本為 南京市長 是以要找以長字結尾的最長比對詞元
第一步，判斷 南京市長 是否存在于詞典，顯然不在
第二步，判斷 京市長 是否存在于詞典，顯然不在
第三步，判斷 市長 是否存在于詞典，此時符合，是以将該文段切分作為詞元
-
未比對文本為 南京 是以要找以京字結尾的最長比對詞元
第一步，判斷 南京 是否存在于詞典，此時符合，是以将該文段切分作為詞元
- 故分詞結果為 南京 / 市長 / 江大橋
但純暴力搜尋時間效率比較差，可以利用字典樹對其進行優化，主要的思路如下：
-
将詞典構造成一棵字典樹，所謂字典樹就是一種資料結構，能減少存儲空間、加快查找速度
字典樹的根節點不包含任何資訊，其餘節點是詞元的公共字首
從根節點到其餘節點的路徑表示由路徑上的字連接配接而成的詞元
- 當進行比對時，本質上是查找字典樹中的一條路徑，是以使用普通的樹節點查找算法就可以
如果用上面的例子來說明，正向比對算法的字典樹和比對過程如下：
-
未比對文本為南京市長江大橋，是以要找以南字開頭的最長比對詞元
第一步，查找最開始根節點的子節點，找到南節點，此時比對南
第二步，查找上一步南節點的子節點，找到京節點，此時比對南京
第三步，查找上一步京節點的子節點，找到市節點，此時比對南京市
第四步，查找上一步市節點的子節點，沒有找得到，是以将上一步的文段切分作為詞元
-
未比對文本為 長江大橋，是以要找以長字開頭的最長比對詞元
第一步，查找最開始根節點的子節點，找到長節點，此時比對長
第二步，查找上一步長節點的子節點，找到江節點，此時比對長江
第三步，查找上一步江節點的子節點，沒有找得到，是以将上一步的文段切分作為詞元
-
未比對文本為 大橋，是以要找以大字開頭的最長比對詞元
第一步，查找最開始根節點的子節點，找到大節點，此時比對大
第二步，查找上一步大節點的子節點，找到橋節點，此時比對大橋
第三步，查找上一步橋節點的子節點，沒有找得到，是以将上一步的文段切分作為詞元
- 故分詞結果為 南京市 / 長江 / 大橋
還是用上面的例子來說明，逆向比對算法的字典樹和比對過程如下：
-
未比對文本為南京市長江大橋，是以要找以橋字結尾的最長比對詞元
第一步，查找最開始根節點的子節點，找到橋節點，此時比對橋
第二步，查找上一步橋節點的子節點，找到大節點，此時比對大橋
第三步，查找上一步大節點的子節點，找到江節點，此時比對江大橋
第四步，查找上一步江節點的子節點，沒有找得到，是以将上一步的文段切分作為詞元
-
未比對文本為南京市長 ，是以要找以長字結尾的最長比對詞元
第一步，查找最開始根節點的子節點，找到長節點，此時比對長
第二步，查找上一步長節點的子節點，找到市節點，此時比對市長
第三步，查找上一步市節點的子節點，沒有找得到，是以将上一步的文段切分作為詞元
-
未比對文本為南京 ，是以要找以京字結尾的最長比對詞元
第一步，查找最開始根節點的子節點，找到京節點，此時比對京
第二步，查找上一步京節點的子節點，找到南節點，此時比對南京
第三步，查找上一步南節點的子節點，沒有找得到，是以将上一步的文段切分作為詞元
- 故分詞結果為 南京 / 市長 / 江大橋
無論使用純暴力搜尋還是字典樹，我們可以發現上述兩種方法得到的分詞結果是不同的
- 正向最大比對：南京市 / 長江 / 大橋
- 逆向最大比對：南京 / 市長 / 江大橋
雙向最大比對算法會綜合考慮正向和逆向的分詞結果，進而決定最終分詞，其規則如下：
- 如果正向和逆向分詞最終的詞元數不同，那麼選擇詞元數較少的那個結果
- 如果正向和逆向分詞最終的詞元數相同，那麼選擇單字詞較少的那個結果（若一樣，則随便）
2.1.2 最短路徑算法
基于詞典比對的另一種算法是最短路徑分詞，該算法的核心思想如下：
- 首先根據詞典将輸入文本中的所有詞元識别出來構成有向無環圖，即詞圖
- 找到從起點到終點的最短路徑作為最佳組合方式，即為分詞結果
具體操作如下：
- 假設給定文本 S = c 1 c 2 . . . c n S = c_1c_2...c_n S=c1c2...cn，其中 c i c_i ci 為單個漢字， n n n 為文本長度
- 建立 n + 1 n + 1 n+1 個節點 V 0 , V 1 , . . . V n V_0,\ V_1,\ ...\ V_n V0, V1, ... Vn，将這些節點作為詞圖中的節點
- 相鄰節點 V i − 1 V_{i-1} Vi−1 和 V i V_{i} Vi ( 1 ≤ i ≤ n ) (1 \le i \le n) (1≤i≤n) 之間建立有向邊 V i − 1 → V i V_{i-1} \rightarrow V_{i} Vi−1→Vi，此時對應的詞元就是 c i c_i ci
- 若 w = c i . . . c j w = c_i...c_j w=ci...cj ( 0 < i < j ≤ n ) (0 \lt i \lt j \le n) (0<i<j≤n) 存在于詞典，那麼節點 V i − 1 V_{i-1} Vi−1 和 V j V_{j} Vj 之間建立有向邊 V i − 1 → V j V_{i-1} \rightarrow V_{j} Vi−1→Vj
- 最後，使用 Dijkstra \text{Dijkstra} Dijkstra 算法尋找以 V 0 V_0 V0 為起點、以 V n V_n Vn 為終點的最短路徑即為分詞結果
一個例子如下：
當然，尋找圖最短路徑是很常見的問題，除了經典的 Dijkstra \text{Dijkstra} Dijkstra 算法 ，也可以用其他合适的算法
另外，根據上述的設定，詞圖中每條邊的權重值都是 1 1 1，也可以用詞頻等統計資訊給邊賦予權重
2.2 基于統計模型
基于統計模型的分詞算法，其目标為：根據輸入的文本和統計資訊，對文本進行分詞得到詞元
通常認為在一定上下文中，相鄰的文字同時出現的頻率或機率越大，就越有可能可以構成詞元
這種資訊被稱為字的共現，能展現文字組合關系的緊密程度和水準，屬于統計資訊的其中一種
該算法通過建立統計模型從大量訓練語料擷取詞元的各種統計資訊并将這些資訊用于分詞預測
下面會詳細介紹各種基于統計模型的分詞算法
2.2.1 N-gram model
在上節提到，我們可以給詞圖中的邊賦予權重，權重資訊可以通過語言機率統計得到
該模型認為，給定輸入文本，其中某個詞出現的機率由之前出現的詞所決定，形式化表達如下：
假設給定輸入文本 S = c 1 c 2 . . . c n S = c_1c_2...c_n S=c1c2...cn，其中 c i c_i ci 為單個詞元， n n n 為文本長度
該文本的出現機率：
P ( S ) = P ( c 1 , c 2 , . . . , c n ) P(S) = P(c_1,\ c_2,\ ...,\ c_n) P(S)=P(c1, c2, ..., cn)
根據條件機率公式：
P ( S ) = P ( c 1 ) ⋅ P ( c 2 ∣ c 1 ) ⋅ P ( c 3 ∣ c 1 , c 2 ) ⋅ ⋯ ⋅ P ( c n ∣ c 1 , c 2 , . . . , c n − 1 ) P(S) = P(c_1) \cdot P(c_2|c_1) \cdot P(c_3|c_1, c_2) \cdot \cdots \cdot P(c_n|c_1, c_2, ..., c_{n-1}) P(S)=P(c1)⋅P(c2∣c1)⋅P(c3∣c1,c2)⋅⋯⋅P(cn∣c1,c2,...,cn−1)
可見，第 n n n 個詞 c n c_n cn 出現的機率取決于前 n − 1 n - 1 n−1 個詞 c 1 , c 2 , . . . , c n − 1 c_1,\ c_2,\ ...,\ c_{n-1} c1, c2, ..., cn−1
然而這種方式的計算複雜度太高，是以需要引入馬爾可夫假設近似上式計算
馬爾科夫假設認為：某個詞出現的機率隻取決于之前有限個詞
假如某個詞出現的機率隻取決于前面一個詞，那麼該模型稱為二進制模型，即 2 -gram 2\text{-gram} 2-gram 語言模型
上述的計算公式可改寫為：
P ( S ) = P ( c 1 ) ⋅ P ( c 2 ∣ c 1 ) ⋅ P ( c 3 ∣ c 2 ) ⋅ ⋯ ⋅ P ( c n ∣ c n − 1 ) P(S) = P(c_1) \cdot P(c_2|c_1) \cdot P(c_3|c_2) \cdot \cdots \cdot P(c_n|c_{n-1}) P(S)=P(c1)⋅P(c2∣c1)⋅P(c3∣c2)⋅⋯⋅P(cn∣cn−1)
假如某個詞出現的機率隻取決于前面兩個詞，那麼該模型稱為三元模型，即 3 -gram 3\text{-gram} 3-gram 語言模型
上述的計算公式可改寫為：
P ( S ) = P ( c 1 ) ⋅ P ( c 2 ∣ c 1 ) ⋅ P ( c 3 ∣ c 1 , c 2 ) ⋅ ⋯ ⋅ P ( c n ∣ c n − 2 , c n − 1 ) P(S) = P(c_1) \cdot P(c_2|c_1) \cdot P(c_3|c_1, c_2) \cdot \cdots \cdot P(c_n|c_{n-2}, c_{n-1}) P(S)=P(c1)⋅P(c2∣c1)⋅P(c3∣c1,c2)⋅⋯⋅P(cn∣cn−2,cn−1)
以此類推，這些模型被稱為： n -gram model n\text{-gram model} n-gram model，可用于模組化在上下文語境中詞元出現的機率
我們可以用這些統計機率給詞圖的邊賦予權重，示意圖如下：
權重詞圖中存在許多從起點到終點的路徑，例如：
- P ( 南京市長江大橋 ) = P ( 南 ∣ S ) ⋅ P ( 京 ∣ 南 ) ⋅ P ( 市 ∣ 京 ) ⋅ P ( 長 ∣ 市 ) ⋅ P ( 江 ∣ 長 ) ⋅ P ( 大 ∣ 江 ) ⋅ P ( 橋 ∣ 大 ) P(南京市長江大橋) = P(南|S) \cdot P(京|南) \cdot P(市|京) \cdot P(長|市) \cdot P(江|長) \cdot P(大|江) \cdot P(橋|大) P(南京市長江大橋)=P(南∣S)⋅P(京∣南)⋅P(市∣京)⋅P(長∣市)⋅P(江∣長)⋅P(大∣江)⋅P(橋∣大)
- P ( 南京市長江大橋 ) = P ( 南京市 ∣ S ) ⋅ P ( 長江 ∣ 南京市 ) ⋅ P ( 大橋 ∣ 長江 ) P(南京市長江大橋) = P(南京市|S) \cdot P(長江|南京市) \cdot P(大橋|長江) P(南京市長江大橋)=P(南京市∣S)⋅P(長江∣南京市)⋅P(大橋∣長江)
- …
找出其中使輸入文本出現機率最大的路徑，即為最佳分詞組合
**那麼上述的這些條件機率需要怎麼計算呢？**這裡會以條件機率 P ( c i ∣ c i − 1 ) P(c_{i}|c_{i-1}) P(ci∣ci−1) 為例進行說明
首先條件機率等于聯合機率除以邊緣機率：
P ( c i ∣ c i − 1 ) = P ( c i , c i − 1 ) P ( c i − 1 ) P(c_{i}|c_{i-1}) = \frac{P(c_{i},c_{i-1})}{P(c_{i-1})} P(ci∣ci−1)=P(ci−1)P(ci,ci−1)
聯合機率隻需統計 c i − 1 , c 1 c_{i-1},c_{1} ci−1,c1 在訓練語料中前後相鄰出現的頻率即可，具體是用出現次數除以語料大小
P ( c i , c i − 1 ) = # ( c i , c i − 1 ) # P(c_{i},c_{i-1}) = \frac{\#(c_{i},c_{i-1})}{\#} P(ci,ci−1)=##(ci,ci−1)
邊緣機率則是統計 c i − 1 c_{i-1} ci−1 在訓練語料中自己單獨出現的頻率即可，仍然是用出現次數除以語料大小
P ( c i − 1 ) = # ( c i − 1 ) # P(c_{i-1}) = \frac{\#(c_{i-1})}{\#} P(ci−1)=##(ci−1)
最後化簡可以得到 ：
P ( c i ∣ c i − 1 ) = # ( c i , c i − 1 ) # ( c i − 1 ) P(c_{i}|c_{i-1}) = \frac{\#(c_{i},c_{i-1})}{\#(c_{i-1})} P(ci∣ci−1)=#(ci−1)#(ci,ci−1)
2.2.2 HMM
HMM \text{HMM} HMM 全稱為 H idden M arkov M odel \textbf{H}\text{idden}\ \textbf{M}\text{arkov}\ \textbf{M}\text{odel} Hidden Markov Model，翻譯為：隐馬爾可夫模型
隐馬爾可夫模型是目前應用廣泛的分詞模型之一，它将分詞問題看作是序列标注任務
所謂的序列标注就是說給定任意的一段輸入序列，要求模型傳回該序列中每個元素的狀态标簽
文本序列分詞所定義的狀态标簽總共有以下四種：
-
B
Begin
-
M
Middle
-
E
End
-
S
Single
根據以上的描述，隻要能推理出文本序列的标簽，就能對該文本進行分詞
下面是一個例子：
隐馬爾可夫模型用于文本序列分詞時包含兩個關鍵的序列：
- 文本序列：作為模型的輸入，即人們顯式看到的句子，又稱為觀測序列
- 狀态序列：作為模型的輸出，即人們不能看到的因素，又稱為隐藏序列
上述隐藏序列又稱為馬爾可夫鍊，即目前狀态的機率分布隻由上一狀态決定（一階）
隐馬爾可夫模型認為觀測序列是由隐藏序列對應生成的，對應的機率圖如下：
由于隐藏序列是人們不可觀察的，是以要通過觀測序列來推理得到隐藏序列
若從數學上了解，假設觀測序列為 X X X，隐藏序列為 Y Y Y，隐馬爾可夫模型實際上是一個生成式模型
因為生成式模型會認為輸出 Y Y Y 按照一定的規律生成輸入 X X X，模型對聯合機率 P ( X , Y ) P(X,\ Y) P(X, Y) 進行模組化
在解決此類問題時，隐馬爾可夫模型會有兩個重要的假設：
- 齊次馬爾可夫假設：隐藏的馬爾可夫鍊在任一時刻的狀态隻與上一時刻的狀态有關
- 觀察值獨立性假設：任一時刻的觀測隻與目前時刻的狀态有關
最後來講該模型的訓練和預測過程，會有三個核心的矩陣，這些矩陣實際上就是隐馬爾可夫模型的參數
- 初始機率矩陣：各個狀态出現在句子開頭的機率
- 轉移機率矩陣：一個狀态出現在另一個狀态之後的機率
- 發射機率矩陣：某個狀态下出現某字的機率
訓練的過程就是根據給定的觀測序列和隐藏序列對，通過統計來求解這三個矩陣
預測的過程就是根據給定的觀測序列，應用這三個矩陣得到機率最大的隐藏序列
下面用一個例子來講解如何求解和應用這三個矩陣，現假設給定的訓練語料如下：
首先計算初始機率矩陣，先統計各個狀态出現在句子開頭的次數，再轉化成機率矩陣就可以
然後計算轉移機率矩陣，先統計一個狀态出現在另一個狀态之後的次數，再轉化成機率矩陣就可以
最後計算發射機率矩陣，先統計某個狀态下出現某字的次數，再轉化成機率矩陣就可以
至此我們已經得到三個矩陣，接下來就是用這些矩陣對新輸入句子中的每個文字預測其狀态标簽
假設現在給定一個輸入句子，例如：我今天去彈吉他，顯然句子中的每個文字都可能有四種狀态
實際上我們需要計算所有可能的狀态組合，并從中選擇出機率最大的即為預測結果，示意圖如下：
然而這樣的純暴力搜尋方法的時間效率是非常低下的，為此我們可以使用維特比算法來進行優化
維特比算法可以了解成是動态規劃算法、或貪心算法、或剪枝算法都可以
下面我們從剪枝的角度來講維特比算法是怎麼運作的，其算法的步驟如下：
- 當 “我” 的狀态為
B
時，到達此節點的路徑有一條，保留
這一條路徑是：
O
B
- 當 “我” 的狀态為
M
時，到達此節點的路徑有一條，保留
這一條路徑是：
O
M
- 當 “我” 的狀态為
E
時，到達此節點的路徑有一條，保留
這一條路徑是：
O
E
- 當 “我” 的狀态為
S
時，到達此節點的路徑有一條，保留
這一條路徑是：
O
S
- 當 “今” 的狀态為
B
時，達到此節點的路徑有四條，保留一條最優路徑，其餘路徑不再考慮 (剪枝)
這四條路徑是：
O
B
B
O
M
B
O
E
B
O
S
B
O
S
B
- 當 “今” 的狀态為
M
時，達到此節點的路徑有四條，保留一條最優路徑，其餘路徑不再考慮 (剪枝)
這四條路徑是：
O
B
M
O
M
M
O
E
M
O
S
M
O
B
M
- 當 “今” 的狀态為
E
時，達到此節點的路徑有四條，保留一條最優路徑，其餘路徑不再考慮 (剪枝)
這四條路徑是：
O
B
E
O
M
E
O
E
E
O
S
E
O
B
E
- 當 “今” 的狀态為
S
時，達到此節點的路徑有四條，保留一條最優路徑，其餘路徑不再考慮 (剪枝)
這四條路徑是：
O
B
S
O
M
S
O
E
S
O
S
S
O
S
S
- 當 “天” 的狀态為
B
時，達到此節點的路徑有四條，保留一條最優路徑，其餘路徑不再考慮 (剪枝)
這四條路徑是：
O
S
B
B
O
B
M
B
O
B
E
B
O
S
S
B
O
B
E
B
- 當 “天” 的狀态為
M
時，達到此節點的路徑有四條，保留一條最優路徑，其餘路徑不再考慮 (剪枝)
這四條路徑是：
O
S
B
M
O
B
M
M
O
B
E
M
O
S
S
M
O
B
M
M
- …
2.2.3 CRF
CRF \text{CRF} CRF 全稱為 C onditional R andom F ield \textbf{C}\text{onditional}\ \textbf{R}\text{andom}\ \textbf{F}\text{ield} Conditional Random Field，翻譯為：條件随機場模型
條件随機場模型将分詞問題看作是序列标注任務，實際上該模型可以由隐馬爾可夫模型引申得到
下面從數學角度入手，橫向對比隐馬爾可夫模型、最大熵馬爾可夫模型、條件随機場模型的異同
首先以數學角度重新來回顧一下隐馬爾可夫模型，該模型的機率圖如下：
為了簡化運算，模型有以下假設：
- 齊次馬爾可夫假設： P ( y t ∣ y 1 : t − 1 , x 1 : t − 1 ) = P ( y t ∣ y t − 1 ) P(y_{t}|y_{1:t-1},\ x_{1:t-1}) = P(y_{t}|y_{t-1}) P(yt∣y1:t−1, x1:t−1)=P(yt∣yt−1)
- 觀察值獨立性假設： P ( x t ∣ y 1 : t , x 1 : t − 1 ) = P ( x t ∣ y t ) P(x_{t}|y_{1:t\ \ \ },\ x_{1:t-1}) = P(x_{t}|y_{t}) P(xt∣y1:t , x1:t−1)=P(xt∣yt)
模型的參數包括：初始機率分布 π \pi π、轉移機率矩陣 A A A、發射機率矩陣 B B B，可将其表示為 λ = ( π , A , B ) \lambda = (\pi,\ A,\ B) λ=(π, A, B)
模型為生成模型，其模組化對象定義為聯合機率分布
P ( X , Y ∣ λ ) = ∏ t = 1 T P ( x t , y t ∣ λ ) = ∏ t = 1 T P ( y t ∣ y t − 1 , λ ) ⋅ P ( x t ∣ y t , λ ) P(X,\ Y|\lambda) = \prod_{t=1}^{T} P(x_t,\ y_t|\lambda) = \prod_{t=1}^{T} P(y_t|y_{t-1}, \lambda) \cdot P(x_t|y_t, \lambda) P(X, Y∣λ)=t=1∏TP(xt, yt∣λ)=t=1∏TP(yt∣yt−1,λ)⋅P(xt∣yt,λ)
式子的前半部分 P ( y t ∣ y t − 1 , λ ) P(y_t|y_{t-1}, \lambda) P(yt∣yt−1,λ) 對應 轉移機率矩陣，初始機率分布可以看作是轉移機率矩陣的初始狀态
式子的後半部分 P ( x t ∣ y t , λ ) P(x_t|y_t\ \ \ , \lambda) P(xt∣yt ,λ) 對應 發射機率矩陣
實際上，該模型的假設并不十分合理，很大程度上是為了降低計算複雜度而妥協的
以觀察值獨立性假設為例，每個觀察值應該與整個序列有關，而不是僅與目前時刻的隐藏狀态有關
最大熵馬爾可夫模型打破了觀察值獨立性假設，模型的機率圖如下：
上半部分表示整個觀測序列對每個隐藏狀态的影響，下半部分表示目前觀測對目前隐藏狀态的影響
通常來說隻畫上半部分或隻畫下半部分都是可以的，這裡是為了對比友善才将二者同時畫出
與隐馬爾可夫模型最大的差別在于箭頭方向的改變，該模型的箭頭方向由觀測指向隐藏狀态
這說明模型更關心的是，在給定觀測資料的情況下，其隐藏狀态的取值
模型為判别模型，其模組化對象定義為條件機率分布
P ( Y ∣ X , λ ) = ∏ t = 1 T P ( y t ∣ y t − 1 , x 1 : T , λ ) P(Y|X,\ \lambda) = \prod_{t=1}^{T} P(y_{t}|y_{t-1},\ x_{1:T},\ \lambda) P(Y∣X, λ)=t=1∏TP(yt∣yt−1, x1:T, λ)
對序列标注任務，該模組化方式實際上是更有優勢的，因為模型隻需關心隐藏狀态就可以
雖然最大熵馬爾可夫模型打破了觀察值獨立性假設，但同時又帶來了标注偏差問題
所謂标記偏差問題，簡單來說，就是在狀态轉移時，若條件轉移機率分布的熵越小，則越不關心觀測值
極端的例子就是在上圖虛線框，若 y t − 1 y_{t-1} yt−1 轉移到 y t y_{t} yt 時隻有一條轉移路徑，則此時的觀測值完全不起作用
根本的原因在于：上圖虛線框中的局部有向圖要求滿足機率分布的性質，是以必須對其進行局部歸一化
條件随機場模型解決了标記偏差問題，并間接了打破齊次馬爾可夫假設，模型的機率圖如下：
對比最大熵馬爾可夫模型最大的改變在于隐藏狀态從有向圖變成無向圖，而無向圖是天然的全局歸一化
我們假設 X X X 和 Y Y Y 有相同的結構分布，此時條件随機場稱為線性随機場
模型還是判别模型，模組化對象還是條件機率分布
P ( y ∣ x ) = 1 Z ( x ) ∑ t = 1 T exp [ ∑ k = 1 K λ k f k ( y t − 1 , y t , x ) + ∑ l = 1 L μ l s l ( y t , x ) ] P(y|x) = \frac{1}{Z(x)} \sum_{t=1}^{T} \exp{[ \sum_{k=1}^{K} \lambda_k f_k(y_{t-1}, y_{t}, x) + \sum_{l=1}^{L} \mu_l s_l( y_{t}, x) ]} P(y∣x)=Z(x)1t=1∑Texp[k=1∑Kλkfk(yt−1,yt,x)+l=1∑Lμlsl(yt,x)]
其中， Z ( x ) Z(x) Z(x) 是規範化因子 ，表示對 y y y 所有可能的取值求和
另外，式子中最核心的部分是兩個特征函數
-
f k f_k fk：定義在邊上的特征函數，又稱為轉移特征函數， K K K 代表定義在該邊上的特征函數的數量
這類函數隻和上一節點、目前節點和輸入有關， λ k \lambda_k λk 表示函數對應的權重
-
s l s_l sl：定義在點上的特征函數，又稱為狀态特征函數， L L L 代表定義在該點上的特征函數的數量
這類函數隻和目前節點和輸入有關， μ l \mu_l μl 表示函數對應的權重
特征函數的取值隻能是零或一，分别表示不滿足或滿足特征條件
每一個特征函數定義一個規則，對應權重定義這個規則的可信度，所有規則和可信度構成了條件機率分布
上述的參數需要通過訓練語料來統計得到，之後便可利用該模型對新輸入的句子進行标注和分詞
最後将特征函數和可信度的分數疊加起來，選擇使得整個句子得分最高的路徑即為最佳分詞組合
最後來總結一下
HMM
和
CRF
的差別：
-
HMM
CRF
-
HMM
CRF
2.3 基于深度學習
基于深度學習的分詞算法，還是将分詞問題看作是序列标注任務，然後使用端到端的模型來進行訓練
而在自然語言處理領域中，經常用循環神經網絡來模組化文本序列，因為它能夠很好地捕捉上下文資訊
長短期記憶網絡是循環神經網絡的變種，在一定程度上能緩解循環神經網絡在訓練時出現的梯度問題
在此基礎上，模型一般會采用雙向結構，這可以進一步增強模型的編碼能力，進而提升分詞預測效果
目前用于分詞的深度模型通常會先用雙向長短期記憶網絡編碼序列，然後接一個線性層用于标簽預測
示意圖如下：
我們可以線上性層後再接一個條件随機場，來學習标簽間的狀态轉移，以避免一些不合理的标簽組合
示意圖如下：
好啦，本文到此結束，感謝您的閱讀！
如果你覺得這篇文章有需要修改完善的地方，歡迎在評論區留下你寶貴的意見或者建議
如果你覺得這篇文章還不錯的話，歡迎點贊、收藏、關注，你的支援是對我最大的鼓勵 (/ω＼)