维特比算法

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.keys():        print("%.5s: " % y)        for t in range(len(V)):            print("%.7s" % ("%f" % V))        printdef viterbi(obs, states, start_p, trans_p, emit_p):    V =     path = {}    # Initialize base cases (t == 0)    for y in states:        V = start_p * emit_p]        path =     # Run Viterbi for t > 0    for t in range(1,len(obs)):        V.append({})        newpath = {}        for y in states:            (prob, state) = max( * trans_p * emit_p], y0) for y0 in states])            V = prob            newpath = path +         # Don't need to remember the old paths        path = newpath    print_dptable(V)    (prob, state) = max(, y) for y in states])    return (prob, path)

def example():    return viterbi(observations,                   states,                   start_probability,                   transition_probability,                   emission_probability)print(example())

维特比算法揭示了观察结果 最有可能由状态序列 产生。 换句话说，对于观察到的活动, 病人第一天感到正常，第二天感到冷时都是健康的，而第三天发烧了。

维特比算法的计算过程可以直观地由格图表示。 维特比路径本质上是穿过格式结构的最长路径。 诊所例子的格式结构如下, 黑色加粗的是维特比路径：

在实现维特比算法时需注意许多编程语言使用浮点数计算，当 p 很小时可能会导致结果下溢。 避免这一问题的常用技巧是在整个计算过程中使用对数概率，在对数系统中也使用了同样的技巧。 当算法结束时，可以通过适当的幂运算获得精确结果。

首先是一些问题必要的设置。 设观察值空间为 ${\displaystyle O=\{o_1,o_2,\dots <!--\; \dots \; -->,o_N\}}$、 状态空间为 ${\displaystyle S=\{s_1,s_2,\dots <!--\; \dots \; -->,s_K\}}$、 观察值序列为 ${\displaystyle Y=\{y_1,y_2,\dots <!--\; \dots \; -->,y_T\}}$, ${\displaystyle A}$ 为 ${\displaystyle K\times <!--\; \times \; -->K}$转移矩阵，其中 ${\displaystyle A_{ij}}$ 为从状态 ${\displaystyle s_i}$ 转移到 ${\displaystyle s_j}$ 的转移概率、 ${\displaystyle B}$ 为 ${\displaystyle K\times <!--\; \times \; -->N}$ 放射矩阵(emission matrix)，其中 ${\displaystyle B_{ij}}$ 为在状态 ${\displaystyle s_i}$ 观察到 ${\displaystyle o_j}$ 的概率、 大小为 ${\displaystyle K}$ 的初始概率数组 ${\displaystyle \mathrm{\pi <!--\; \pi \; -->}}$ ， ${\displaystyle {\mathrm{\pi <!--\; \pi \; -->}}_i}$ 为 ${\displaystyle x_1==s_i}$ 的概率。 我们称路径 ${\displaystyle X=\{x_1,x_2,\dots <!--\; \dots \; -->,x_T\}}$ 为生成观察值 ${\displaystyle Y=\{y_1,y_2,\dots <!--\; \dots \; -->,y_T\}}$ 的状态序列。

在这个动态规划问题中, 我们构造了两个大小为 ${\displaystyle K\times <!--\; \times \; -->T}$ 的二维表 ${\displaystyle T_1,T_2}$ 。 ${\displaystyle T_1}$ 的每个元素, ${\displaystyle T_1}$ ，保存生成 ${\displaystyle Y=\{y_1,y_2,\dots <!--\; \dots \; -->,y_j\}}$ 时最有可能的路径 ${\displaystyle \stackrel{^<!--\; ^\; -->}{X}=\{{\stackrel{^<!--\; ^\; -->}{x}}_1,{\stackrel{^<!--\; ^\; -->}{x}}_2,\dots <!--\; \dots \; -->,{\stackrel{^<!--\; ^\; -->}{x}}_j\}}$ ， ${\displaystyle {\stackrel{^<!--\; ^\; -->}{x}}_j=s_i}$ 的概率。 ${\displaystyle T_2}$ 的每个元素, ${\displaystyle T_2}$，保存最有可能路径 ${\displaystyle \stackrel{^<!--\; ^\; -->}{X}=\{{\stackrel{^<!--\; ^\; -->}{x}}_1,{\stackrel{^<!--\; ^\; -->}{x}}_2,\dots <!--\; \dots \; -->,{\stackrel{^<!--\; ^\; -->}{x}}_{j-<!--\; -\; -->1},{\stackrel{^<!--\; ^\; -->}{x}}_j\}}$ , ${\displaystyle \mathrm{\forall <!--\; \forall \; -->}j,2\le <!--\; \le \; -->j\le <!--\; \le \; -->T}$ 的 ${\displaystyle {\stackrel{^<!--\; ^\; -->}{x}}_{j-<!--\; -\; -->1}}$。

我们按 ${\displaystyle K\cdot <!--\; \cdot \; -->j+i}$ 增序填充两个表 ${\displaystyle T_1,T_2}$。