This is a short post that continues from the more-detailed alpha recursion HMM post. In this post I’ll implement the Viterbi algorithm like Barber does in “Bayesian Reasoning and Machine Learning”. Like before, I’m porting the MatLab code from the textbook.

## Viterbi algorithm in HMMs using message passing

The Viterbi algorithm finds the most-likely path $$h_{1:T}$$ for the visibles $$v_{1:T}$$, where $$T$$ is the timestep of the last observed visible. The algorithm takes in the visibles $$v_{1:T}$$, the initial state $$p(h_1)$$, the transition probabilities $$p(h_{t} \mid h_{t - 1})$$, and the emission probabilities $$p(v_t \mid h_t)$$, and returns the list of most-likely hidden states $$h_{1:T}$$.

I generated the required probabilities in the alpha recursion HMM post.

### Algorithm

Barber frames the Viterbi algorithm as message passing using the max-product algorithm.

This version of the algorithm begins at the end of the hidden states ($$h_T$$), and computes an incoming message from future states. The message is meant to represent the effect of maximizing over those states. Barber gives the messages as:

Once the messages are computed, the algorithm then computes the most-likely state for $$h_1$$, and uses that to compute the most-likely state for $$h_2$$ and so on. It basically maximizes the marginal of $$p(h_t \mid v_{1:T})$$ and then uses the most-likely state for $$h_t$$ in the transition matrix for computing $$p(h_{t + 1} \mid v_{1:T})$$ so it returns a valid path.

Now in Python!

## Visualizing

I can plot the most-likely states. 