前向算法
此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (2018年11月18日) |
前向算法(Forward algorithm),在隐马尔可夫模型(HMM)中,是用于计算“置信状态”的。置信状态指根据既往证据推算出的当前状态的概率分布。这个过程也被叫做“滤波”。前向算法和维特比算法紧密相关但又互不相同。
发展历史
前向算法是用来解决解码问题的算法之一。自从语音识别技术[1]和模式识别技术发展以来,它也越来越普遍地被用在像计算生物学[2]这样的使用HMM的领域内。
算法
整个算法的目标是计算联合概率分布 。为了方便,我们把 简写做 ,将 简写做 。直接计算 则需要计算所有状态序列 的边缘分布,而它的数量和 成指数相关。使用这一算法,我们可以利用HMM的条件独立性质,递归地进行计算。
我们令
- .
利用链式法则来展开 ,我们可以得到
- .
由于 和除了 之外的一切都条件独立,而 又和 之外的一切都条件独立,因此
- .
这样,由于 和 由HMM的输出概率和状态转移概率我们可以很快计算用 计算出 ,并且可以避免递归计算。
前向算法可以很容易地被修改来适应其他的HMM变种,比如马尔可夫跳跃线性系统。
平滑处理
为了能够使用“未来的历史”(比如我们在试图预测过去的某个时点的状态),我们可以运行后向算法,它是前向算法的一个补充。这一操作被称为平滑[为何?]。 前向-后向算法对 计算 ,因此使用了过去和未来的全部信息。
解码算法
为了解码最可能的序列,需要使用维特比算法。它会从过去的观测中试图推测最可能的状态序列,也即使 最大化的状态序列。
参考文献
- ^ Lawrence R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition". Proceedings of the IEEE, 77 (2), p. 257–286, February 1989. 10.1109/5.18626
- ^ Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison, "Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids". Cambridge University Press, 1999, ISBN 0521629713.