前向算法(Forward algorithm),在隐马尔可夫模型(HMM)中,是用于计算“置信状态”的。置信状态指根据既往证据推算出的当前状态的概率分布。这个过程也被叫做“滤波”。前向算法和维特比算法紧密相关但又互不相同。
| 此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (2018年11月18日) |
前向算法是用来解决解码问题的算法之一。自从语音识别技术[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.