Forward–backward algorithm: Difference between revisions

Revision as of 10:58, 31 May 2011

Revision as of 09:43, 2 August 2011

Line 1:

{{Mergefrom|BCJR algorithm|discuss=Talk:Forward-backward algorithm#Merger proposal|date=June 2009}}

{{Mergefrom|Forward algorithm|date=April 2010}}

The '''forward-backward algorithm''' is an [[inference]] [[algorithm]] for [[hidden Markov models]] which computes the [[posterior probability|posterior]] [[marginal probability|marginals]] of all hidden state variables given a sequence of observations/emissions <math>o_{1:t}:= o_1,\dots,o_t</math>, i.e. it computes, for all hidden state variables <math>X_k \in \{X_1, \dots, X_t\}</math>, the distribution <math>P(X_k\ |\ o_{1:t})</math>. This inference task is usually called ''smoothing''. The algorithm makes use of the principle of [[dynamic programming]] to efficiently compute the values that are required to obtain the posterior marginal distributions in two passes. The first pass goes forward in time while the second goes backward in time; hence the name ''forward-backward algorithm''.