Forward algorithm

The forward algorithm (including the forward algorithm, the forward procedure ) is calculated with the aid of so-called forward - variables for a given hidden Markov model, the probability of a given observation. He uses the programming method of dynamic programming.

Markov model

The Markov model is defined as wherein

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

Referred to.

Task & Forward variables

Given a word the Forward algorithm calculates now, so actually to make the probability of the observation in the existing model.

For the forward variables are used, it is the probability to have observed at the time the prefix and be stored in the state:

Operation

The forward variables, and hence the overall probability can be calculated recursively:

Complexity

The algorithm requires surgery and provides an efficient method of calculating the probability value. The memory requirement is because to achieve the polynomial term, all are stored in a matrix.

If the intermediate results are not needed by for after the end of the recursion, then reduces to the memory requirements, as two column vectors of length sufficient to and store in each recursion.

Other applications

The forward variables are needed together with the backward variables 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 of observing to have been at a fixed time in the state, as is true according to the Bayes formula: