五、前向算法（Forward Algorithm）
计算观察序列的概率（Finding the probability of an observed sequence）
2b.计算t=1时的局部概率
‘s
我们按如下公式计算局部概率：
t ( j )= Pr( 观察状态 | 隐藏状态j ) x Pr(t时刻所有指向j状态的路径）
特别当t=1时，没有任何指向当前状态的路径。故t=1时位于当前状态的概率是初始概率，即Pr(state|t=1)=P(state)，因此，t=1时的局部概率等于当前状态的初始概率乘以相关的观察概率：
所以初始时刻状态j的局部概率依赖于此状态的初始概率及相应时刻我们所见的观察概率。
2c.计算t>1时的局部概率‘s
我们再次回顾局部概率的计算公式如下：
t ( j )= Pr( 观察状态 | 隐藏状态j ) x Pr(t时刻所有指向j状态的路径）
我们可以假设（递归地），乘号左边项“Pr( 观察状态 | 隐藏状态j )”已经有了，现在考虑其右边项“Pr(t时刻所有指向j状态的路径）”。
为了计算到达某个状态的所有路径的概率，我们可以计算到达此状态的每条路径的概率并对它们求和，例如：
计算所需要的路径数目随着观察序列的增加而指数级递增，但是t-1时刻‘s给出了所有到达此状态的前一路径概率，因此，我们可以通过t-1时刻的局部概率定义t时刻的‘s，即：
故我们所计算的这个概率等于相应的观察概率（亦即，t+1时在状态j所观察到的符号的概率）与该时刻到达此状态的概率总和——这来自于上一步每一个局部概率的计算结果与相应的状态转移概率乘积后再相加——的乘积。
注意我们已经有了一个仅利用t时刻局部概率计算t+1时刻局部概率的表达式。
现在我们就可以递归地计算给定隐马尔科夫模型(HMM)后一个观察序列的概率了——即通过t=1时刻的局部概率‘s计算t=2时刻的‘s，通过t=2时刻的‘s计算t=3时刻的‘s等等直到t=T。给定隐马尔科夫模型(HMM)的观察序列的概率就等于t=T时刻的局部概率之和。
2d.降低计算复杂度
我们可以比较通过穷举搜索（评估）和通过递归前向算法计算观察序列概率的时间复杂度。
我们有一个长度为T的观察序列O以及一个含有n个隐藏状态的隐马尔科夫模型l=(
,A,B)。
穷举搜索将包括计算所有可能的序列：
公式
对我们所观察到的概率求和——注意其复杂度与T成指数级关系。相反的，使用前向算法我们可以利用上一步计算的信息，相应地，其时间复杂度与T成线性关系。
注：穷举搜索的时间复杂度是
，前向算法的时间复杂度是
，其中T指的是观察序列长度，N指的是隐藏状态数目。
3.总结
我们的目标是计算给定隐马尔科夫模型HMM下的观察序列的概率——Pr(observations |
)。
我们首先通过计算局部概率（‘s）降低计算整个概率的复杂度，局部概率表示的是t时刻到达某个状态s的概率。
t=1时，可以利用初始概率(来自于P向量）和观察概率Pr(observation|state)（来自于混淆矩阵）计算局部概率；而t>1时的局部概率可以利用t-时的局部概率计算。
因此，这个问题是递归定义的，观察序列的概率就是通过依次计算t=1,2,…,T时的局部概率，并且对于t=T时所有局部概率‘s相加得到的。
注意，用这种方式计算观察序列概率的时间复杂度远远小于计算所有序列的概率并对其相加（穷举搜索）的时间复杂度。
未完待续：前向算法3
本文翻译自：http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
部分翻译参考：隐马尔科夫模型HMM自学
转载请注明出处“我爱自然语言处理”：www.52nlp.cn
本文链接地址：http://www.52nlp.cn/hmm-learn-best-practices-five-forward-algorithm-2
相关文章:
个人理解，这里是把需要重复计算的项，存储在了局部概率里，减少了重复计算，是动态规划的思想。
[回复]
admin 回复:
八月 23rd, 2009 at 14:11
是这样的，前向算法和维特比算法都利用了动态规划的思想。
[回复]
‘现在我们就可以递归地计算给定隐马尔科夫模型(HMM)后一个观察序列的概率了——即通过t=1时刻的局部概率’s计算t=2时刻的’s，通过t=2时刻的’s计算t=3时刻的’s等等直到t=T。给定隐马尔科夫模型(HMM)的观察序列的概率就等于t=T时刻的局部概率之和。’
你翻译的文章很好，我把原文也看过了。收获很大。
但是有一个问题就是：为什么’给定隐马尔科夫模型(HMM)的观察序列的概率就等于t=T时刻的局部概率之和‘？
我的理解是：整个观察序列的概率等于：每个observation的概率的乘积，也就是：
P(dry)*P(soggy)*P(damp).
但是t=T时刻的局部概率只求出了P(damp)啊，还需要再乘以t=1和t=2时的P(dry)和P(soggy)才是整个观察序列的概率。这里一直比较迷惑，希望得到解答，谢谢！
我对文章的理解是：在求T时刻的局部概率alfa（T）时，已经包含了t=1和t=2时的P(dry)，P(soggy)，所以不用再乘了。但是感觉中间又少了些东西。
[回复]
52nlp 回复:
十一月 28th, 2009 at 12:45
首先，你的理解“整个观察序列的概率等于：每个observation的概率的乘积，也就是：
P(dry)*P(soggy)*P(damp)”是有问题的。如果给定了隐藏状态的序列，譬如“sunny,sunny,sunny”，那么观察序列的概率可以等于Pr(dry,damp,soggy | sunny,sunny,sunny),根据独立性假设，可以等价于“B(dry|sunny)*B(damp|sunny)*B(soggy|sunny)”，但是当前的隐藏状态序列是不可知的，所以必须穷举出所有的隐藏状态序列，计算给出的观察序列的概率，并对其求和，也就是：
Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)
有27种情况，但是需要注意的是，这个计算过程中除了有上述观察概率的相乘外，还要考虑隐藏状态之间的转移概率，因为隐藏状态之间的转移是不确定的。
还是拿例子说吧，最后一个时刻的局部概率有三个:当隐藏状态为sunny时，局部概率为Pr(dry,damp,soggy|.,.,sunny)；为cloudy时，局部概率为Pr(dry,damp,soggy|.,.,cloudy)；同理，第三个局部概率为(dry,damp,soggy|.,.,rainy)。
其中“.,.”代表的是任意两个隐藏状态之间的组合(3*3)，每个局部概率已经计算好了总的27种情况中的9种情况，所以它们之和就是所有可以穷举的27中情况。
估计你的理解中没有考虑到每种情况计算概率后还有求和，所以觉得其中缺了什么吧！
[回复]
多谢回答！
感觉关键是hidden的state对observation的决定作用没有理解好。这下明白了
[回复]
52nlp 回复:
十二月 1st, 2009 at 07:32
不客气，欢迎多来走走！
[回复]