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算法的极大似然参数估计[J].河南大学学 报:自然科学版,2002,32(4):35-41.

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

算法channel使用指南(V2.0)

01 引言 欢迎关注 算法channel ! 交流思想,分享知识,找到迈入机器学习大门的系统学习方法,并在这条道路上不断攀登,这是小编创办本公众号的初衷。 本...

36880
来自专栏算法channel

基本算法|图解各种树(二)

01 — 二叉搜索树 基本算法|图解各种树(一) 二叉搜索树,又称为二叉排序树,简写为 BST,它与线性表,链表,二叉树间的关系,二维链表近似是二叉树,BST继...

31250
来自专栏算法channel

算法channel关键词和文章索引

希望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1Tags 排序算法 链表 树 图 动态规划 ...

35850
来自专栏算法channel

图算法|Dijkstra算法python实现

01 — Dijkstra算法的理论部分 关于Dijkstra算法的原理部分,请参考之前的推送: 图算法|Dijkstra最短路径算法 Dijkstra算法总...

78560
来自专栏互联网杂技

各厂算法原理

豆瓣:我买了俩馒头,问我,你要不要来碗米饭? 淘宝:我吃完俩馒头,问我,你要不要来俩馒头? 百度:“老板,给我俩馒头”—“湖南株洲馒头机制造厂供应优质馒头机” ...

35150
来自专栏智能算法

FASTN如何快速的检测出角点

1. FASTN算法的动机 大部分特征检测算法的效果较好,但是达不到实时,因此提出FAST (Features from Accelerated Segment...

35170
来自专栏智能算法

听你说话 机器学习算法就能检测抑郁症了

抑郁症越来越变成一个常见词,很多普通人心情不好时就称自己得了抑郁症。不过即便对医生来说,诊断也不是件容易的事。而南加州大学的研究人员开发出的机器学习工具,或许...

31830
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

1.6K70
来自专栏算法channel

图算法|Dijkstra最短路径算法

01 — 单源最短路径 首先解释什么是单源最短路径,所谓单源最短路径就是指定一个出发顶点,计算从该源点出发到其他所有顶点的最短路径。如下图所示,如果源点设为A,...

99950
来自专栏智能算法

身份证号码验证算法

来自:旭东的博客 - 博客园 链接:http://www.cnblogs.com/xudong-bupt/p/3293838.html(点击尾部阅读原文前往) ...

49550

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励