查看“︁维特比算法”︁的源代码

{{NoteTA
|G1=Math
|G2=IT}}
'''维特比算法'''（{{lang-en|Viterbi algorithm}}）是一种[[动态规划]][[算法]]。它用于寻找[[最大后验概率|最有可能产生观测事件序列]]的'''维特比路径'''——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。

术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在[[统计句法分析]]中动态规划算法可以被用于发现最可能的上下文无关的派生（解析）的字符串，有时被称为“维特比分析”。

维特比算法由[[安德鲁·维特比]]于1967年提出，用于在数字通信链路中解卷积以消除噪音。<ref>{{Cite web |url=http://arxiv.org/abs/cs/0504020v2 |title=29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History |accessdate=2012-11-23 |archive-date=2016-06-02 |archive-url=https://web.archive.org/web/20160602230628/http://arxiv.org/abs/cs/0504020v2 |dead-url=no }}</ref> 此算法被广泛应用于[[CDMA]]和[[GSM]]数字蜂窝网络、拨号调制解调器、卫星、深空通信和[[802.11]]无线网络中解卷积码。现今也被常常用于[[语音识别]]、[[关键字识别]]、[[计算语言学]]和[[生物信息学]]中。例如在语音（语音识别）中，声音信号做为观察到的事件序列，而文本字符串，被看作是隐含的产生声音信号的原因，因此可对声音信号应用维特比算法寻找最有可能的文本字符串。

==算法==
假设给定[[隐马尔可夫模型|隐式马尔可夫模型]]（HMM）状态空间 <math>S</math>，共有k个状态，初始状态 <math>i</math> 的概率为 <math>\pi_i</math> ，从状态 <math>i</math> 到状态 <math>j</math> 的转移概率为 <math>a_{i,j}</math>。 令观察到的输出为 <math>y_1,\dots, y_T</math>。 产生观察结果的最有可能的状态序列 <math>x_1,\dots,x_T</math> 由递推关系给出：<ref>Xing E, slide 11</ref>

:<math>
\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}
</math>

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

:<math>
\begin{array}{rcl}
x_T &=& \arg\max_{x \in S} (V_{T,x}) \\
x_{t-1} &=& \mathrm{Ptr}(x_t,t)
\end{array}
</math>
这里我们使用了{{link-en|arg max|arg max}}的标准定义
算法复杂度为 <math>O(T\times\left|{S}\right|^2)</math>

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

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

医生知道村民的总体健康状况，还知道发烧和没发烧的病人通常会抱怨什么症状。 换句话说，医生知道隐马尔可夫模型的参数。 这可以用[[Python]]语言表示如下:
<syntaxhighlight lang="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},
   }
</syntaxhighlight>
在这段代码中, 起始概率<code>start_probability</code> 表示病人第一次到访时医生认为其所处的HMM状态，他唯一知道的是病人倾向于是健康的。这里用到的特定概率分布不是均衡的,如转移概率大约是<code>{'Healthy': 0.57, 'Fever': 0.43}</code>。 转移概率<code>transition_probability</code>表示潜在的马尔可夫链中健康状态的变化。在这个例子中，当天健康的病人仅有30%的机会第二天会发烧。放射概率<code>emission_probability</code>表示每天病人感觉的可能性。假如他是健康的，50%会感觉正常。如果他发烧了，有60%的可能感觉到头晕。

[[File:An example of HMM.png|border|center|400px|Graphical representation of the given HMM]]

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

<syntaxhighlight lang="python" line="1">

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

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

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

<syntaxhighlight lang="python">
def example():
    return viterbi(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability)
print(example())
</syntaxhighlight>

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

维特比算法的计算过程可以直观地由[[卷积码|格图]]表示。 维特比路径本质上是穿过格式结构的最长路径。 诊所例子的格式结构如下, 黑色加粗的是维特比路径：
[[Image:Viterbi animated demo.gif|border|center|Animation of the trellis diagram for the Viterbi algorithm. After Day 3, the most likely path is <code>['Healthy', 'Healthy', 'Fever']</code>]]

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

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

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

我们按 <math>K\cdot j+i </math> 增序填充两个表 <math> T_1[i,j],T_2[i,j]</math>。

:<math>T_1[i,j]=\max_{k}{(T_1[k,j-1]\cdot A_{ki}\cdot B_{iy_j})} </math>,
:<math> T_2[i,j]=\arg\max_{k}{(T_1[k,j-1]\cdot A_{ki}\cdot B_{iy_j})} </math>

;输入:
*            观察空间 <math> O=\{o_1,o_2,\dots,o_N\}</math>，
*            状态 <math> S=\{s_1,s_2,\dots,s_K\} </math>，
*            观察序列  <math> Y=\{y_1,y_2,\ldots, y_T\} </math> 若在<math> t </math> 时间观察值为 <math> o_i </math>，则 <math> y_t==i </math>,
*            大小为 <math> K\cdot K </math> 的转移矩阵 <math> A </math>，<math> A_{ij} </math> 为从状态 <math> s_i </math> 到 <math> s_j </math> 的转移概率，
*            大小为 <math> K\cdot N </math> 的放射矩阵 <math> B </math>，<math> B_{ij} </math> 为状态 <math> s_i </math> 观察到 <math> o_j </math> 的概率，
*            大小为 <math> K </math> 的初始概率数组 <math> \pi </math>，<math> \pi_i </math> 为 <math> x_1 ==  s_i </math> 的概率，
;输出:
*最有可能的隐含状态序列 <math> X=\{x_1,x_2,\ldots,x_T\} </math>
  '''function''' ''VITERBI''( {{math|''O'', ''S'', ''π'', ''Y'', ''A'', ''B''}} ) : {{mvar|X}}
      '''for''' each state {{math|''s<sub>i</sub>''}} '''do'''
          {{math|''T''<sub>1</sub>[''i'',1] ← ''π<sub>i</sub>''&middot;''B''<sub>''iy''<sub>1</sub></sub>}}
          {{math|''T''<sub>2</sub>[''i'',1] ← 0}}
      '''end for'''
      '''for''' {{math|''i'' ← ''2'',''3'',...,''T''}} '''do'''
          '''for''' each state {{math|''s<sub>j</sub>''}} '''do'''
              {{nowrap|<math>T_1[j,i] \gets \max_{k}{(T_1[k,i-1]\cdot A_{kj}\cdot B_{jy_i})} </math>}}
              {{nowrap|<math>T_2[j,i] \gets \arg\max_{k}{(T_1[k,i-1]\cdot A_{kj}\cdot B_{jy_i})} </math>}}
          '''end for'''
      '''end for'''
      {{nowrap|<math>z_T \gets \arg\max_{k}{(T_1[k,T])} </math>}}
      {{math|''x<sub>T</sub>'' ← s<sub>z<sub>T</sub></sub>}}
      '''for''' {{math|''i'' ← ''T'',''T-1'',...,''2''}} '''do'''
          {{math|''z<sub>i-1</sub>'' ← ''T''<sub>2</sub>[''z''<sub>i</sub>,i]}}
          {{math|''x<sub>i-1</sub>'' ← ''s<sub>z<sub>i-1</sub></sub>''}}
      '''end for'''
      '''return''' {{mvar|X}}
  '''end function'''

== 使用动态规划的算法 ==
* [[最长公共子序列]]
* [[Floyd-Warshall算法]]

==注释==
<references />

==参考资料==
* {{cite journal |doi=10.1109/TIT.1967.1054010 |author=Viterbi AJ |title=Error bounds for convolutional codes and an asymptotically optimum decoding algorithm |journal=IEEE Transactions on Information Theory |volume=13 |issue=2 |pages=260–269 |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1054010 |date=April 1967 |access-date=2012-11-23 |archive-date=2020-07-29 |archive-url=https://web.archive.org/web/20200729112810/https://ieeexplore.ieee.org/document/1054010/;jsessionid=RhaaVGv5VL04dEbgnME4baPbmgiDj18xfqRP6XbUHnXiQqBD1431!-1215303959 |dead-url=no }} (note: the Viterbi decoding algorithm is described in section IV.) Subscription required.


[[Category:最优化算法]]
[[Category:动态规划]]
[[Category:错误检测与校正]]
[[Category:马尔可夫模型]]