Python機器學習算法實現

Author：louwill

Machine Learning Lab

? ? ?

HMM（Hidden Markov Model）也就是隱馬爾可夫模型，是一種由隱藏的馬爾可夫鏈隨機生成觀測序列的過程，是另一種經典的概率圖模型。本文在闡述HMM的基本定義和相關概念的基礎上，引申出HMM的三個重要問題：估計算法、學習算法和預測算法問題，并給出相應的代碼實現方式。

HMM的定義與相關概念

HMM是關于時序的概率模型，描述一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀測而產生隨機序列的過程。其中隱藏的馬爾可夫鏈隨機生成的狀態的序列稱之為狀態序列，每個狀態產生的狀態構成的序列，稱之為觀測序列。

HMM由初始狀態概率向量，狀態轉移概率矩陣和觀測概率矩陣決定，其中和決定狀態序列，決定觀測序列。所以，HMM可以用一個三元符號來表示：

設為所有可能的狀態的集合，是所有可能的觀測的集合：
，
其中是可能的狀態數，是可能的觀測數。

是長度為的狀態序列，是對應的觀測序列。
，

作為狀態轉移矩陣，可表達為：

其中：，是在時刻處于狀態的條件下在時刻轉移到狀態的概率。

作為觀測概率矩陣，可表達為：

其中：，是在時刻處于狀態條件下生成的觀測的概率。

文字和公式表述可能過于抽象，我們以一個具體的例子來看一下HMM。假設有4個盒子，每個盒子里面都要紅白兩種顏色的球，各個盒子里面的紅白球顏色數量分布如下表所示。

摸球規則如下：首先從4個盒子里等概率的選擇一個1個盒子，從這個盒子里隨機摸一個球，記錄顏色后放回。然后從當前盒子隨機地轉移到下一個盒子，轉移規則如下：如果當前盒子為1，那么下一個盒子一定是2，如果當前盒子是2或者3，則分別以概率0.4和0.6轉移到左邊或者右邊的盒子，如果當前的盒子是4，那么各以0.5的概率停留在4或者轉移到3，確定了轉移的盒子后，就從該盒子中隨機摸取一個球記錄其顏色并放回。將上述摸球試驗獨立重復進行5次，得到一個球的觀測序列為：
紅，紅，白，白，紅

我們按照HMM的三要素對該例子進行分析。在上述摸球過程中，我們只能觀測到摸到的球的顏色，即可以觀測到球的顏色序列；而觀察不到球是從哪個盒子摸到的，即觀測不到盒子的序列。所以，該例中狀態序列即為盒子的序列，觀測序列即為摸取到的球的顏色序列。具體如下所示。
狀態序列：盒子，盒子，盒子，盒子，

觀測序列：紅，白，，狀態序列和觀測序列長度，初始概率分布，狀態轉移概率分布矩陣為：

觀測概率矩陣為：

綜上，我們可以歸納一個長度為的觀測序列的生成過程如下：

• 按照初始狀態分布產生狀態

• 令

• 按照狀態的觀測概率分布生成

• 按照狀態的狀態轉移概率分布產生狀態，

• 令；如果，跳轉到第三步否則過程終止。

根據該例我們可編寫一個HMM觀測序列生成過程的代碼如下。

HMM的三個基本問題

跟CRF一樣，HMM也有三個基本問題，分別是概率估計、學習問題和預測問題。

HMM的估計算法

HMM的概率估計問題，即在給定模型和觀測序列，計算在模型下觀測序列出現的概率。

跟CRF一樣，HMM的概率估計方法依然是前向-后向算法。先來看前向算法。HMM定義前向概率如下：給定HMM模型，定義到時刻部分觀測序列且狀態為的概率為前向概率，記為：

可以看到前向概率是一個聯合概率。通過該定義可以遞推的計算前向概率及觀測序列概率。在輸入為HMM模型，觀測序列和輸出為觀測序列概率的情形下，觀測序列概率的前向算法表述如下：

• 初值：，

• 遞推：對，有，

• 終止：

下面給出前向概率算法的具體推導過程。根據前向概率的定義，可以推導初值為：

其中表示有狀態生成的觀測概率，假設在時刻觀測數據，則有：

且由前向概率定義可得：

根據上式，遍歷的取值求和，可得的邊際概率：

令，有:

上式推導中根據觀測獨立假設第一項可化簡為：

第二項可根據齊次馬爾可夫假設化簡為：

假設已知，在前向概率的定義的基礎上，有：

將前述化簡結果帶上上式，可得：

后向概率算法同理可推導。基于前向-后向概率我們可計算HMM的一些延申概率和期望，這里略過。

HMM的學習算法

HMM的第二個關鍵問題就是學習問題。即已知觀測序列，估計HMM模型的參數，使得在該模型下觀測序列概率$P(O|\lambda)最大。

當訓練數據集同時包含觀測序列和對應的狀態序列時，我們可以直接使用極大似然估計來估計HMM的模型參數。但大多數情況下，訓練數據僅有觀測序列而未給出對應的狀態序列，這時我們將觀測序列看作觀測數據，狀態序列看作不可觀測的隱數據，此時的HMM模型實際上一個含有隱變量的概率模型：

由第22講我們知道含有隱變量的概率模型可以通過EM算法來進行迭代求解。應用EM算法求解HMM模型參數也叫Baum-Welch算法。基于Baum-Welch算法求解HMM模型參數過程如下：

• 確定完全數據的對數似然函數
  將觀測數據寫為，隱數據寫為，完全數據可以寫為。完全數據的對數似然函數為。

• EM算法的E步：求函數
  
  其中為HMM參數的當前估計值，是要極大化的HMM參數。
  

• EM算法的M步：極大化函數求模型參數。

HMM的預測算法

HMM的預測問題也就是解碼問題。即再已知模型和觀測序列的情況下，求對給定觀測序列條件概率P(I|O)最大的狀態序列。即給定觀測序列，求最有可能的對應的狀態序列。

跟CRF預測算法一樣，HMM的預測算法同樣是一個求解最優路徑問題，所以解碼算法仍然是上一篇文章說到的維特比算法。關于維特比算法的通俗解釋，參考上一篇CRF的講解。基于維特比算法的HMM最優路徑求解過程如下。

• 初始化：，，

• 遞推。對:
  
  ，

• 終止：
  

• 最優路徑回溯。對:

HMM的代碼實現

完整的HMM需要實現的內容比較多。這里我們僅給出基于盒子摸球模型的HMM觀測序列生成過程和維特比解碼過程的參考實現方式。完整的算法筆者后續會在GitHub上給出。

基于4個盒子摸球的HMM模型的觀測序列生成過程如下：

import numpy as np# 根據給定的概率分布隨機返回數據 def get_data_with_distribution(dist): r = np.random.rand()for i, p in enumerate(dist):if r < p: return ir -= pdef generate(T):'''根據給定的參數生成觀測序列T: 指定要生成數據的數量'''# 根據初始概率分布生成第一個狀態z = get_data_with_distribution(pi) # 生成第一個觀測數據x = get_data_with_distribution(B[z]) result = [x]# 遍歷生成余下的狀態和觀測數據for _ in range(T-1): z = get_data_with_distribution(A[z])x = get_data_with_distribution(B[z])result.append(x)return result### 盒子和球相關的模型參數 # 初始狀態概率向量 pi = np.array([0.25, 0.25, 0.25, 0.25])# 狀態轉移概率矩陣 A = np.array([[0, 1, 0, 0],[.4, 0, .6, 0],[0, .4, 0, .6],[0, 0, .5, .5]])# 觀測概率矩陣 B = np.array([[0.5, 0.5],[0.3, 0.7],[0.6, 0.4],[0.8, 0.2]])# 生成10個數據 generate(10) [0, 0, 0, 0, 0, 0, 1, 1, 0, 0]

在已知模型參數和觀測序列的情況下，基于維特比算法的解碼反推最有可能的隱狀態序列：

def viterbi_decode(X):T, x = len(X), X[0]# 初始化delta = pi * B[:,x]varphi = np.zeros((T, N), dtype=int)path = [0] * T# 遞推for i in range(1, T):delta = delta.reshape(-1,1) tmp = delta * Avarphi[i,:] = np.argmax(tmp, axis=0)delta = np.max(tmp, axis=0) * B[:,X[i]]# 終止path[-1] = np.argmax(delta)# 最優路徑回溯for i in range(T-1,0,-1):path[i-1] = varphi[i,path[i]]return pathX = [1,0,1,0,0] N = 4 print(viterbi_decode(X)) [1, 0, 1, 2, 3]

參考資料：

李航 統計學習方法 第二版

https://zhuanlan.zhihu.com/p/85454896

往期精彩：

數學推導+純Python實現機器學習算法28：CRF條件隨機場

數學推導+純Python實現機器學習算法27：EM算法

數學推導+純Python實現機器學習算法26：隨機森林

數學推導+純Python實現機器學習算法25：CatBoost

數學推導+純Python實現機器學習算法24：LightGBM

數學推導+純Python實現機器學習算法23：kmeans聚類

數學推導+純Python實現機器學習算法22：最大熵模型

數學推導+純Python實現機器學習算法21：馬爾科夫鏈蒙特卡洛

數學推導+純Python實現機器學習算法20：LDA線性判別分析

數學推導+純Python實現機器學習算法19：PCA降維

數學推導+純Python實現機器學習算法18：奇異值分解SVD

數學推導+純Python實現機器學習算法17：XGBoost

數學推導+純Python實現機器學習算法16：Adaboost

數學推導+純Python實現機器學習算法15：GBDT

數學推導+純Python實現機器學習算法14：Ridge嶺回歸

數學推導+純Python實現機器學習算法13：Lasso回歸

數學推導+純Python實現機器學習算法12：貝葉斯網絡

數學推導+純Python實現機器學習算法11：樸素貝葉斯

數學推導+純Python實現機器學習算法10：線性不可分支持向量機

數學推導+純Python實現機器學習算法8-9：線性可分支持向量機和線性支持向量機

數學推導+純Python實現機器學習算法7：神經網絡

數學推導+純Python實現機器學習算法6：感知機

數學推導+純Python實現機器學習算法5：決策樹之CART算法

數學推導+純Python實現機器學習算法4：決策樹之ID3算法

數學推導+純Python實現機器學習算法3：k近鄰

數學推導+純Python實現機器學習算法2：邏輯回歸

數學推導+純Python實現機器學習算法1：線性回歸

---

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯獲取一折本站知識星球優惠券，復制鏈接直接打開：https://t.zsxq.com/yFQV7am本站qq群1003271085。加入微信群請掃碼進群：

總結

以上是生活随笔為你收集整理的【机器学习基础】数学推导+纯Python实现机器学习算法24：HMM隐马尔可夫模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。