《機器學習實戰》學習總結（十一）——隱馬爾可夫模型（HMM）

04-28

摘要

1.概率圖模型

2.隱馬爾可夫模型

3.隱馬爾可夫問題的解法概述

註：這裡學習的演算法內容已經不完全屬於《機器學習實戰》中講述的知識了，但為了文章名稱的統一性，我還是取了這個名字。

概率圖模型

概率圖模型，顧名思義就是用圖的形式表達變數相關關係的概率模型。它以圖為表現形式，最常見的就是用一個節點表示一個或一組隨機變數，用節點之間的邊表示變數間的關係。

概率圖模型主要有兩種形式：

1.有向圖模型，如下圖所示：

節點與節點之間是用有向的邊聯繫起來的，它代表了一種因果關係， $P_1$ 表示從A變到B的概率為 $P_1$ .

2.無向圖模型，如下圖所示：

節點與節點之間是用無向的邊聯繫起來的，它代表節點與節點之間的相關關係，無因果關係或者不知道因果關係。

隱馬爾可夫模型

隱馬爾可夫模型（Hidden Markov Model，HMM），是一種有向圖模型。

什麼是馬爾可夫模型呢？給大家舉個例子：

現在有4個袋子，每個袋子裡面有10個球，袋子裡面的球情況如下：

這時候我們從4個袋子中隨機選一個袋子，從這個袋子中隨機抽出一個球，記錄其顏色，然後放回。然後從當前袋子隨機轉移到另外一個袋子，轉移的規則是這樣：如果當前袋子編號是1，那麼下一個袋子一定是袋子2；如果當前的袋子是2或3，那麼分別以0.4和0.6的概率轉移到左邊或右邊的袋子；如果當前袋子是4，那麼各以0.5的概率停留在袋子4或轉移到袋子3。我們確定轉移的袋子後，再從這個袋子中隨機抽出一個球，記錄其顏色，放回。上述過程重複5次，得到球的觀測序列：

O=｛紅，紅，藍，藍，紅｝

我們只能觀測到球顏色的序列，但是具體是從哪個袋子中取出的我們並不知道。

所以我們就可以有如下定義，

狀態序列：就是例子中所說的每次從哪個袋子中取出的球，狀態序列一般情況下我們是不知道的。

觀測序列：我們實際可以觀測到的東西，就是例子中每次取出的球的顏色，觀測序列一般情況下我們是知道的。

定義完了兩個序列，下面我們就要開始定義隱馬爾可夫模型中最重要的三個因素：

1.狀態轉移概率矩陣A

$A=[a_{ij}]_{N imes N}$

$a_{ij}$ 代表這一時刻狀態為 $i$ ，下一時刻狀態轉移到 $j$ 的概率，在上面的例子中狀態轉移概率矩陣為：

$A=left( egin{array}{ccc} 0 & 1 & 0& 0 \ 0.4 & 0 & 0.6& 0 \ 0 & 0.4 & 0 & 0.6\ 0 & 0 & 0.5 & 0.5\ end{array} ight)$

2.觀測概率矩陣B

觀測概率矩陣表示當處於某一狀態時，生成具體觀測的概率，在上面的例子中觀測矩陣為：

$A=left( egin{array}{ccc} 0.5 & 0.5 \ 0.3 & 0.7 \ 0.6 & 0.4\ 0.8 & 0.2\ end{array} ight)$

3.初始狀態概率向量 $pi$

初始狀態轉移概率向量表示最開始處於某一狀態的概率，在例子中，由於一開始是隨機選取了一個袋子，所以初始狀態概率向量為：

$pi=(0.25,0.25,0.25,0.25)^T$

隱馬爾可夫模型 $lambda$ 就是由上述三個要素決定，記作：

$lambda=(A,B,pi)$

狀態轉移矩陣A和初始狀態概率向量 $pi$ 決定了隱藏的馬爾可夫鏈，生成了不可觀測的狀態序列；觀測概率矩陣B確定了如何從狀態生成觀測，其與狀態序列一起決定了如何產生觀測序列。

有了上面的介紹，下面我們來規定一些符號：

設Q為所有可能的狀態的集合，V是所有可能的觀測的集合：

$Q=left{ q_1,q_2,...,q_N ight}, V=left{ v_1,v_2,...,v_M ight}$

其中N是可能的狀態數，M是可能的觀測數。在例子中，Q和V分別為：

Q={袋子1，袋子2，袋子3，袋子4，袋子5}；V=｛紅色，藍色｝

定義 $i$ 為長度為T的狀態序列，O為對應的觀測序列：

$I=left{ i_1,i_2,...,i_T ight},O=left{ o_1,o_2,...,o_T ight}$

在例子中，O對應為：

O=｛紅，紅，藍，藍，紅｝

定義完了上面的符號，我們引出隱馬爾可夫模型的兩個基本假設：

1.齊次馬爾可夫性假設，即假設隱藏的馬爾可夫鏈在任意時刻t的狀態只依賴於前一時刻的狀態，與其他時刻的狀態和觀測無關。

2.觀測獨立性假設，即假設任意時刻的觀測只依賴於該時刻的狀態，與其他狀態及觀測無關。

以上就是隱馬爾可夫模型的原理內容，那這個模型主要是為了解決什麼問題呢？

隱馬爾可夫問題的解法概述

1.基本問題

在實際應用中，人們比較關心隱馬爾可夫模型的3個基本問題：

1.給定模型 $lambda=(A,B,pi)$ 和觀測序列 $O=(o_1,o_2,...o_T)$ ，計算在模型 $lambda$ 下觀測序列O出現的概率 $P(O|lambda)$ 。換言之，如何評估模型和觀測序列之間的匹配程度？

2.已知觀測序列 $O=(o_1,o_2,...o_T)$ ，估計模型 $lambda=(A,B,pi)$ 的參數，使得在該模型下觀測序列概率 $P(O|lambda)$ 最大。換言之，如何訓練模型使其能最好地描述觀測數據？

3.已知模型 $lambda=(A,B,pi)$ 和觀測序列 $O=(o_1,o_2,...o_T)$ ，如何找到與此觀測序列最匹配的狀態序列 $I=(i_1,i_2,...i_T)$ 。換言之，如何根據觀測序列推斷出隱藏的狀態序列？

上述就是隱馬爾可夫模型的3個基本問題。這三個基本問題在現實應用中十分廣泛：

對於第一個問題，比如說我們要根據以往的觀測序列 $O=(o_1,o_2,...o_{T-1})$ 來推斷出當前時刻最有可能的觀測值 $o_T$ ，這就可以轉化為第一個問題求解概率 $P(O|lambda)$ 。

對於第二個問題，在大多數現實應用中，人工指定模型參數變得不太可行，如何根據訓練樣本學得最優的模型參數恰恰是第二個問題。

對於問題三，比如說在語音識別任務中，觀測值為語音信號，隱藏狀態為文字，目標就是根據觀測序列來找到最有可能的狀態序列（即對應的文字），這是問題3。

那這3個問題具體應該怎麼求解呢？

2.問題求解

這裡的問題求解部分只做簡單介紹，大家對解法有個印象就行，可以跳過，想要深入了解的讀者可自行查閱資料。

2.1 問題1求解

對於問題1，計算觀測序列概率 $P(O|lambda)$ ，我們一般採用前向和後向演算法。我在這裡簡要介紹前向演算法。

我們首先定義前向概率：

$alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|lambda)$

它表示我們在給定模型參數 $lambda$ 的條件下，到時刻t部分觀測序列為 $(o_1,o_2,...,o_t)$ 且狀態為 $q_i$ 的概率。

首先我們可以得到：

$alpha_1(i)=pi_ib_i(o_1)$

其中 $b_i(o_1)$ 表示隱藏狀態為 $i$ 時，其觀測狀態為 $o_1$ 的觀測概率。

之後我們得到

$alpha_2(i)=(sum_{j=1}^{N}{alpha_1(j)a_{ji}})b_i(o_2)$

其中 $a_{ji}$ 代表隱藏狀態由 $j$ 轉換為 $i$ 的狀態轉移概率。這樣經過一步步遞推可以得到：

$alpha_{t+1}(i)=(sum_{j=1}^{N}{alpha_t(j)a_{ji}})b_i(o_{t+1}),i=1,2,...N$

最終我們得到：

$P(O|lambda)=sum_{i=1}^{N}{alpha_T(i)}$

以上就是前向演算法的步驟，李航老師《統計學習方法》P177例10.2可以幫助大家理解，大家可以自行查閱。

2.2 問題2求解

對於問題2，我們假設有觀測序列O，想要學得隱馬爾可夫模型的參數 $lambda=(A,B,pi)$ ，這個參數估計問題可以由EM演算法求得。EM演算法我們將在下下次和大家一起學習。

2.3 問題3求解

問題3給定了觀測序列 $O=(o_1,o_2,...o_T)$ 和模型參數 $lambda=(A,B,pi)$ ，想要得到與觀測序列最匹配的狀態序列。

解決這個問題主要用到維特比演算法(Viterbi algorithm)，我簡述一下這個演算法的思路。定義：

$delta_t(i)=maxP(i_t=i,i_{t-1},...i_1,o_t,...o_1|lambda)$

其代表時刻為t時，隱藏狀態為 $i$ 的所有單個路徑中的最大值。這樣得到,

$delta_1(i)=pi_ib_i(o_1)$

其表示在開始時刻t=1時，隱藏狀態為 $i$ ，觀測狀態為 $o_1$ 的概率。其中 $b_i(o_1)$ 表示隱藏狀態為 $i$ 時觀測狀態為 $o_1$ 的觀測概率。

這樣，可以得到：

$delta_2(i)=maxleft[ delta_1(j)a_{ji} ight]b_i(o_2),1leq jleq N$

當我們得到的 $delta_2(i)$ 後，遞歸得到：

$delta_t(i)=maxleft[ delta_{t-1}(j)a_{ji} ight]b_i(o_t),1leq jleq N$

之後我們選擇：

$P^*=maxdelta_t(i),1leq ileq T$

這就是最優路徑，這裡求得的 $i$ 就是時刻為T時的最佳隱藏狀態。之後我們根據最優路徑往前倒推，就可以得到最佳的狀態序列。

對這個演算法想要深入了解的可以參照李航老師《統計學習方法》P185。

以上就是隱馬爾可夫模型全部的原理內容，希望能給大家一些幫助。下一次我們一起學習概率圖模型（2）：條件隨機場。

聲明

最後，所有資料均本人自學整理所得，如有錯誤，歡迎指正，有什麼建議也歡迎交流，讓我們共同進步！轉載請註明作者與出處

以上原理部分主要來自於《機器學習》—周志華，《統計學習方法》—李航，《機器學習實戰》—Peter Harrington。代碼部分主要來自於《機器學習實戰》，我對代碼進行了版本的改進，文中代碼用Python3實現，這是機器學習主流語言，本人也會儘力對代碼做出較為詳盡的注釋。