查看“︁前向算法”︁的源代码

{{expert|time=2018-11-18T05:29:51+00:00}}
{{noteTA
|T=zh-cn:前向算法; zh-tw:前向式演算法;
|G1=Math
|G2=IT
|1=zh-cn:前向算法; zh-tw:前向式演算法;
}}
'''前向算法'''（{{lang|en|Forward algorithm}}），在[[隐马尔可夫模型]]（HMM）中，是用于计算“置信状态”的。置信状态指根据既往证据推算出的当前状态的概率分布。这个过程也被叫做“滤波”。前向算法和[[维特比算法]]紧密相关但又互不相同。

==发展历史==
前向算法是用来解决解码问题的算法之一。自从语音识别技术<ref name="speechRecognition">[[Lawrence Rabiner|Lawrence R. Rabiner]], "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition". ''Proceedings of the [[IEEE]]'', 77 (2), p.&nbsp;257–286, February 1989. [https://dx.doi.org/10.1109/5.18626 10.1109/5.18626]</ref>和模式识别技术发展以来，它也越来越普遍地被用在像[[计算生物学]]<ref name="bio">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.</ref>这样的使用HMM的领域内。

==算法==
整个算法的目标是计算[[联合概率分布]] <math>p(x_t,y_{1:t})</math>。为了方便，我们把 <math>x(t)</math> 简写做 <math>x_t</math>，将 <math>(y(1), y(2), ..., y(t))</math> 简写做 <math>y_{1:t}</math>。直接计算<math>p(x_t,y_{1:t})</math>则需要计算所有状态序列 <math>\{x_{1:t-1}\}</math> 的[[边缘分布]]，而它的数量和 <math>t</math> 成指数相关。使用这一算法，我们可以利用HMM的[[条件独立]]性质，[[递归]]地进行计算。

我们令

::<math>\alpha_t(x_t) = p(x_t,y_{1:t}) = \sum_{x_{t-1}}p(x_t,x_{t-1},y_{1:t})</math>.

利用[[链式法则 (概率)|链式法则]]来展开<math>p(x_t,x_{t-1},y_{1:t})</math>，我们可以得到

::<math>\alpha_t(x_t) = \sum_{x_{t-1}}p(y_t|x_t,x_{t-1},y_{1:t-1})p(x_t|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})</math>.

由于 <math>y_t</math> 和除了 <math>x_t</math> 之外的一切都条件独立，而 <math>x_t</math> 又和 <math>x_{t-1}</math> 之外的一切都条件独立，因此

::<math>\alpha_t(x_t) = p(y_t|x_t)\sum_{x_{t-1}}p(x_t|x_{t-1})\alpha_{t-1}(x_{t-1})</math>.

这样，由于 <math>p(y_t|x_t)</math> 和 <math>p(x_t|x_{t-1})</math> 由HMM的[[隐马尔可夫模型#使用隐马尔可夫模型|输出概率]]和[[隐马尔可夫模型#使用隐马尔可夫模型|状态转移概率]]我们可以很快计算用 <math>\alpha_{t-1}(x_{t-1})</math> 计算出<math>\alpha_t(x_t)</math>，并且可以避免递归计算。

前向算法可以很容易地被修改来适应其他的HMM变种，比如[[马尔可夫跳跃线性系统]]。

==平滑处理==
为了能够使用“未来的历史”（比如我们在试图预测过去的某个时点的状态），我们可以运行后向算法，它是前向算法的一个补充。这一操作被称为平滑{{why|date=2015年3月}}。 [[前向-后向算法]]对 <math>1<k<t</math> 计算 <math>P(x_k | y_{1:t} )</math>，因此使用了过去和未来的全部信息。

==解码算法==
为了解码最可能的序列，需要使用[[维特比算法]]。它会从过去的观测中试图推测最可能的状态序列，也即使 <math>P(x_{0:t}|y_{0:t})</math> 最大化的状态序列。

==参考文献==
{{reflist|1|refs=}}

[[Category:马尔可夫模型]]