Forward–backward algorithm: Difference between revisions

Revision as of 18:46, 1 April 2008

Revision as of 16:23, 27 April 2008

Line 1:

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 model]]s.

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. ThisThe brute force procedure has a [[time complexity]] of <math> O(2\cdot T \cdot N^T) </math>, where <math>T</math> is the length of sequences and <math>N</math> 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. The forward-backward algorithm has time complexity <math> O(N^2 T)\, </math>.

==See also==