# 维特比算法

## 算法

${\displaystyle {\begin{array}{rcl}V_{1,k}&=&\mathrm {P} {\big (}y_{1}\ |\ k{\big )}\cdot \pi _{k}\\V_{t,k}&=&\max _{x\in S}\left(\mathrm {P} {\big (}y_{t}\ |\ k{\big )}\cdot a_{x,k}\cdot V_{t-1,x}\right)\end{array}}}$

${\displaystyle {\begin{array}{rcl}x_{T}&=&\arg \max _{x\in S}(V_{T,x})\\x_{t-1}&=&\mathrm {Ptr} (x_{t},t)\end{array}}}$

## 例子

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)
print

for y in V[0].keys():
print("%.5s: " % y)
for t in range(len(V)):
print("%.7s" % ("%f" % V[t][y]))
print

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())


## 伪代码

${\displaystyle T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}}$ ,
${\displaystyle T_{2}[i,j]=\arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}}$

• 观察空间 ${\displaystyle O=\{o_{1},o_{2},\dots ,o_{N}\}}$
• 状态 ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{K}\}}$
• 观察序列 ${\displaystyle Y=\{y_{1},y_{2},\ldots ,y_{T}\}}$  若在${\displaystyle t}$  时间观察值为 ${\displaystyle o_{i}}$ ，则 ${\displaystyle y_{t}==i}$ ,
• 大小为 ${\displaystyle K\cdot K}$  的转移矩阵 ${\displaystyle A}$ ${\displaystyle A_{ij}}$  为从状态 ${\displaystyle s_{i}}$ ${\displaystyle s_{j}}$  的转移概率，
• 大小为 ${\displaystyle K\cdot N}$  的放射矩阵 ${\displaystyle B}$ ${\displaystyle B_{ij}}$  为状态 ${\displaystyle s_{i}}$  观察到 ${\displaystyle o_{j}}$  的概率，
• 大小为 ${\displaystyle K}$  的初始概率数组 ${\displaystyle \pi }$ ${\displaystyle \pi _{i}}$ ${\displaystyle x_{1}==s_{i}}$  的概率，

• 最有可能的隐含状态序列 ${\displaystyle X=\{x_{1},x_{2},\ldots ,x_{T}\}}$
 function VITERBI( .mw-parser-output .serif{font-family:Times,serif}O, S, π, Y, A, B ) : X
for each state si do
T1[i,1] ← πi·Biy1
T2[i,1] ← 0
end for
for i ← 2,3,...,T do
for each state sj do
${\displaystyle T_{1}[j,i]\gets \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}}$
${\displaystyle T_{2}[j,i]\gets \arg \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}}$
end for
end for
${\displaystyle z_{T}\gets \arg \max _{k}{(T_{1}[k,T])}}$
xT ← szT
for i ← T,T-1,...,2 do
zi-1 ← T2[zi,i]
xi-1 ← szi-1
end for
return X
end function


## 注释

1. ^ 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History. [2012-11-23]. （原始内容存档于2016-06-02）.
2. ^ Xing E, slide 11