向前-向后算法(forward-backward algorithm)

《向前-向后算法(forward-backward algorithm)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、向前-向后算法（forward-backwardalgorithm）本文承接上篇博客《隐马尔可夫模型及的评估和解码问题》，用到的概念和例子都是那里面的。学习问题在HMM模型中，已知隐藏状态的集合S，观察值的集合O，以及一个观察序列（o1,o2,...,on），求使得该观察序列出现的可能性最大的模型参数（包括初始状态概率矩阵π，状态转移矩阵A，发射矩阵B）。这正好就是EM算法要求解的问题：已知一系列的观察值X，在隐含变量Y未知的情况下求最佳参数θ*，使得：在中文词性标注里，根据为训练语料，我们观察到了一系列的词（对应EM中的X），如

2、果每个词的词性（即隐藏状态）也是知道的，那它就不需要用EM来求模型参数θ了，因为Y是已知的，不存在隐含变量了。当没有隐含变量时，直接用maximumlikelihood就可以把模型参数求出来。预备知识首先你得对下面的公式表示认同。以下都是针对相互独立的事件，P(A,B)=P(B

3、A)*P(A)P(A,B,C)=P(C)*P(A,B

4、C)=P(A,C

5、B)*P(B)=P(B,C

6、A)*P(A)P(A,B,C,D)=P(D)*P(A,B

7、D)*P(C

8、A)=P(D)*P(A,B

9、D)*P(C

10、B)P(A,B

11、C)=P(D1,A,B

12、C

13、)+P(D2,A,B

14、C)  D1,D2是事件D的一个全划分理解了上面几个式子，你也就能理解本文中出现的公式是怎么推导出来的了。EM算法求解我们已经知道如果隐含变量Y是已知的，那么求解模型参数直接利用MaximumLikelihood就可以了。EM算法的基本思路是：随机初始化一组参数θ(0)，根据后验概率Pr(Y

15、X;θ)来更新Y的期望E(Y)，然后用E(Y)代替Y求出新的模型参数θ(1)。如此迭代直到θ趋于稳定。在HMM问题中，隐含变量自然就是状态变量，要求状态变量的期望值，其实就是求时刻ti观察到xi时处于状态si的概率，为了

16、求此概率，需要用到向前变量和向后变量。向前变量向前变量 是假定的参数它表示t时刻满足状态，且t时刻之前（包括t时刻）满足给定的观测序列的概率。1.令初始值2.归纳法计算3.最后计算复杂度向后变量向后变量        它表示在时刻t出现状态，且t时刻以后的观察序列满足的概率。1.初始值2.归纳计算E-Step定义变量为t时刻处于状态i，t+1时刻处于状态j的概率。     定义变量表示t时刻呈现状态i的概率。实际上         是从其他所有状态转移到状态i的次数的期望值。是从状态i转移出去的次数的期望值。是从状态i转移到状态j

17、的次数的期望值。M-Step是在初始时刻出现状态i的频率的期望值，是从状态i转移到状态j的次数的期望值 除以  从状态i转移出去的次数的期望值，是在状态j下观察到活动为k的次数的期望值  除以  从其他所有状态转移到状态j的次数的期望值, 然后用新的参数再来计算向前变量、向后变量、和。如此循环迭代，直到前后两次参数的变化量小于某个值为止。下面给出我的java代码：1importjava.io.BufferedReader;2importjava.io.File;3importjava.io.FileReader;4importja

18、va.io.IOException;5importjava.util.Arrays;6importjava.util.HashMap;7importjava.util.LinkedList;8importjava.util.List;9importjava.util.Map;10importjava.util.Map.Entry;1112/**13*隐马尔可夫模型参数学习。14*15*@Author:zhangchaoyang16*@Since:2015年4月4日17*@Version:1.018*/19publicclassHm

19、mLearn{2021privateintstateCount;//状态的个数22privateMapobserveIndexMap=newHashMap();//观察值及其索引编号23/**24*通过学习得到的模型参数25*/26privatedouble[]stateProb;//初始状态概率矩阵27privatedouble[][]stateTrans;//状态转移矩阵28privatedouble[][]emission;//混淆矩阵2930privateLi

20、stobserveSeqs=newLinkedList();//训练集中所有的观察序列3132/**33*迭代终止条件34*/35privatefinalintITERATION_MAX=100;36privatef