Viterbi Algorithm

#maths Given a Hidden Markov Model with known parameters, we can deduct the most likely sequence of hidden states given a sequence of observation. The Viterbi algorithm gives us a sequence while the forward algorithm gives us a probability. The Viterbi algorithm is similar to the forward algorithm where instead of summing the likelihoods, we take the max. We can write it as the following:

$$\begin{array}{rlr}\text{Initialization:}& {\alpha }_1(X_i)=\pi [i]P(Y^0|X_i),& 1\le i\le N\\ \text{Recursion:}& {\alpha }_{t+1}(i)=\underset{1\le i\le N}{\max }[{\alpha }_t(X_j)P(X_i|X_j)]P(Y^t|X_i),& 1\le t\le T-1,1\le i\le N\\ \text{Termination:}& P(O)=\underset{1\le i\le N}{\max }{\alpha }_T(i),& \end{array}$$

Further reading:

• Viterbi Algorith