在上一篇文章中留下了个尾巴是关于 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.
岳佳,王士同. 高斯混合模型聚类中 EM 算法及初始化的研究【J】. 微计算 机信息,2006(1lX):244-246.
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 算法的含缺失数据的参数估计【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】. 山东大学学报
来源: https://juejin.im/post/5a576f59f265da3e484bbdf0