Forward-backward algorithm

The forward-backward algorithm is an inference algorithm for hidden Markov models. Given a sequence of observations, it computes the posterior marginal probability of every hidden state variable, a task usually called smoothing. It relies on dynamic programming and works in two passes over the sequence: a forward pass that computes, for each position, the probability of ending in each state given the observations so far, and a backward pass that computes the probability of the remaining observations from each starting state. Combining the two sets of probabilities, and normalising with Bayes' rule, gives the distribution over states at any point in time given the whole observation sequence. The two passes are also called message passes, a term from belief propagation. The algorithm finds the most likely state at each individual time, but not the most likely sequence of states, which is a job for the Viterbi algorithm. The name is also used for the wider class of algorithms that work on sequence models in a forward and backward manner.