HMM学习笔记_3(从一个实例中学习Viterbi算法)

在上一篇博客 http://www.cnblogs.com/tornadomeet/archive/2012/03/24/2415583.html中，我们已经从一个例子中学会了HMM的前向算法，解决了HMM算法的第一个问题，即模型评估问题。这一讲中我们来解决第二个问题：HMM的解码问题，即即给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样寻找满足这种观察序列意义上最优的隐含状态序列S，这一步中最常用的算法就是Viterbi算法了。

同样的，我们先引入3个符合：

：表示在观察时刻t正处在状态j，且沿一条路径q1q2q3..qt，产生出的o1o2o3…ot最大概率。

：表示的是一个状态值，该状态值产生了上面的 ，也就是说计算时是由上一次那个状态产生的。

：表示在观察时刻t中所有的内最大的那个状态，所以它也是一个状态值。

由上面的解释可以得出这3个符合的数学表达式如下：

所有说当已知观察序列，要用viterbi算法求解最优状态序列时与前面一讲中的求最大观察值概率的算法非常相似。只是在求 时不再是将其来源相加，而是取其中最大的那个。

废话少说，还是看刚开始的那个题目：

HMM模型如下，试通过前向算法计算产生观察符号序列O={ABAB}时用Viterbi算法求出最大可能的状态序列。

当然初始概率矩阵π=(1,0,0),即开始处于状态1。按照上面的公式理论，我们的递推依次解出，以及。解法如下：

第一次观察时：

第二次观察时：

第三次观察时：

第四次观察时：

其递推结果为：

所以最后的结果状态序列为s1、s2、s2、s2.

其计算结果示意图如下所示：

浅绿色的箭头表示最有可能的状态序列。写得比较乱，大家随便凑合着看。