HMM中的维特比解码(Viterbi Agorithm)

在之前的文章中，已经分别介绍了隐马科夫模型（HMM）的概况以及HMM中广泛应用的一种解决估值问题的算法：前向法(Forward Algorithm)。在本文将介绍解决HMM另外一个问题 – 解码问题 – 的算法：维特比算法(Viterbi Agorithm)，也属于HMM中的一个基本算法，而且算法本身很像Forward的这个概念，理解起来相对容易。

本文目录：

• Page 1: 前文提要
• Page 2: 一般算法与高效维的特比算法
• Page 3: 实例与伪代码
• Page 4: 参考资料

Last Modified：2010/12/25 16:57 All rights reserved.

前文提要：

在之前的HMM文章中提到，HMM模型将涉及到3个问题：

1. 给定一个观察到得序列O，及参数，求出，即发生这种观察序列的可能性。对应上面例子中，即是我给定一个最终确定了的水果序列S，求我选到这样的水果的可能性。
2. 给定一个观察到的序列O，及参数，求出最有可能产生这种序列的状态序列S。对应上面例子中，即我给定一个最终确定了的水果序列S，求我最可能的选水果筐路径。
3. 同样给定一个观察得到的序列O，求如何调整参数，使最大。

对于问题1，我们已经讨论过Forward Algorithm并成功高效地解决了这个问题。接下来我们将讨论解决平时称为“解码问题”的问题二的解决方法。

在问题二中，对应选水果的例子，我们需要解决的问题是，当我们知道最后选出来的水果序列，以及框选水果(Emission Matrix)、框转框(Transition Matrix)这两个概率，求可能选出这种水果序列的框路径。

* 在讨论这个问题之前，可以先复习一下之前的前向法，因为整体思路跟前向法类似。