The Decoding Problem and the Viterbi Algorithm
Next: The Learning Problem Up: Three basic problems of Previous: The Evaluation Problem and

The Decoding Problem and the Viterbi Algorithm

In this case We want to find the most likely state sequence for a given sequence of observations, and a model,

The solution to this problem depends upon the way ``most likely state sequence'' is defined. One approach is to find the most likely state at t=t and to concatenate all such ' 's. But some times this method does not give a physically meaningful state sequence. Therefore we would go for another method which has no such problems.
In this method, commonly known as Viterbi algorithm, the whole state sequence with the maximum likelihood is found. In order to facilitate the computation we define an auxiliary variable,

which gives the highest probability that partial observation sequence and state sequence up to t=t can have, when the current state is i.
It is easy to observe that the following recursive relationship holds.

where,

So the procedure to find the most likely state sequence starts from calculation of using recursion in 1.8, while always keeping a pointer to the ``winning state'' in the maximum finding operation. Finally the state , is found where

and starting from this state, the sequence of states is back-tracked as the pointer in each state indicates.This gives the required set of states.
This whole algorithm can be interpreted as a search in a graph whose nodes are formed by the states of the HMM in each of the time instant .