3.5 用于解码HMM状态序列的维特比算法
3.5.1 动态规划和维特比算法
动态规划（DP）是一种分而治之地解决复杂问题的方法，它通过将复杂问题分成一些更简单的问题来实现目标[112, 113]。这个算法最开始由R.Bellman在20世纪50年代发明[112]。DP算法的基本依据是Bellman最优化准则。该准则保证：“在关于数个阶段之间互不关联的优化问题中，不管初始状态或者初始决策是什么，剩余的决策都应该包含一个最优的方法用于选择从第一个选择得到的状态中去得到剩余的决策。”
作为一个例子，我们将讨论马尔可夫决策过程中的优化准则，马尔可夫决策过程由两部分参数决定。第1部分参数是转移概率
其中，系统的当前状态只依赖于系统的前一阶段所处的状态及在那个状态上所采取的决策（符合马尔可夫特性）。第2部分参数提供了决策收益，其定义如下：
=在n阶段和状态i上，采用决策k时得到的收益。
下面定义F(n, i）作为阶段n和状态i上最优决策被采取时的平均总收益。这可以通过DP算法遵循下面的优化准则而递归得到：
特别地，当n=N（即最后阶段）时，状态i的总收益为
最优决策序列可以在最后一轮递归计算之后进行回溯。
从上面的分析可以得到，在运用DP算法时，优化过程的不同阶段（例如，上例中的阶段1, 2, ..., n, ..., N）需要被区分定义。我们需要在每个阶段上做最优化决策。系统中针对每个阶段都有许多不同的状态（在上例中以i为标识）。对给定阶段所采取的决策（以k为标识）使问题依据状态转移概率
，从当前阶段n转变到下一阶段n+1。
如果应用DP算法来寻找最优路径，则Bellman优化准则将转化为下面的形式：“从A到C且经过节点B的最优路径必须包含从A到B的最优路径，以及从B到C的最优路径。”这个优化准则的推论是很有意义的。也就是说，为了找到从节点A通过一个“前提”的节点B到C的最优路径，并没有必要去重新考虑所有可能的从A到B的局部路径。相比于穷尽式的搜索方法，显著地减少了路径搜索消耗。当不能确认前提节点B是否在最优路径上时，许多候选的节点将被一一衡量，由此通过DP算法的回溯步骤能够最终决定。Bellman优化准则是下面将讨论的这种用于HMM语音处理上非常流行的优化算法的基本点。
3.5.2 用于解码HMM状态的动态规划算法
关于前面讨论的HMM，需要解决的一个基本运算问题就是，在给定一组观察序列
的情况下，如何高效地找到最优的HMM状态序列。这是一个复杂的T阶路径寻找优化问题，并直接适合于使用DP算法来求解。DP算法应用于这样的求解目标时，也被称为维特比算法，该算法一开始是用来解决数字通信中的信道最优卷积编码问题的。
为了说明作为一种最优路径搜索技术的维特比算法，我们可以使用二维梯度（或称为格子图）来刻画一个从左向右传播的HMM。图中的横轴表示时间为第t帧，纵轴表示第i个HMM状态。
对一个状态转移概率aij给定的HMM，设状态输出概率分布为bi(ot)，令δi(t）表示部分观察序列
的到达时间t，同时相应的HMM状态序列在该时间处在状态i时的联合似然度的最大值为
注意到每一个给定的δi(t）都对应格子图中的一个节点。每一个新增的时间都对应在DP算法中去向一个新的阶段。在最终的阶段t=T，我们有最优函数δi(T)，这个最优函数通过计算所有t≤T−1的阶段来得到。基于DP最优准则，对公式（3.50）在当前处理的t+1阶段的局部最优似然度，可以使用下面的函数等式来递归得到：
对每一个状态j，每一个正在处理阶段的状态都是一个以在全局最优路径中的假设为先导的节点。所有这样的节点在经过回溯操作之后，除最终的一个外，都将被淘汰。这里使用的DP算法的基本点是，作为一个在格子图中的独立节点，我们只需要计算δj(t+1）的大小，这样就避免了保存大量从初始阶段到当前t+1阶段的局部路径的需求，也就避免了这些额外的搜索消耗。使用DP优化准则能够在线性计算复杂度的情况下保证其最优化结果，而避免了随着观察数据序列长度T增长而带来的大量计算量增加。
除了公式（3.50）中的最主要递归流程，完整的维特比算法要求额外的递归初始化、递归终止条件和路线回溯。完整的算法在算法3.2中给出，其中初始状态概率为πi。维特比算法的结果包含最大联合似然度观察和状态序列P*，以及相应的状态转移路径q*(t)。
上面使用维特比算法找到的针对一个从左到右传播的HMM的最佳状态转移路径，等价于确定最优HMM状态分割所需要的信息。状态分割的概念在语音建模和识别中最常用于从左到右传播的HMM，其中每个HMM状态通常都与较大数量的连续帧数的观察向量序列相对应。这是因为观察值不能被简单地对应回早先的状态，同时因为从左向右传播的限制，而且在从左到右的HMM中，最后一帧需要对应最右边的状态。
注意，相同的维特比算法也可以被应用到单高斯HMM，有关GMMHMM和DNN-HMM的情况，我们将在第6章中详细讨论。