Viterbi Algorithm - Algorithm

Algorithm

Suppose we are given a Hidden Markov Model (HMM) with state space, initial probabilities of being in state and transition probabilities of transitioning from state to state . Say we observe outputs . The most likely state sequence that produces the observations is given by the recurrence relations:

\begin{array}{rcl} V_{1,k} &=& \mathrm{P}\big( y_1 \ | \ k \big) \cdot \pi_k \\ V_{t,k} &=& \mathrm{P}\big( y_t \ | \ k \big) \cdot \max_{x \in S} \left( a_{x,k} \cdot V_{t-1,x}\right) \end{array}

Here is the probability of the most probable state sequence responsible for the first observations that has as its final state. The Viterbi path can be retrieved by saving back pointers that remember which state was used in the second equation. Let be the function that returns the value of used to compute if, or if . Then:

\begin{array}{rcl} x_T &=& \arg\max_{x \in S} (V_{T,x}) \\ x_{t-1} &=& \mathrm{Ptr}(x_t,t) \end{array}

Here we're using the standard definition of arg max.
The complexity of this algorithm is .

Read more about this topic:  Viterbi Algorithm