HMM：Hidden Markov Model，是用來描述隱含未知參數的統計模型，由顯狀態（可觀測序列）、隱狀態、發射概率（隱狀態產生顯狀態的概率）、轉移概率（顯狀態之間的轉換）、初始概率（通常指隱狀態）五部分構成，關于HMM的原理，這里我不便過多贅述，有原理不清的同學，建議大家參考這邊博客，寫得十分詳細：https://www.cnblogs.com/skyme/p/4651331.html

那么給定一個顯狀態序列（觀測狀態），我們如何根據給定內容來推斷隱狀態序列呢？我們這里就來介紹（Viterbi）維特比算法

這里我們通過一個十分著名的例子來理解維特比算法思想，以及代碼部分：

例：一個東京的朋友每天根據天氣{下雨，天晴}決定當天的活動{公園散步,購物,清理房間}中的一種，我每天只能在twitter上看到她發的推“啊，我前天公園散步、昨天購物、今天清理房間了！”，那么我可以根據她發的推特推斷東京這三天的天氣。在這個例子里，顯狀態是活動，隱狀態是天氣。

現在我們已知：

初始概率：{'Rainy':?0.6,?'Sunny':?0.4}

轉換概率：{ 'Rainy'?:?{'Rainy':?0.7,?'Sunny':?0.3},? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 'Sunny'?:?{'Rainy':?0.4,?'Sunny':?0.6},}

發射概率：{ 'Rainy'?:?{'walk':?0.1,?'shop':?0.4,?'clean':?0.5},? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 'Sunny'?:?{'walk':?0.6,?'shop':?0.3,?'clean':?0.1},}

讓我們來預測東京的天氣。

思路：例，第一天晴的概率P(一，晴) = P(晴) * P(散步 | 晴)，即初始概率 * 發射概率。分別計算第一天晴和陰的概率來更新初始化概率。

第二天晴的概率 = P(一，晴) * P(晴->晴) * P(購物 | 晴)，即初始概率 * 轉換概率 * 發射概率。注意，這里的初始化：這里會在第一天的基礎上計算4組，兩組晴天概率，兩組陰天概率，選各組的最大值作為最終結果，并更新初始化概率。

第三天依然如此，要在上一天的基礎上計算四組，如果第三天是序列最后一個值，則計算4組中的唯一一個最大值作為結果，并回溯，得到隱狀態預測序列，算法結束。否則重復：‘兩組晴天概率，兩組陰天概率，選各組的最大值作為最終結果，并更新初始化概率 ’操作。

值得注意的是，這里的回溯選擇和回溯可以說是維特比算法的經典，也是維特比算法不同于前向傳播的地方，大家要注意這一點。

代碼：這里的代碼鏈接：https://github.com/hankcs/Viterbi

現在我們來看代碼：

#初始化條件 states = ('Rainy', 'Sunny')observations = ('walk', 'shop', 'clean')start_probability = {'Rainy': 0.6, 'Sunny': 0.4}transition_probability = {'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},}emission_probability = {'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}, }# 打印每一次計算的保留值，對應到本題即晴天，陰天各自的最大值 def print_dptable(V):print " ",for i in range(len(V)): print "%7d" % i,printfor y in V[0].keys():print "%.5s: " % y,for t in range(len(V)):print "%.7s" % ("%f" % V[t][y]),printdef viterbi(obs, states, start_p, trans_p, emit_p):""":param obs:觀測序列:param states:隱狀態:param start_p:初始概率（隱狀態）:param trans_p:轉移概率（隱狀態）:param emit_p: 發射概率 （隱狀態表現為顯狀態的概率）:return:"""# 路徑概率表 V[時間][隱狀態] = 概率V = [{}]# 一個中間變量，代表當前狀態是哪個隱狀態path = {}# 初始化初始狀態 (t == 0)，即第一天的計算在這里進行for y in states:V[0][y] = start_p[y] * emit_p[y][obs[0]]path[y] = [y]# 對第二天及以后應用維特比算法for t in range(1, len(obs)):V.append({})newpath = {}for y in states:#這里即為計算每一組中的最大值，即前一天陰天的的情況下今天是y的概率，以及前一天晴天時今天是y的概率中選擇一個最大值#隱狀態概率 = 前狀態是y0的概率 * y0轉移到y的概率 * y在t狀態是為當前狀態的概率(prob, state) = max([(V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])# 記錄最大概率V[t][y] = prob# 記錄路徑，這里為了方便回溯，記錄回溯結果newpath[y] = path[state] + [y]# 記錄回溯結果path = newpathprint_dptable(V)(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])return (prob, path[state])def example():return viterbi(observations,states,start_probability,transition_probability,emission_probability)print example()

運行結果：

0 1 2 Rainy: 0.06000 0.03840 0.01344 Sunny: 0.24000 0.04320 0.00259 (0.01344, ['Sunny', 'Rainy', 'Rainy'])

通過這樣一個簡單的例子我們就能明白維特比算法的原理了。

總結

以上是生活随笔為你收集整理的HMM：Hidden Markov Model 代码讲解的全部內容，希望文章能夠幫你解決所遇到的問題。

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