EM算法学习(番外篇):HMM的参数估计

在上一篇文章中留下了个尾巴是关于EM算法在HMM隐马尔可夫模型的参数估计拓展上的应用.在学习EM算法以后,我们再去学习HMM的Baum-Weich算法就会相对的非常容易,Baum-Weich不过是EM算法的一种特例而已,这个算法是1972年提出的,Baum-Weich的出现甚至是早于EM算法的,这两者的关系有兴趣的同学.可以看看Satistical Methodsfor Speech Recognition,这里边对于Baum- Welch和EM的关系有很完整的描述.

一:HMM的定义

隐马尔科夫模型实际上是一个双重的随机过程,其中一重随机过程不能直接被观测到,通过状态转移概率矩阵描述,另一重随机过程输出可以观测的观测符号,这个是由输出的概率来进行定义的.隐马尔科夫的模型的参数”入”可以表示为一个五元组:

1;S是一组状态的集合,S={1,2,.....N},而随机序列X在t时刻所处的状态为q(t),并且q(t)属于S.

2:V是一组输出符号组成的集合,V={v1,v2,........,v(m)},而观测序列o(t)属于{v1,v2,........,v(m)},并且t在[1,T]之间.

3:B=bj(k)是输出符号的概率分布

bj(k)表示在状态j时输出符号v(k)的概率,即bj(k)=P(vk | j),k属于[1,M],j属于[1,N]

4:π=π(i)是初始概率分布,其中π = P(q1 = i)表示在时刻1时选择状态i的概率.

二:HMM研究的三个问题

1:估算问题:

在给定HMM的参数(S V A B π)和观测序列O = (o1,o2,…..oT)的情况下,如何有效的计算出观测序列的概率,即P(O | 入)?

2:解码问题

在给定HMM的参数(S V A B π)和观测序列O = (o1,o2,…..oT)的情况下,如何寻找一个状态转换序列q = (q1,q2,…..qT),使得该状态转换序列最有可能产生上述观测序列?

3:学习问题

在模型参数未知或者不准确的情况下,如何根据观测序列O = (o1,o2,…..oT)得到模型参数或者是调整模型参数,即如何确定一组模型参数’入*’使得P(O | 入*)达到最大?

解决思路:

第一个问题可以用向前或者是向后算法解决

第二个问题可以用Viterbi算法解决

上述两个问题不再赘述

第三个问题:使用Baum-Welch(EM算法)来去解决HMM的第三个问题

三:Baum-Welch算法的原理和步骤

根据EM算法的基本思路:随机初始化一组参数0(o),然后根据后验概率模型P(Y | X,0(0) )来更新隐含变量Y的期望E(Y),然后用E(Y)代替Y求出新的模型参数0(1),就这样迭代直到0趋于稳定就可以.

对于HMM的第三个问题(学习问题),隐含变量自然就是状态的变量,要求状态变量的期望值实际上就是求在t时刻随机变量X所处状态qt = i的概率,为了求这个概率,我们引入了向前变量和向后变量.

1:向前变量:

αt(i) = P(01,02,03,……0t,qt = i | 入),即给定模型参数”入”,在给定时间t的前提下,处在状态i并且观测序列为o1,o2,......ot的概率,那么显然有:

2:向后向量

βt(i) = P(o(t+1),o(t+2),…….o(T) | qt = i, 入).即给定模型参数入,在时刻t,处在状态i并且观测序列为o(t+1),o(t+2),…….o(T) 的概率,那么显然有:

3:E步

首先定义变量:

即给定参数模型”入”,和观测序列O,在时刻t处在状态i且时刻为t+1处在状态为j的概率.进一步的话,可以写成:

其次,定义变量:

表示的是在给定模型参数和观测序列的前提下,t时刻处在状态i的概率.

那么将t带入上式,就有表示为状态i转移出去的次数的期望值,后部分表示为从状态i到状态j的次数的期望值.

4:M步

π(i)是表示在初始时刻出现状态i的频率的期望值,即有:

则同理可得:

a(i,j)表示的是从状态i到状态j的次数的期望值除以从状态i转移出去的次数的期望值,既有:

bj(k)是在状态为j的情况下观察到输出值为k的次数的期望值除以其他所有状态转移到状态j的次数的期望值,即有:

并且有:

这样就引入新的参数λ = (A,B,π)再来计算向前变量at(i),向后变量Bt(i),ξ(i,j),然后这样如此的循环迭代,直到前后两次参数的变化量小于某个值为止.

5:算法的实现:

在这个部分,引用上边的Baum-Welch算法,来做一个关于HMM的参数估计的例子.

现在假设一个HMM的模型的参数结构是(S V A B π),其中S={1,2,3},V={1,2},π = (0,1,0),A,B如图:

我们首先由这个HMM模型生成20个观测值作为O:

O = (1,2,1,2,1,2,1,2,1,1,1,1,12,1,2,1,2,1,2)

然后根据上边的公式得到,可以进行更新,然后用这个20个的观测值来去训练模型然后进行参数估计,估计结果如下:

通过比较真正的参数和估计的参数,效果还是可以的,但是这还不够,为了进一步的提高估计的精确率,我们增加观测值,这一次我们用1000个观测值,反正都是随机生成的,训练下参数,结果如下:

效果还不错的,所以根据结果可以看见,增加样本训练量真的可以提高参数估计的精度,并且增加样本数还可以减少迭代的次数,这个算法还是很有效的.

好的,在完成这个以后,这个EM算法的系列就彻底结束了,也希望小伙伴们可以多多指教,感激不尽.

参考资料:

Little R J A，Rubin D B.Statistical Analysis with Missing Data[M】.New York:Wiley and Sons，Inc.1987.

Zhao Z，Huang B，Liu F.Parameter estimation in batch process using EM

algorithm with particle filter[J].Computers&Chemical Engineering，2013， 57:159-172.bibitembibl4 Delyon B，Lavielle M，Moulines E.Convergence of a stochastic approximation version of the EM algorithm[J]。Annals of Statistics，1999:94-128.

岳佳，王士同.高斯混合模型聚类中EM算法及初始化的研究【J】.微计算 机信息，2006(1lX):244-246.

陈婷。基于EM算法的含缺失数据的参数估计【D】.大连理工大学，2008.

孙大飞，刘文举.基于EM算法的极大似然参数估iJ-!屎iff[J].河南大学学 报:自然科学版，2002，32(4):35-41.

孟丽新，刘洪.基于EM算法约束条件下参数的估计【J】.东北师大学报: 自然科学版，2009，40(4):28-32.

罗季.Monte Carlo EM加速算法【J】.应用概率统计，2008，24(3):311—318.

张宏东 EM算法及应用【J】.山东大学学报