隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率

隐马尔科夫模型HMM（一）HMM模型

　　　　隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率

　　　　在隐马尔科夫模型HMM（一）HMM模型中，我们讲到了HMM模型的基础知识和HMM的三个基本问题，本篇我们就关注于HMM第一个基本问题的解决方法，即已知模型和观测序列，求观测序列出现的概率。

1. 回顾HMM问题一：求观测序列的概率

　　　　首先我们回顾下HMM模型的问题一。这个问题是这样的。我们已知HMM模型的参数λ=(A,B,Π)。其中A是隐藏状态转移概率的矩阵，B是观测状态生成概率的矩阵， Π是隐藏状态的初始概率分布。同时我们也已经得到了观测序列O={o1,o2,...oT},现在我们要求观测序列O在模型λ下出现的条件概率P(O|λ)。 　　　　乍一看，这个问题很简单。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。 　　　　我们可以列举出所有可能出现的长度为T的隐藏序列I={i1,i2,...,iT},分布求出这些隐藏序列与观测序列O={o1,o2,...oT}的联合概率分布P(O,I|λ)，这样我们就可以很容易的求出边缘分布P(O|λ)了。 　　　　具体暴力求解的方法是这样的：首先，任意一个隐藏序列I={i1,i2,...,iT}出现的概率是： P(I|λ)=πi1ai1i2ai2i3...aiT−1iT 　　　　对于固定的状态序列I={i1,i2,...,iT}，我们要求的观察序列O={o1,o2,...oT}出现的概率是： P(O|I,λ)=bi1(o1)bi2(o2)...biT(oT) 　　　　则O和I联合出现的概率是： P(O,I|λ)=P(I|λ)P(O|I,λ)=πi1bi1(o1)ai1i2bi2(o2)...aiT−1iTbiT(oT) 　　　　然后求边缘概率分布，即可得到观测序列O在模型λ下出现的条件概率P(O|λ)： P(O|λ)=∑IP(O,I|λ)=∑i1,i2,...iTπi1bi1(o1)ai1i2bi2(o2)...aiT−1iTbiT(oT) 　　　　虽然上述方法有效，但是如果我们的隐藏状态数N非常多的那就麻烦了，此时我们预测状态有NT种组合，算法的时间复杂度是O(TNT)阶的。因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。 　　　　前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。

2. 用前向算法求HMM观测序列的概率

　　　　前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。 　　　　在前向算法中，通过定义“前向概率”来定义动态规划的这个局部状态。什么是前向概率呢, 其实定义很简单：定义时刻t时隐藏状态为qi, 观测状态的序列为o1,o2,...ot的概率为前向概率。记为： αt(i)=P(o1,o2,...ot,it=qi|λ) 　　　　既然是动态规划，我们就要递推了，现在我们假设我们已经找到了在时刻t时各个隐藏状态的前向概率，现在我们需要递推出时刻t+1时各个隐藏状态的前向概率。 　　　　从下图可以看出，我们可以基于时刻t时各个隐藏状态的前向概率，再乘以对应的状态转移概率，即αt(j)aji就是在时刻t观测到o1,o2,...ot，并且时刻t隐藏状态qj, 时刻t+1隐藏状态qi的概率。如果将想下面所有的线对应的概率求和，即∑j=1Nαt(j)aji就是在时刻t观测到o1,o2,...ot，并且时刻t+1隐藏状态qi的概率。继续一步，由于观测状态ot+1只依赖于t+1时刻隐藏状态qi, 这样[∑j=1Nαt(j)aji]bi(ot+1)就是在在时刻t+1观测到o1,o2,...ot，ot+1，并且时刻t+1隐藏状态qi的概率。而这个概率，恰恰就是时刻t+1对应的隐藏状态i的前向概率，这样我们得到了前向概率的递推关系式如下： αt+1(i)=[∑j=1Nαt(j)aji]bi(ot+1)

前向后向算法是前向算法和后向算法的统称，这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。

我们的动态规划从时刻1开始，到时刻T结束，由于αT(i)表示在时刻T观测序列为o1,o2,...oT，并且时刻T隐藏状态qi的概率，我们只要将所有隐藏状态对应的概率相加，即∑i=1NαT(i)就得到了在时刻T观测序列为o1,o2,...oT的概率。 　　　　下面总结下前向算法。 　　　　输入：HMM模型λ=(A,B,Π)，观测序列O=(o1,o2,...oT) 　　　　输出：观测序列概率P(O|λ) 　　　　1) 计算时刻1的各个隐藏状态前向概率： α1(i)=πibi(o1),i=1,2,...N 　　　　2) 递推时刻2,3,...T时刻的前向概率： αt+1(i)=[∑j=1Nαt(j)aji]bi(ot+1),i=1,2,...N 　　　　3) 计算最终结果： P(O|λ)=∑i=1NαT(i) 　　　　从递推公式可以看出，我们的算法时间复杂度是O(TN2)，比暴力解法的时间复杂度O(TNT)少了几个数量级。

3. HMM前向算法求解实例

4. 用后向算法求HMM观测序列的概率

　　　　熟悉了用前向算法求HMM观测序列的概率，现在我们再来看看怎么用后向算法求HMM观测序列的概率。 　　　　后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”，那么后向概率是如何定义的呢？ 　　　　定义时刻t时隐藏状态为qi, 从时刻t+1到最后时刻T的观测状态的序列为ot+1,ot+2,...oT的概率为后向概率。记为： βt(i)=P(ot+1,ot+2,...oT|it=qi,λ) 　　　　后向概率的动态规划递推公式和前向概率是相反的。现在我们假设我们已经找到了在时刻t+1时各个隐藏状态的后向概率βt+1(j)，现在我们需要递推出时刻t时各个隐藏状态的后向概率。如下图，我们可以计算出观测状态的序列为ot+2,ot+3,...oT， t时隐藏状态为qi, 时刻t+1隐藏状态为qj的概率为aijβt+1(j), 接着可以得到观测状态的序列为ot+1,ot+2,...oT， t时隐藏状态为qi, 时刻t+1隐藏状态为qj的概率为aijbj(ot+1)βt+1(j), 则把下面所有线对应的概率加起来，我们可以得到观测状态的序列为ot+1,ot+2,...oT， t时隐藏状态为qi的概率为∑j=1Naijbj(ot+1)βt+1(j)，这个概率即为时刻t的后向概率。

　　　这样我们得到了后向概率的递推关系式如下： βt(i)=∑j=1Naijbj(ot+1)βt+1(j) 　　　　现在我们总结下后向算法的流程,注意下和前向算法的相同点和不同点： 　　　　输入：HMM模型λ=(A,B,Π)，观测序列O=(o1,o2,...oT) 　　　　输出：观测序列概率P(O|λ) 　　　　1) 初始化时刻T的各个隐藏状态后向概率： βT(i)=1,i=1,2,...N 　　　　2) 递推时刻T−1,T−2,...1时刻的后向概率： βt(i)=∑j=1Naijbj(ot+1)βt+1(j),i=1,2,...N 　　　　3) 计算最终结果： P(O|λ)=∑i=1Nπibi(o1)β1(i) 　　　　此时我们的算法时间复杂度仍然是O(TN2)。

5. HMM常用概率的计算

　　　　利用前向概率和后向概率，我们可以计算出HMM中单个状态和两个状态的概率公式。 　　　　1）给定模型λ和观测序列O,在时刻t处于状态qi的概率记为: γt(i)=P(it=qi|O,λ)=P(it=qi,O|λ)P(O|λ) 　　　　利用前向概率和后向概率的定义可知： P(it=qi,O|λ)=αt(i)βt(i) 　　　　于是我们得到： γt(i)=αt(i)βt(i)∑j=1Nαt(j)βt(j) 　　　　2）给定模型λ和观测序列O,在时刻t处于状态qi，且时刻t+1处于状态qj的概率记为: ξt(i,j)=P(it=qi,it+1=qj|O,λ)=P(it=qi,it+1=qj,O|λ)P(O|λ) 　　　　而P(it=qi,it+1=qj,O|λ)可以由前向后向概率来表示为: P(it=qi,it+1=qj,O|λ)=αt(i)aijbj(ot+1)βt+1(j) 　　　　从而最终我们得到ξt(i,j)的表达式如下： ξt(i,j)=αt(i)aijbj(ot+1)βt+1(j)∑r=1N∑s=1Nαt(r)arsbs(ot+1)βt+1(s) 　　　　3) 将γt(i)和ξt(i,j)在各个时刻t求和，可以得到： 　　　　在观测序列O下状态i出现的期望值∑t=1Tγt(i) 　　　　在观测序列O下由状态i转移的期望值∑t=1T−1γt(i) 　　　　在观测序列O下由状态i转移到状态j的期望值∑t=1T−1ξt(i,j) 　　　　上面这些常用的概率值在求解HMM问题二，即求解HMM模型参数的时候需要用到。我们在这个系列的第三篇来讨论求解HMM参数的问题和解法。

（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-ok@163.com）