# 维特比算法

## 算法

${\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},
}


def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}]
path = {}

# Initialize
for st in states:
V[0][st] = start_p[st] * emit_p[st][obs[0]]
path[st] = [st]

# Run Viterbi when t > 0
for t in range(1,len(obs)):
V.append({})
newpath = {}

for curr_st in states:
paths_to_curr_st = []
for prev_st in states:
paths_to_curr_st.append((V[t-1][prev_st] * trans_p[prev_st][curr_st] * emit_p[curr_st][obs[t]], prev_st))
curr_prob, prev_state = max(paths_to_curr_st)
V[t][curr_st] = curr_prob
newpath[curr_st] = path[prev_state] + [curr_st]

# No need to keep the old paths
path = newpath

for line in dptable(V):
print(line)
prob, end_state = max([(V[-1][st], st) for st in states])
return prob, path[end_state]

def dptable(V):
# Print a table of steps from dictionary
yield ' ' * 4 + '    '.join(states)
for t in range(len(V)):
yield '{}   '.format(t) + '    '.join(['{:.4f}'.format(V[t][state]) for state in V[0]])


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