维特比算法

维特比算法

维特比算法（Viterbi algorithm）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。

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

维特比算法由安德鲁·维特比(Andrew Viterbi)于1967年提出，用于在数字通信链路中解卷积以消除噪音。[1] 此算法被广泛应用于CDMA和GSM数字蜂窝网络、拨号调制解调器、卫星、深空通信和802.11无线网络中解卷积码。现今也被常常用于语音识别、关键字识别、计算语言学和生物信息学中。例如在语音(语音识别)中，声音信号做为观察到的事件序列,而文本字符串,被看作是隐含的产生声音信号的原因，因此可对声音信号应用维特比算法寻找最有可能的文本字符串。

算法

假设给定隐式马尔可夫模型（HMM）状态空间 ，初始状态  的概率为  ，从状态  到状态  的转移概率为 。 令观察到的输出为 。 产生观察结果的最有可能的状态序列  由递推关系给出：[2]

此处  是前  个最终状态为  的观测结果最有可能对应的状态序列的概率。 通过保存向后指针记住在第二个等式中用到的状态  可以获得维特比路径。声明一个函数  ，它返回若 时计算  用到的  值 或若 时的 . 这样:

这里我们使用了arg max的标准定义。
算法复杂度为 

伪代码

首先是一些问题必要的设置。 设观察值空间为 、 状态空间为 、 观察值序列为 ,  为 转移矩阵 ，其中  为从状态  转移到  的转移概率、  为  放射矩阵(emission matrix)，其中  为在状态  观察到  的概率、 大小为  的初始概率数组  ，  为  的概率。 我们称路径  为生成观察值  的状态序列。

在这个动态规划问题中, 我们构造了两个大小为  的二维表  。  的每个元素,  ，保存生成  时最有可能的路径  ，  的概率。  的每个元素,  , 保存最有可能路径  ,  的 。

我们按  增序填充两个表 。

,

   输入:  观察空间 , 

           状态 , 

           观察序列   若在 时间观察值为  ,则 ,

           大小为  的转移矩阵 ,  为从状态  到  的转移概率,

           大小为  的放射矩阵 ,  为状态  观察到  的概率, 

           初始概率数组  of size ,  为  的概率, 

   输出: 最有可能的隐含状态序列 

A01 function VITERBI( O, S,π,Y,A,B ) : X

A02     for each state si do

A03         T1[i,1]←πiBi

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

A09             T2[j,i]←

A10         end for

A11     end for

A12     zT←

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