Viterbi Algorithm

Finding probable states
Definition
Example
Summary
Section 4 - Page 1
1 2

Summary

For a particular HMM, the Viterbi algorithm is used to find the most probable sequence of hidden states given a sequence of observed states. We exploit the time invariance of the probabilities to reduce the complexity of the problem by avoiding the necessity for examining every route through the trellis. The algorithm keeps a backward pointer (f) for each state (t > 1), and stores a probability (d) with each state.

The probability d is the probability of having reached the state following the path indicated by the back pointers.

When the algorithm reaches the states at time, t = T, the d's for the final states are the probabilities of following the optimal (most probable) route to that state. Thus selecting the largest, and using the implied route, provides the best answer to the problem.