Forward–backward algorithm

The forward-backward algorithm is a dynamic programming algorithm for computing the probability of a particular output sequence, given the parameters of the model, in the context of hidden Markov models.

A brute force procedure for the solution of this problem is the generation of all possible sequences of observed events and hidden states with their probabilities using the two transition matrices. The joint probability of two sequences, given the model, is calculated by multiplying the corresponding probabilities. This procedure has a time complexity of $O(2\cdot T\cdot N^{T})$, where $T$ is the length of sequences and $N$ is the number of symbols in the state alphabet. This is intractable for realistic problems, as the number of possible hidden node sequences typically is extremely high.

... to be continued

See also

• Baum Welch algorithm
• Hidden Markov model
• Viterbi algorithm

References

• Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.
• Rabiner L. R., Juang B. H. (1986). "An introduction to hidden Markov models". IEEE ASSP Magazine: 4–15. {{cite journal}}: Unknown parameter |month= ignored (help)
• Charniak Eugene (1993). Statistical Language Learning. MIT Press. ISDN 978-0-262-53141-2. {{cite book}}: Unknown parameter |address= ignored (|location= suggested) (help)

External links

• Tutorial of Hidden Markov Models including the forward-backward algorithm