# 维特比算法

## 算法

$\begin{array}{rcl} V_{1,k} &=& \mathrm{P}\big( y_1 \ | \ k \big) \cdot \pi_k \\ V_{t,k} &=& \mathrm{P}\big( y_t \ | \ k \big) \cdot \max_{x \in S} \left( a_{x,k} \cdot V_{t-1,x}\right) \end{array}$

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

## 伪代码

$T_1[i,j]=\max_{k}{(T_1[k,j-1]\cdot A_{ki}\cdot B_{ij})}$,
$T_2[i,j]=\arg\max_{k}{(T_1[k,j-1]\cdot A_{ki}\cdot B_{ij})}$
   输入:  观察空间 $O=\{o_1,o_2,\dots,o_N\}$,
状态 $S=\{s_1,s_2,\dots,s_K\}$,
观察序列  $Y=\{y_1,y_2,\ldots, y_T\}$ 若在$t$ 时间观察值为 $o_i$ ,则 $y_t==i$,
大小为 $K\cdot K$ 的转移矩阵 $A$, $A_{ij}$ 为从状态 $s_i$ 到 $s_j$ 的转移概率,
大小为 $K\cdot N$ 的放射矩阵 $B$, $B_{ij}$ 为状态 $s_i$ 观察到 $o_j$ 的概率,
初始概率数组 $\pi$ of size $K$, $\pi_i$ 为 $x_1 == s_i$ 的概率,
输出: 最有可能的隐含状态序列 $X=\{x_1,x_2,\ldots,x_T\}$
A01 function VITERBI( O, S,π,Y,A,B ) : X
A02     for each state si do
A03         T1[i,1]←πi$\cdot$Bi$y_1$
A04         T2[i,1]←0
A05     end for
A06     for i←2,3,...,T do
A07         for each state sj do
A08             T1[j,i]←$\max_{k}{(T_1[k,i-1]\cdot A_{kj}\cdot B_{jy_i})}$
A09             T2[j,i]←$\arg\max_{k}{(T_1[k,i-1]\cdot A_{kj}\cdot B_{jy_i})}$
A10         end for
A11     end for
A12     zT←$\arg\max_{k}{(T_1[k,T])}$
A13     xT←szT
A14     for i←T,T-1,...,2 do
A15         zi-1←T2[zi,i]
A16         xi-1←szi-1
A17     end for
A18     return X
A19 end function


## 例子

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