4. NLP中文斷詞

英文斷詞基本上就是靠著標點符號跟空白，但中文每個詞跟詞之間沒有空白，所以中文斷詞不能用這個方法，這時我們就需要一些特別的方法幫助電腦學習如何將中文斷詞。

目前斷詞的主流方法有以下幾種:

• 基於詞典的分詞法：按照一定的策略將待匹配的字符串和一個已建立好的夠大的詞典中的詞進行匹配
• 基於統計的機器學習算法：HMM, CRF (Conditional Random Field), SVM, etc.
• 基於深度學習的算法：雙向LSTM模型

由於目前主流的中文斷詞「結巴」是基於傳統機器學習算法的斷詞演算法，因此本日課程會著重於介紹此斷詞演算法。

結巴的斷詞演算法主要為：

• 針對存在於字典的字詞：

1. 根據字典產生Trie Tree(字典樹、字首樹、前綴樹)
2. 根據Trie Tree建立給定輸入句的DAG (有向無環圖)
3. 使用動態規劃(Dynamic Programming)來找出最大機率路徑，此路徑及為基於詞頻最大的分詞結果

• 針對不存在於字典的字詞：

1. 使用隱馬可夫模型(HMM)與維特比演算法(Viterbi)來進行分詞辨識

接著會依序介紹上方所提及的方法，包含Trie Tree、DAG、馬可夫模型、隱馬可夫模型跟維特比演算法。

Trie Tree

Trie樹是基於一個字典建構的，在結巴中這個字典為 dict.txt ，內部包含兩萬多個詞，其中包含詞、詞頻、與詞性(結巴作者根據中國人民日報語料等資料訓練而得)。當數個詞語前面的字相同，就可以使用Trie樹來儲存。

下圖為{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”}的Trie Tree，可以發現有幾個特點，其一是Root不包含字符，其二是從根節點到某一節點路徑上經過的字符連結起來，為該節點對應的字符串，最後是每個單詞的公共前綴作為一個字符節點保存。

DAG

給定一個待分詞的句子，根據由字典生成的Trie樹查找來生成有向無環圖。其實就是根據字典查詢，列舉出根據字典所有可能的句子切分。在結巴中是將句子中某個詞的開始位置作為dictionary的Key，而可能的結尾位置(多個)構成的list作為dictionary的Value。

以「我愛自然語言」的DAG為例：

• 0: [0] 表示在dict.txt建立的Trie樹中以“我”為開頭的詞只有一個(我)
• 2: [2, 3] 表示在dict.txt建立的Trie樹中以“自”為開頭的詞有: a. “自“; b. “自然”
• 最後根據動態規劃，找出基於dict.txt中的詞頻的最大機率路徑得到最後斷詞結果

馬可夫模型

一種具有狀態的隨機過程，從目前狀態轉移 s 到下一個狀態 s’ 的機率由P(s’|s)來決定(在s的前提下s’發生的機率)，這個狀態之轉移機率並不會受到狀態以外的因素所影響，因此與時間無關。

• 一階馬可夫模型: 當前狀態只與前一個狀態有關 P(Xi|Xi-1)
• m階馬可夫模型: 當前狀態可能受前 m 個狀態所影響 P(Xi|Xi-1, Xi-2, …., Xi-m)

狀態轉移矩陣：當由一個狀態要轉移到下一個狀態時，會有相對應的轉移機率，而所有可能的轉移機率構成的矩陣即為狀態轉移矩陣。(對於有M個狀態的一階馬可夫模型，因為任何一個狀態都有可能是所有狀態的下一個轉移狀態，因此會有MxM個狀態的轉移矩陣)

初始機率向量(PI 向量)：初始化模型，會需要當前的狀態情況，而表示此狀態的向量即為初始機率向量。

舉例來說，假設有三種天氣狀態: Sunny, Cloudy, Rainy

以上為狀態轉移矩陣，昨天是晴天的狀況，今天是晴天的機率就是0.5，陰天的機率為0.375，雨天的機率是0.125。以下是初始機率向量，意指第一天是晴天的機率是100%

最後整理一下本例的重點：

• 狀態：Sunny, Cloudy, Rainy
• PI向量：初始化時每一個狀態的機率
• 狀態轉移矩陣：給定前一天狀態下，當前的天氣狀態機率

隱馬可夫模型

在某些情況下，我們無法直接觀測到狀態資訊(ex: 晴天、多雲、雨天)，但我們可以藉由其他可察覺的觀察狀態，例如我們可以觀察水草的狀態(ex:乾燥、濕潤、潮濕)，來推測實際狀態的機率為何。

舉例來說，有兩種天氣狀態Sunny, Rainy跟三種觀察狀態Walk, Shop, Wet

• 隱藏狀態：系統的真實狀態(Sunny, Rainy)
• 觀察狀態：在過程中「可視」的狀態
• PI向量：初始化時隱藏狀態的機率
• 狀態轉移矩陣：隱藏狀態到另外一個隱藏狀態的機率
• 發射矩陣：隱藏狀態觀察到某一個觀察狀態的機率

延續本例，若有一個人連續觀察到三天水草都是乾燥的(Dry)，則這三天的天氣機率為何？

1. Sunny, Sunny, Sunny: 0.4*0.6*0.6*0.6*0.6*0.6 = 0.031104
2. Rainy, Sunny, Sunny: 0.6*0.1*0.3*0.6*0.6*0.6 = 0.003888

維特比演算法(Viterbi)

維特比演算法實際上是使用動態規劃求解隱馬可夫模型預測，即使用動態規劃求解最大機率路徑。因此可以從t=1的時刻，開始計算在時刻t狀態i的所有路徑的最大概率，直到到達終點t=T時狀態為i的所有路徑的最大機率。

維特比演算法會在所有路徑中，找尋最大機率的路徑。像是圖中，所有路徑裡A->D->G的機率如果最大，則維特比演算法即為選取此路徑。

在結巴的斷詞中，即是使用上述的隱馬可夫模型與維特比算法來決定不在字典中的詞的斷詞結果。

• 隱藏狀態: 在斷詞中的隱藏狀態為{B:begin, M:middle, E:end, S:single}，所有的詞都有可能是這四種狀態的其中一種。(B:代表該字為詞語中的起始自; M:代表是詞語中的中間字; E:代表是詞語中的結尾字; S:代表單字成詞)。初始的狀態機率儲存於 “prob_start.py”

ex: 這是一個斷詞的舉例 → 這是(BE) 一個(BE) 斷詞的(BME) 舉例(BE)

• 狀態轉移矩陣: 因為隱藏狀態為BEMS四種，因此此狀態矩陣為4x4的二維矩陣(BEMS x BEMS)。結巴將轉移矩陣儲存於prob_trans.py
• 狀態發射矩陣: 此矩陣表示在某狀態(BEMS)下是某個特定詞的機率 P(Obersverd, Status) = P(Status) * P(Observed | Status)。結巴將此矩陣儲存於 prob_emit.py

結巴在未知詞(不在字典裡的字詞)的斷詞中，給定輸入字詞，然後再利用”prob_start.py” (初始機率)、“prob_trans.py”(狀態轉移矩陣)、與“prob_emit.py“(狀態發射矩陣)，搭配維特比算法來計算最大機率的斷詞組合。