维特比算法

假设给定隐式马尔可夫模型（HMM）状态空间 ${\displaystyle S}$，共有k个状态，初始状态 ${\displaystyle i}$ 的概率为 ${\displaystyle \pi _{i}}$ ，从状态 ${\displaystyle i}$ 到状态 ${\displaystyle j}$ 的转移概率为 ${\displaystyle a_{i,j}}$。 令观察到的输出为 ${\displaystyle y_{1},\dots ,y_{T}}$。 产生观察结果的最有可能的状态序列 ${\displaystyle x_{1},\dots ,x_{T}}$ 由递推关系给出：[2]

${\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 V_{t,k}}$ 是前 ${\displaystyle t}$ 个最终状态为 ${\displaystyle k}$ 的观测结果最有可能对应的状态序列的概率。 通过保存向后指针记住在第二个等式中用到的状态 ${\displaystyle x}$ 可以获得维特比路径。声明一个函数 ${\displaystyle \mathrm {Ptr} (k,t)}$ ，它返回若 ${\displaystyle t>1}$时计算 ${\displaystyle V_{t,k}}$ 用到的 ${\displaystyle x}$ 值 或若 ${\displaystyle t=1}$时的${\displaystyle k}$ . 这样:

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

这里我们使用了arg max的标准定义 算法复杂度为 ${\displaystyle O(T\times \left|{S}\right|^{2})}$

想象一个乡村诊所。村民有着非常理想化的特性，要么健康要么发烧。他们只有问诊所的医生的才能知道是否发烧。 聪明的医生通过询问病人的感觉诊断他们是否发烧。村民只回答他们感觉正常、头晕或冷。

假设一个病人每天来到诊所并告诉医生他的感觉。医生相信病人的健康状况如同一个离散马尔可夫链。病人的状态有两种“健康”和“发烧”，但医生不能直接观察到，这意味着状态对他是“隐含”的。每天病人会告诉医生自己有以下几种由他的健康状态决定的感觉的一种：正常、冷或头晕。这些是观察结果。 整个系统为一个隐马尔可夫模型(HMM)。

医生知道村民的总体健康状况，还知道发烧和没发烧的病人通常会抱怨什么症状。 换句话说，医生知道隐马尔可夫模型的参数。 这可以用Python语言表示如下:

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},
   }

在这段代码中, 起始概率start_probability 表示病人第一次到访时医生认为其所处的HMM状态，他唯一知道的是病人倾向于是健康的。这里用到的特定概率分布不是均衡的,如转移概率大约是{'Healthy': 0.57, 'Fever': 0.43}。 转移概率transition_probability表示潜在的马尔可夫链中健康状态的变化。在这个例子中，当天健康的病人仅有30%的机会第二天会发烧。放射概率emission_probability表示每天病人感觉的可能性。假如他是健康的，50%会感觉正常。如果他发烧了，有60%的可能感觉到头晕。

Graphical representation of the given HMM

病人连续三天看医生，医生發现第一天他感觉正常，第二天感觉冷，第三天感觉头晕。 于是医生产生了一个问题：怎样的健康状态序列最能够解释这些观察结果。维特比算法解答了这个问题。

# 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])

函数viterbi 具有以下参数: obs 为观察结果序列, 例如 ['normal', 'cold', 'dizzy']； states 为一组隐含状态； start_p 为起始状态概率; trans_p 为转移概率; 而 emit_p 为放射概率。 为了简化代码，我们假设观察序列 obs 非空且 trans_p[i][j] 和 emit_p[i][j] 对所有状态 i,j 有定义。

在运行的例子中正向/维特比算法使用如下:

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

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

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

Animation of the trellis diagram for the Viterbi algorithm. After Day 3, the most likely path is ['Healthy', 'Healthy', 'Fever']

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

首先是一些问题必要的设置。 设观察值空间为 ${\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 A}$ 为 ${\displaystyle K\times K}$转移矩阵，其中 ${\displaystyle A_{ij}}$ 为从状态 ${\displaystyle s_{i}}$ 转移到 ${\displaystyle s_{j}}$ 的转移概率、 ${\displaystyle B}$ 为 ${\displaystyle K\times N}$ 放射矩阵(emission matrix)，其中 ${\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}\}}$ 为生成观察值 ${\displaystyle Y=\{y_{1},y_{2},\ldots ,y_{T}\}}$ 的状态序列。

在这个动态规划问题中, 我们构造了两个大小为 ${\displaystyle K\times T}$ 的二维表 ${\displaystyle T_{1},T_{2}}$ 。 ${\displaystyle T_{1}}$ 的每个元素, ${\displaystyle T_{1}[i,j]}$ ，保存生成 ${\displaystyle Y=\{y_{1},y_{2},\ldots ,y_{j}\}}$ 时最有可能的路径 ${\displaystyle {\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j}\}}$ ， ${\displaystyle {\hat {x}}_{j}=s_{i}}$ 的概率。 ${\displaystyle T_{2}}$ 的每个元素, ${\displaystyle T_{2}[i,j]}$，保存最有可能路径 ${\displaystyle {\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}\}}$ , ${\displaystyle \forall j,2\leq j\leq T}$ 的 ${\displaystyle {\hat {x}}_{j-1}}$。

我们按 ${\displaystyle K\cdot j+i}$ 增序填充两个表 ${\displaystyle T_{1}[i,j],T_{2}[i,j]}$。

${\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( 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

• 最长公共子序列
• Floyd-Warshall算法

1. . [2012-11-23]. （原始内容存档于2016-06-02）.
2. Xing E, slide 11

• Viterbi AJ. . IEEE Transactions on Information Theory. April 1967, 13 (2): 260–269 [2012-11-23]. doi:10.1109/TIT.1967.1054010. （原始内容存档于2020-07-29）. (note: the Viterbi decoding algorithm is described in section IV.) Subscription required.