Forward-backward algorithm

The Backward algorithm ( also backward algorithm, reverse procedure ) is calculated by means of variables, the backward probability at a given Hidden Markov Model (HMM) to watch a particular symbol sequence. The algorithm uses the method of programming of the dynamic programming.

Markov model

Given a HMM, which

• The amount of the hidden states,
• The alphabet of observable symbols
• The matrix of the transition probabilities,
• The matrix of emission probabilities,
• The initial probability distribution for the possible initial states,

Referred to.

Task & Backward variables

Given a word of Backward algorithm calculates now, so actually making the probability in the existing model observation.

For the backward variables are used, they refer to the probability of observing the suffix if the HMM has been in the state at the time:

Algorithm

The backward variables are determined recursively:

Complexity

The matrix of all backward variables need memory, the intermediate results in the connection no longer be used, then reduced to the space, as only two more columns to the length needed to store the values ​​of and in each recursion.

For each individual variable is summed over rows, so the term is.

Other applications

The backward variables are needed along with the forward variable for the Baum-Welch algorithm for the solution of the given with hidden Markov models, learning problem.

In addition, the knowledge of which allows the determination of the probability for the observation of to have been at a fixed time in the state, because valid according to the Bayesian formula: