维特比算法求解HMM上的最短路径

下面是我的理解

一个东京的朋友每天根据天气{下雨，天晴}决定当天的活动{公园散步,购物,清理房间}中的一种，我每天只能在twitter上看到她发的推“啊，我前天公园散步、昨天购物、今天清理房间了！”，那么我可以根据她发的推特推断东京这三天的天气。在这个例子里，显状态是活动，隐状态是天气。

  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},
}

第一天是晴天的概率=0.4×0.6=0.24
第一天是雨天的概率=0.6×0.1=0.06

并不能因此判断第一天的天气，因为他们是最初始的，只有起始点指向它们（只有一个分支）还要根据第一天晴天雨天的概率计算第二天的天气概率。

第二天的情况分为s-r,r-r,r-s,s-s。因为第二天天气往前推的分支有两个，即第二天的前一天也就是第一天的天气情况有两种，因此可以比较s-r,r-r选出概率较大的那一个，剩下的指向雨天的分支去掉。比较s-s,r-s选出概率较大的那一个，剩下指向晴天的分支去掉。
s-r=0.4×8.6×0.4×0.4=0.384
r-r=0.6×0.1×0.7×0.4=0.168(舍)
s-s=0.4×0.6×0.6×0.3=0432
r-s=0.6×0.6×0.3×0.3=0.0054(舍)

同理选出第三天的天气，即为所求

演算

代码（参考网络）

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]# 对 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_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())

运行结果

原题链接
viterbi