隐马尔科夫模型HMM自学（4-2）Forward Algorithm

来源：百度文库编辑：神马文学网时间：2024/04/28 00:48:54

崔晓源翻译
书接上文，前一话我们讲到了Forward Algorithm中初始状态的部分概率的计算方法。这次我们继续介绍。
2c.如何计算t>1时刻的部分概率
回忆一下我们如何计算部分概率：

t ( j )= Pr( observation | hidden state is j ) * Pr(all paths to state j at time t)
我们可知（通过递归）乘积中第一项是可用的。那么如何得到Pr(all paths to state j at time t) 呢？
为了计算到达一个状态的所有路径的概率，就等于每一个到达这个状态的路径之和：

随着序列数的增长，所要计算的路径数呈指数增长。但是在t时刻我们已经计算出所有到达某一状态的部分概率，因此在计算t+1时刻的某一状态的部分概率时只和t时刻有关。

这个式子的含义就是恰当的观察概率（状态j下，时刻t+1所真正看到的观察状态的概率）乘以此时所有到达该状态的概率和（前一时刻所有状态的概率与相应的转移概率的积）。因此，我们说在计算t+1时刻的概率时，只用到了t时刻的概率。这样我们就可以计算出整个观察序列的概率。
2d.复杂度比较
对于观察序列长度T，穷举法的复杂度为T的指数级；而Forward Algorithm的复杂度为T的线性。
=======================================================
最后我们给出Forward Algorithm的完整定义
We use the forward algorithm to calculate the probability of a T long observation sequence;

where each of the y is one of the observable set. Intermediate probabilities (

‘s) are calculated recursively by first calculating

for all states at t=1.

Then for each time step, t = 2, ..., T, the partial probability

is calculated for each state;

that is, the product of the appropriate observation probability and the sum over all possible routes to that state, exploiting recursion by knowing these values already for the previous time step. Finally the sum of all partial probabilities gives the probability of the observation, given the HMM,

=======================================================
我们还用天气的例子来说明如何计算t=2时刻，状态CLOUDY的部分概率

怎么样？看到这里豁然开朗了吧。要是还不明白，我就.....................还有办法，看个动画效果：
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg3.html
参数定义：
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg4.html
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg5.html
最后记住我们使用这个算法的目的（没有应用任何算法都是垃圾），从若干个HMM模型中选出一个最能够体现给定的观察状态序列的模型（概率最大的那个）。
Forward Algorithm （Done）
http://blogcui.spaces.live.com/blog/cns!46BDB23E24219CE9!152.entry?_c=BlogPart

隐马尔科夫模型HMM自学（4-2）Forward Algorithm 隐马尔科夫模型HMM自学（4-1）Forward Algorithm 隐马尔科夫模型HMM自学（5-2）Viterbi Algorithm 隐马尔科夫模型HMM自学（5-1）Viterbi Algorithm 隐马尔科夫模型HMM自学（2）隐马尔科夫模型HMM自学隐马尔科夫模型HMM自学（1）隐马尔科夫模型HMM自学（3）隐马尔科夫模型HMM自学（6）尾声隐马尔科夫模型HMM自学（1）隐马尔科夫模型HMM（2）隐马尔科夫模型HMM（1）隐马尔科夫模型HMM 隐马尔可夫(HMM)模型的各种语言实现基因算法源码2(Geneic Algorithm) [Forward]静态时序分析（Static?Timing?Analysis）211111 Approximation algorithm 自学资料（Excel VBA）[收集整理4] 自学资料（Excel VBA）[收集整理4] 自学资料（Excel VBA）[收集整理4] 自学资料（Excel VBA）[收集整理2] 自学资料（Excel VBA100）[收集整理2] 自学资料（Excel VBA）[收集整理2] 谈中医自学方法2

隐马尔科夫模型HMM自学 （4-2）Forward Algorithm

隐马尔科夫模型HMM自学（4-2）Forward Algorithm