七、前向-后向算法(Forward-backward algorithm)
上一节我们定义了两个变量及相应的期望值，本节我们利用这两个变量及其期望值来重新估计隐马尔科夫模型（HMM）的参数
如果我们定义当前的HMM模型为
，那么可以利用该模型计算上面三个式子的右端；我们再定义重新估计的HMM模型为
，那么上面三个式子的左端就是重估的HMM模型参数。Baum及他的同事在70年代证明了
因此如果我们迭代地的计算上面三个式子，由此不断地重新估计HMM的参数，那么在多次迭代后可以得到的HMM模型的一个最大似然估计。不过需要注意的是，前向-后向算法所得的这个结果（最大似然估计）是一个局部最优解。
关于前向-后向算法和EM算法的具体关系的解释，大家可以参考HMM经典论文《A tutorial on Hidden Markov Models and selected applications in speech recognition》，这里就不详述了。下面我们给出UMDHMM中的前向-后向算法示例，这个算法比较复杂，这里只取主函数，其中所引用的函数大家如果感兴趣的话可以自行参考UMDHMM。
前向-后向算法程序示例如下（在baum.c中):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | void BaumWelch(HMM *phmm, int T, int *O, double **alpha, double **beta, double **gamma, int *pniter, double *plogprobinit, double *plogprobfinal) { int i, j, k; int t, l = 0; double logprobf, logprobb, threshold; double numeratorA, denominatorA; double numeratorB, denominatorB; double ***xi, *scale; double delta, deltaprev, logprobprev; deltaprev = 10e-70; xi = AllocXi(T, phmm->N); scale = dvector(1, T); ForwardWithScale(phmm, T, O, alpha, scale, &logprobf); *plogprobinit = logprobf; /* log P(O |intial model) */ BackwardWithScale(phmm, T, O, beta, scale, &logprobb); ComputeGamma(phmm, T, alpha, beta, gamma); ComputeXi(phmm, T, O, alpha, beta, xi); logprobprev = logprobf; do { /* reestimate frequency of state i in time t=1 */ for (i = 1; i <= phmm->N; i++) phmm->pi[i] = .001 + .999*gamma[1][i]; /* reestimate transition matrix and symbol prob in each state */ for (i = 1; i <= phmm->N; i++) { denominatorA = 0.0; for (t = 1; t <= T - 1; t++) denominatorA += gamma[t][i]; for (j = 1; j <= phmm->N; j++) { numeratorA = 0.0; for (t = 1; t <= T - 1; t++) numeratorA += xi[t][i][j]; phmm->A[i][j] = .001 + .999*numeratorA/denominatorA; } denominatorB = denominatorA + gamma[T][i]; for (k = 1; k <= phmm->M; k++) { numeratorB = 0.0; for (t = 1; t <= T; t++) { if (O[t] == k) numeratorB += gamma[t][i]; } phmm->B[i][k] = .001 + .999*numeratorB/denominatorB; } } ForwardWithScale(phmm, T, O, alpha, scale, &logprobf); BackwardWithScale(phmm, T, O, beta, scale, &logprobb); ComputeGamma(phmm, T, alpha, beta, gamma); ComputeXi(phmm, T, O, alpha, beta, xi); /* compute difference between log probability of two iterations */ delta = logprobf - logprobprev; logprobprev = logprobf; l++; } while (delta > DELTA); /* if log probability does not change much, exit */ *pniter = l; *plogprobfinal = logprobf; /* log P(O|estimated model) */ FreeXi(xi, T, phmm->N); free_dvector(scale, 1, T); } |
前向-后向算法就到此为止了。
未完待续：总结
注：原创文章，转载请注明出处“我爱自然语言处理”：www.52nlp.cn
本文链接地址：http://www.52nlp.cn/hmm-learn-best-practices-seven-forward-backward-algorithm-5
相关文章:
很是好啊,谢谢楼主的分享,
[回复]
欢迎常来看看！
[回复]
楼主，你好。用Baum-welch算法来训练HMM模型时，只用输入隐藏状态的个数，观察向量的个数，观察序列，我有个几个疑问：
1.单单靠这些，怎么来评估这个参数模型就是最优的？因为我用这个算法测试的时候，每次迭代次说都是1.
2.
现在我想利用HMM来做人体行为识别，我有一个基本行为库，其中包括三个行为（也就是隐藏状态）：walk，run，jump；库中包括的是人体不同行为的轮廓，每个行为对应8个观察向量，也就是说此模型总共观察向量有32个。我该怎么训练HMM呢
[回复]
52nlp 回复:
十二月 1st, 2009 at 21:10
不好意思，晚上回来的比较迟。
首先用Baum-welch算法来训练HMM模型本身得到的解是局部最优，而全局最优解。另外，只给出这几个条件用这个算法进行无监督训练的HMM模型效果应该很差。
举个例子，在实际的词性标注应用中，也会辅之以词典词性信息或者词类信息才能得到一个相对较好的HMM词性标注模型。但就是这样，也没有从一个已经做好标注的小语料库中直接得到的HMM模型的准确率高。
所以对于你的第2个问题，最好的方法是你能建立一个与实际问题相对应的训练集，譬如：
O1/walk O2/jump O3/run O4/run ...
....
其中Oi是观察向量，从这样的训练集中直接计算生成一个HMM模型的效果估计会比利用Baum-welch算法来训练HMM模型好很多。
[回复]
jumay 回复:
十二月 1st, 2009 at 21:26
谢谢你！O(∩_∩)O~ 我再考虑一下
[回复]
你好，楼主，我有一个问题：用上述bw算法来训练HMM的时候，按理说迭代次数是不同的，但是不管我的输入观察序列是多少，迭代次数都是1.为什么会这样
[回复]
52nlp 回复:
十二月 1st, 2009 at 21:16
没有仔细考虑这个问题，估计输入序列可能过短，可以试着用100长以上的序列试一下。不太清楚原因，在我讲的《HMM在自然语言处理中的应用一：词性标注3》中训练序列的长度是590。
另外，觉得在umdhmm中直接使用Baum-welch算法来训练HMM模型只适用于教学举例，真正的应用中如果没有很好的训练集也应该辅之以一些辅助信息。
[回复]
jumay 回复:
十二月 1st, 2009 at 21:54
你好！谢谢你的答复。这个地方还是不太理解，即便是我辅助的有观察值对应的隐藏状态，比如说0/walk 2/walk 3/walk 8/run 9/run 10/run ，该怎么利用这些参数和bw算法进行有监督的训练呢
[回复]
52nlp 回复:
十二月 1st, 2009 at 22:59
这个可以参考“HMM在自然语言处理中的应用一：词性标注5”，直接计算HMM的各个参数值就可了。
博主，我一直没看懂baum-welch算法，即使是看着umdhmm的代码，博主提到的《A tutorial on Hidden Markov Models and selected applications in speech recognition》，是L.R.Rabiner的那一篇吗？
我想应用hmm识别到图像匹配中去，训练时效果很差，所以想仔细理解一下训练用的算法。
[回复]
52nlp 回复:
十月 10th, 2010 at 00:10
是这一篇论文，建议好好读读英文原始文献，我这里翻译的比较粗糙。
另外除了多花一点时间琢磨这个算法外，所需要的一些基本数学知识也要了解一下。
[回复]
博主你好，我有几个问题想向你请教，希望你给予指点，先谢谢了。
1.我现在在做中文语料的词性标注，首先要用EM算法来估计AB矩阵，
所以我要用到前后向算法，但是一次前后向算法之后，得到的两个前后向矩阵
均溢出！（前后向算法就会溢出）；
2.关于EM算法初始值的选择，我怎样才能尽可能选择好的初始值呢？
[回复]
Beingspider 回复:
十二月 24th, 2010 at 21:58
第一个问题已经解决，我找了资料第二个问题主要是对B(发射概率)的初始化。博主有没有好的建议？或者能给我提供些关于K均值分割算法的资料，谢谢了。
[回复]
52nlp 回复:
十二月 24th, 2010 at 23:05
非常抱歉，这方面我没有什么经验，也没有这方面的资料！
[回复]
Beingspider 回复:
十二月 25th, 2010 at 10:51
呵呵，没事。还是要谢谢你。
在前向算法与后向算法中都分别有带WithScale的函数；比如在backward.c 中有两个函数，一个是Backward()一个是BackwardWithScale()，请问后者有什么用。本人比较菜，望博主能指点一二。谢谢
[回复]
52nlp 回复:
四月 10th, 2011 at 17:50
从代码中看scale一个比例因子数组，它是对前向算法和后向算法每一轮的中间结果进行按比例修正的，至于为什么这样做，我也不是很清楚，抱歉！
[回复]
请问WithScale是什么意思，有什么用 回复:
四月 10th, 2011 at 20:55
Thank you anyway
[回复]
此代码在模型参数调整中存在错误。我在改写的C#代码里修正了此错误。
详见：http://blog.csdn.net/jhqin/archive/2011/06/09/6534916.aspx
[回复]
52nlp 回复:
六月 10th, 2011 at 13:08
谢谢指正！
[回复]