NLP硬核入門-隱馬爾科夫模型HMM

• 2019 年 10 月 31 日
• 筆記

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<<M，則預測序列更有可能選擇狀態A，因為A的轉移概率較大。

6 工程實現細節

在具體實現過程中，為避免多個很小的數相乘導致浮點數下溢，所以可以取對數，使相乘變為相加。

由於HMM的EM演算法中存在求和操作（Viterbi演算法只有乘積操作），所以不能簡單地使用取對數來避免浮點數下溢，採用的方式是設置一個比例係數，將概率值乘以它來放大；當每次迭代結束後，再把比例係數取消掉，繼續下一次迭代。

7 jieba分詞源碼解讀

分詞任務是NLP的幾個基礎任務之一，jieba分詞是一個應用得很廣泛的開源項目。jieba分詞使用了好幾個不同的分詞演算法，我們在這一節對其中的HMM分詞程式碼進行解讀。

7.1 HMM分詞基本概念

利用HMM演算法進行分詞，實際上就是執行一個序列標註任務。

我們看到的詞語是觀測序列，我們要預測一個狀態序列，最後通過狀態序列，來執行分詞操作。

狀態序列包括B、M、E、S四種狀態。單個字構成的詞，被標註為S。多個字構成的詞，詞語的第一個字被標註為B，最後一個字被標註為E，中間的若干個子被標註為M。

7.2 模型參數

jieba分詞通過有監督的方式，獲取模型參數A，B，π。

狀態轉移概率矩陣A被保存在文件prob_trans中：

觀測概率矩陣B被保存在文件prob_emit中：

初始狀態概率向量π被保存在文件prob_start中：

7.3 維特比演算法

如截圖所示，維特比解碼流程同4.2節的描述完全一致，關鍵的部分我已經添加了注釋。

唯一需要注意的是，HMM的工程實踐中，大部分概率值都被取了對數，所以乘法操作在程式碼里體現為加法操作。

7.4 分詞

根據維特比演算法輸出的標註狀態序列，輸出分詞結果。

知乎文章地址：https://zhuanlan.zhihu.com/p/87632700

由於微信公眾號文章有修改字數的限制，故本文後續的糾錯和更新將呈現在知乎的同名文章里。

參考文獻

[1] 李航 統計學習方法 清華大學出版社

[2] 隱馬爾科夫模型HMM（一/二/三/四） 劉建平Pinard https://www.cnblogs.com/pinard/

本文轉載自公眾號：數論遺珠，作者阮智昊