1 基本概念
1.1 定義、假設和應用
我們先通過一個簡單的例子，來了解隱馬爾科夫模型 HMM 。假設：
（ 1 ）小明所在城市的天氣有 { 晴天，陰天，雨天 } 三種情況，小明每天的活動有 { 宅，打球 } 兩種選項。
（ 2 ）作為小明的朋友，我們只知道他每天參與了什麼活動，而不知道他所在城市的天氣是什麼樣的。
（ 3 ）這個城市每天的天氣情況，會和前一天的天氣情況有點關係。譬如說，如果前一天是晴天，那麼後一天是晴天的機率，就大於後一天是雨天的機率。
（ 4 ）小明所在的城市，一年四季的天氣情況都差不多。
（ 5 ）小明每天會根據當天的天氣情況，決定今天進行什麼樣的活動。
（ 6 ）我們想通過小明的活動，猜測他所在城市的天氣情況。
那麼，城市天氣情況和小明的活動選擇，就構成了一個隱馬爾科夫模型 HMM ，我們下面用學術語言描述下：
（ 1 ） HMM 的基本定義： HMM 是用於描述由隱藏的狀態序列和顯性的觀測序列組合而成的雙重隨機過程。 在前面的例子中，城市天氣就是隱藏的狀態序列，這個序列是我們觀測不到的。小明的活動就是觀測序列，這個序列是我們能夠觀測到的。這兩個序列都是隨機序列。
（ 2 ） HMM 的假設一：馬爾科夫性假設。當前時刻的狀態值，僅依賴於前一時刻的狀態值，而不依賴於更早時刻的狀態值。 每天的天氣情況，會和前一天的天氣情況有點關係。
（ 3 ） HMM 的假設二：齊次性假設。狀態轉移機率矩陣與時間無關。即所有時刻共享同一個狀態轉移矩陣。 小明所在的城市，一年四季的天氣情況都差不多。
（ 4 ） HMM 的假設三：觀測獨立性假設。當前時刻的觀察值，僅依賴於當前時刻的狀態值。 小明每天會根據當天的天氣情況，決定今天進行什麼樣的活動。
（ 5 ） HMM 的應用目的：通過可觀測到的數據，預測不可觀測到的數據。 我們想通過小明的活動，猜測他所在城市的天氣情況。
注一：馬爾科夫性：隨機過程中某事件的發生只取決於它的上一事件，是「無記憶」過程。
注二： HMM 被廣泛應用於標註任務。在標註任務中，狀態值對應著標記，任務會給定觀測序列，以預測其對應的標記序列。
注三： HMM 屬於生成模型，是有向圖。
1.2 三個基本問題
在學習 HMM 的過程中，我們需要研究三個問題，它們分別是：
機率計算問題 ：給定模型參數和觀測序列，計算該觀測序列的機率。是後面兩個問題的基礎。
學習訓練問題 ：給定觀測序列，估計模型參數。
解碼預測問題 ：給定模型參數和觀測序列，求機率最大的狀態序列。
這三個問題會貫穿我們學習 HMM 的整個過程，在接下來的三個小節，我們會分別學習這三個問題。
2 機率計算問題
2.1 標記符號和參數
先約定一下 HMM 的標記符號，並通過套用上文的例子來理解：
（ 1 ）狀態值集合（一共有 N 種狀態值）：
天氣的狀態值集合為 { 晴天，陰天，雨天 } 。
（ 2 ）觀測值集合（一共有 M 種觀測值）：
小明活動的觀測值集合為 { 宅，打球 } 。
（ 3 ）狀態值序列：
每一天的城市天氣狀態值構成的序列。
（ 4 ）觀測值序列：
每一天的小明活動的觀測值構成的序列。
（ 5 ）序列狀態值、觀測值下標： idx(t) ，表示 t 時刻的狀態值或觀測值，取的是狀態值、觀測值集合中的第 idx(t) 個。
再給出 HMM 模型的三個參數： A ， B ，π。
A ：狀態轉移機率矩陣。 表征轉移機率，維度為 N*N 。
B ：觀測機率矩陣。 表徵發射機率，維度為 N*M 。
π：初始狀態機率向量 。維度為 N*1 。
λ =(A,B, π ) ，表示模型的所有參數。
同樣通過上文的例子來理解這三個參數。
狀態轉移機率矩陣 A ：
觀測機率矩陣 B ：
初始機率狀態向量π：
2.2 前向後向算法
我們通過前向後向算法，來計算特定觀測序列出現的機率。
（ 2.2 節和 2.3 節涉及大量的公式推導，沒有興趣的童鞋可以跳過不看，不影響文章其它部分的理解）
2.2.1 前向算法模型
定義
表示在模型參數已知的條件下，預測 1~t 時刻觀測值為特定序列以及 t 時刻狀態值為特定值的機率。
前向算法模型的思路是：利用 t 時刻的α值，去預測 t+1 時刻的α值。使用的是疊代的思路。
（ 1 ）模型初值：
（ 2 ）疊代公式：
（ 3 ）模型終值：
2.2.2 後向算法模型
定義
表示在模型參數和 t 時刻狀態值已知的條件下，預測 t+1 之後所有時刻觀測值為特定序列的機率。
後算法模型的思路是：利用 t+1 時刻的β值，去預測 t 時刻的β值。使用的是遞歸的思路。
（ 1 ）模型初值：人為地定義
（ 2 ）遞歸公式：
（ 3 ）模型終值：
2.2.3 前向後向算法模型公式
這個公式比李航教授書里的公式更容易理解些，《統計學習方法》書里的公式是：
這兩個公式都是正確的，這兩個公式在推導過程中獲取的以下兩個公式，在 2.3 節有不同的應用：
2.3 一些機率和期望的計算
2.3.1 兩個常用的機率公式
（ 1 ）
給定模型λ和觀測序列，求時刻 t 處於指定狀態的機率。
（ 2 ）
給定模型λ和觀測序列，求時刻 t 和 t+1 處於指定狀態的機率。
2.3.2 三個常用的期望公式
在觀測序列 O 的條件下，狀態 i 出現的期望值：
在觀測序列 O 的條件下，由狀態 i 轉移的期望值：
在觀測序列 O 的條件下，由狀態 i 轉移到狀態 j 的期望值：
3 學習訓練問題
模型參數的學習，可以根據有無標註數據，分為有監督和無監督兩類。
在 HMM 里，如果訓練數據包含觀測序列和狀態序列，即為有監督學習。如果訓練數據只包含觀測序列，即為無監督學習。
在有監督學習中，可以直接通過統計方法，求得模型的狀態轉移機率矩陣 A 、觀測機率矩陣 B 、初始狀態機率向量π。
在無監督學習中，模型使用 Baum-Welch 算法來求得模型參數。 Baum-Welch 算法是 HMM 模型中最難的部分，由於本文是「入門」文章，這裡就不展開推導了。
注一：其實 Baum-Welch 算法和 EM 算法是一樣的，只是 Baum-Welch 算法提出得比較早，當時 EM 算法還沒有被歸納出來。
4 解碼預測問題
4.1 貪心算法
貪心算法使用了條件獨立性假設，認為不同時刻出現的狀態是互相孤立的，是沒有相關性的。所以，可以分別求取序列每個時刻最有可能出現的狀態，再將各個時刻的狀態按順序組合成狀態序列，作為預測結果。
貪心算法使用的公式，是 2.3.1 節推導出的
貪心算法的優點是計算簡單。缺點是不同時刻的狀態之間，實際上是機率相關的，這種算法可能導致陷入局部最優點，無法取到全局整體序列的最優值。
實際上，業界極少用貪心算法來解碼預測 HMM 模型的狀態序列。
4.2 維特比算法
維特比 Viterbi 算法使用了動態規劃 DP 的思路，在這一節，我們不列舉公式，而是通過一個例子，來呈現維特比算法是怎麼工作的。
依舊使用前文的天氣和活動的例子，模型參數和 2.1 節一樣：
狀態轉移機率矩陣 A ：
觀測機率矩陣 B ：
初始機率狀態向量π：
現在已知小明在 3 天裡的活動序列為： [ 宅，打球，宅 ] ，求最有可能的天氣序列情況。
維特比算法預測過程：
步驟 1 ：根據模型參數π和 B ，求得第 1 天天氣的機率分布。
P(D1 ，晴天，宅 )=0.2*0.5=0.1
P(D1 ，陰天，宅 )=0.4*0.4=0.16
P(D1 ，雨天，宅 )=0.4*0.7=0.28
此時我們保存 3 個序列：
序列最後時刻為晴天的最大機率序列： [ 晴天： 0.1]
序列最後時刻為陰天的最大機率序列： [ 陰天： 0.16]
序列最後時刻為雨天的最大機率序列： [ 雨天： 0.28]
步驟 2 ：根據步驟 1 的 3 個序列，模型參數 A 和 B ，求得第 2 天天氣的機率分布。
P(D2 ，晴天，打球 )
= max(P(D1 ，晴天 )*P(D2 ，晴天 |D1 ，晴天 )* P( 打球 |D2 ，晴天 ),
P(D1 ，陰天 )*P(D2 ，晴天 |D1 ，陰天 )* P( 打球 |D2 ，晴天 ),
P(D1 ，雨天 )*P(D2 ，晴天 |D1 ，雨天 )* P( 打球 |D2 ，晴天 ))
= max(0.1*0.5*0.5, 0.16*0.3*0.5, 0.28*0.2*0.5 ) （前一時刻為雨天時，序列機率最大）
= 0.028
序列最後時刻為晴天的最大機率序列： [ 雨天，晴天： 0.028]
P(D2 ，陰天，打球 )
= max(0.1*0.2*0.6, 0.16*0.5*0.6, 0.28*0.3*0.6 ) （前一時刻為雨天時，序列機率最大）
= 0.0504
序列最後時刻為陰天的最大機率序列： [ 雨天，陰天： 0.0504]
P(D2 ，雨天，打球 )
= max(0.1*0.3*0.3, 0.16*0.2*0.3, 0.28*0.5*0.3 ) （前一時刻為雨天時，序列機率最大）
= 0.042
序列最後時刻為雨天的最大機率序列： [ 雨天，雨天： 0.042]
步驟 3 ：根據步驟 2 的 3 個序列，模型參數 A 和 B ，求得第 3 天天氣的機率分布。
P(D3 ，晴天，宅 )
=max(0.028*0.5*0.5, 0.0504*0.3*0.5 , 0.042*0.2*0.5) （前一時刻為陰天時，序列機率最大）
= 0.00756
序列最後時刻為晴天的最大機率序列： [ 雨天，陰天，晴天： 0.00756]
P(D3 ，陰天，宅 )
= max(0.028*0.2*0.4, 0.0504*0.5*0.4 , 0.042*0.3*0.4) （前一時刻為陰天時，序列機率最大）
= 0.01008
序列最後時刻為陰天的最大機率序列： [ 雨天，陰天，陰天： 0.01008]
P(D3 ，雨天，宅 )
= max(0.028*0.3*0.7, 0.0504*0.2*0.7, 0.042*0.5*0.7 ) （前一時刻為雨天時，序列機率最大）
= 0.0147
序列最後時刻為雨天的最大機率序列： [ 雨天，雨天，雨天： 0.0147]
步驟 4 ：對比步驟 3 的 3 個序列，選出其中機率最大的那個狀態序列。
[ 雨天，陰天，晴天： 0.00756] ， [ 雨天，陰天，陰天： 0.01008] ， [ 雨天，雨天，雨天： 0.0147] 中，機率最大的序列為 [ 雨天，雨天，雨天 ] ，機率值為 0.0147 。
所以最優可能的天氣序列情況為： [ 雨天，雨天，雨天 ]
最後，簡單地描述下維特比算法的思路：
（ 1 ）若狀態值集合有 N 個取值，則需維護 N 個狀態序列，以及 N 個狀態序列對應的機率。每個狀態序列存儲的是：序列最後一個時刻取值為特定狀態（共 N 個狀態）時，機率最大的狀態序列。 本節案例中，就維護晴天、陰天、雨天三個狀態序列，及其機率。
（ 2 ）自第 1 個時刻開始，根據狀態子序列和模型參數，計算和更新 N 個狀態序列及其機率值。 本節的案例中，對於當前時刻的晴天、陰天、雨天 3 個狀態值，分別拼接上一時刻的狀態序列和當前時刻的狀態。例如 D3 晴天分別拼接 D2 狀態序列得到： [ 雨天，晴天 ]+[ 晴天 ] ， [ 雨天，陰天 ]+[ 晴天 ] ， [ 雨天，雨天 ]+[ 晴天 ]3 個新序列。通過計算求得其中機率最大的序列為 [ 雨天，陰天，晴天 ] ，最後更新晴天狀態序列為 [ 雨天，陰天，晴天 ] ，丟棄另外兩個序列，並保存機率值 0.00756 。 D3 狀態為陰天和雨天的狀態序列更新流程與此相同。
（ 3 ）一直疊代到最後一個時刻，對比所有狀態序列的機率值，機率值最大的狀態序列即為最大狀態機率序列。
註： 4.2 小節的例子數據，引用自李航《統計學習方法》。
5 HMM 的局限性
馬爾科夫性（有限歷史性）：實際上在 NLP 領域的文本數據，很多詞語都是長依賴的。
齊次性：序列不同位置的狀態轉移矩陣可能會有所變化，即位置信息會影響預測結果。
觀測獨立性：觀測值和觀測值（字與字）之間是有相關性的。
單向圖：只與前序狀態有關，和後續狀態無關。在 NLP 任務中，上下文的信息都是必須的。
標記偏置 LabelBias ：若狀態 A 能夠向 N 種狀態轉移，狀態 B 能夠向 M 種狀態轉移。若 N< 在具體實現過程中，為避免多個很小的數相乘導致浮點數下溢，所以可以取對數，使相乘變為相加。 由於 HMM 的 EM 算法中存在求和操作（ Viterbi 算法只有乘積操作），所以不能簡單地使用取對數來避免浮點數下溢，採用的方式是設置一個比例係數，將機率值乘以它來放大；當每次疊代結束後，再把比例係數取消掉，繼續下一次疊代。 分詞任務是 NLP 的幾個基礎任務之一， jieba 分詞是一個應用得很廣泛的開源項目。 jieba 分詞使用了好幾個不同的分詞算法，我們在這一節對其中的 HMM 分詞代碼進行解讀。 利用 HMM 算法進行分詞，實際上就是執行一個序列標註任務。 我們看到的詞語是觀測序列，我們要預測一個狀態序列，最後通過狀態序列，來執行分詞操作。 狀態序列包括 B 、 M 、 E 、 S 四種狀態。單個字構成的詞，被標註為 S 。多個字構成的詞，詞語的第一個字被標註為 B ，最後一個字被標註為 E ，中間的若干個子被標註為 M 。 jieba 分詞通過有監督的方式，獲取模型參數 A ， B ，π。 狀態轉移機率矩陣 A 被保存在文件 prob_trans 中： 觀測機率矩陣 B 被保存在文件 prob_emit 中： 初始狀態機率向量π被保存在文件 prob_start 中： 如截圖所示，維特比解碼流程同 4.2 節的描述完全一致，關鍵的部分我已經添加了注釋。 唯一需要注意的是， HMM 的工程實踐中，大部分機率值都被取了對數，所以乘法操作在代碼里體現為加法操作。 根據維特比算法輸出的標註狀態序列，輸出分詞結果。6 工程實現細節
7 jieba 分詞源碼解讀
7.1 HMM 分詞基本概念
7.2 模型參數
7.3 維特比算法
7.4 分詞