- 输入输出
已知观察序列，求概率最大的状态。
-
图
https://upload.wikimedia.org/wikipedia/commons/7/73/Viterbi_animated_demo.gif
image 思想
而维特比算法的精髓就是，既然知道到第i列所有节点Xi{j=123…}的最短路径，那么到第i+1列节点的最短路径就等于到第i列j个节点的最短路径+第i列j个节点到第i+1列各个节点的距离的最小值。复杂度
假设每一列节点最多有D个（也就是图的宽度为D），并且图一共有N列，那么，每次计算至多计算D*D次（从i列的D个节点中挑一个计算到i+1列D个节点的距离）。至多计算N次。那么复杂度骤减为，远远小于穷举
。
伪代码
for t in range(1, 观察序列长度)：
for state in (状态集合)：
V[t] = max([ ( V[t-1][ y0 ] * trans_p[y0][state] * emit_p[y0][ obs[t] ], y0 ) for y0 in states]) # 使得上一层状态y0 到本状态state 概率值最大
- 代码:
# coding:utf-8
'''
@file: vitebi.py
@time: 2018/10/18 下午8:43
@desc:
'''
states = ('Healthy', 'Fever')
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
transition_probability = {
'Healthy': {'Healthy': 0.7, 'Fever': 0.3},
'Fever': {'Healthy': 0.4, 'Fever': 0.6},
}
emission_probability = {
'Healthy': {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever': {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
# Helps visualize the steps of Viterbi.
def print_dptable(V):
print(" ")
for i in range(len(V)):
print("%7d" % i)
for y in V[0].keys():
print("%.5s: " % y)
for t in range(len(V)):
print("%.7s" % ("%f" % V[t][y]))
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}]
path = {}
# Initialize base cases (t == 0)
for y in states:
V[0][y] = start_p[y] * emit_p[y][obs[0]]
path[y] = [y]
# Run Viterbi for t > 0
for t in range(1, len(obs)):
V.append({})
newpath = {}
for y in states:
(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]
# Don't need to remember the old paths
path = newpath
print_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())
