HMM（隱馬爾可夫模型）是用來描述隱含未知參數的統計模型，舉一個經典的例子：一個朋友每天根據天氣{下雨，天晴}決定當天的活動{公園散步,購物,清理房間}中的一種，我每天只能在twitter上看到她發的推“啊，我前天公園散步、昨天購物、今天清理房間了！”，那么我可以根據她發的推特推斷東京這三天的天氣。在這個例子里，顯狀態是活動，隱狀態是天氣。
任何一個HMM都可以通過下列五元組來描述：

:param obs:觀測序列:param states:隱狀態:param start_p:初始概率（隱狀態）:param trans_p:轉移概率（隱狀態）:param emit_p: 發射概率 （隱狀態表現為顯狀態的概率）:return:

這個例子可以用如下的HMM來描述：
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}, }

求解最可能的隱狀態序列是HMM的三個典型問題之一，通常用維特比算法解決。維特比算法就是求解HMM上的最短路徑（-log(prob)，也即是最大概率）的算法。

稍微用中文講講思路，很明顯，第一天天晴還是下雨可以算出來：

定義V[時間][今天天氣] = 概率，注意今天天氣指的是，前幾天的天氣都確定下來了（概率最大）今天天氣是X的概率，這里的概率就是一個累乘的概率了。因為第一天我的朋友去散步了，所以第一天下雨的概率V[第一天][下雨] = 初始概率[下雨] * 發射概率[下雨][散步] = 0.6 * 0.1 = 0.06，同理可得V[第一天][天晴] = 0.24 。從直覺上來看，因為第一天朋友出門了，她一般喜歡在天晴的時候散步，所以第一天天晴的概率比較大，數字與直覺統一了。從第二天開始，對于每種天氣Y，都有前一天天氣是X的概率 * X轉移到Y的概率 * Y天氣下朋友進行這天這種活動的概率。因為前一天天氣X有兩種可能，所以Y的概率有兩個，選取其中較大一個作為V[第二天][天氣Y]的概率，同時將今天的天氣加入到結果序列中比較V[最后一天][下雨]和[最后一天][天晴]的概率，找出較大的哪一個對應的序列，就是最終結果。

代碼如下：

#coding:utf-8 ''' Created on 2017-5-24@author: 劉帥 ''' 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:print obs[0]V[0][y] = start_p[y] * emit_p[y][obs[0]]path[y] = [y]# 對 t > 0 跑一遍維特比算法for t in range(1, len(obs)):V.append({})newpath = {}for y in states:# 概率 隱狀態 = 前狀態是y0的概率 * y0轉移到y的概率 * y表現為當前狀態的概率(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 path#print pathprint_dptable(V)(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])print statereturn (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’])

我們發現感覺應該是sunny，sunny，rainy
但是當第三步時候要取得最大值0.01344，第二天必須是rainy，所以結果是sunny，rainy，rainy

即0.0384 * 0.5 * 0.7 = 0.01344

總結

以上是生活随笔為你收集整理的HMM之维特比算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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