The Viterbi algorithm decodes the maximum-likelihood sequence of latent states in a hidden Markov model. Rather than estimating each state independently, it searches for the most probable complete path through the observed sequence. section 7.1.2
A practical Viterbi decoder follows this structure:
- Represent the HMM with a latent-state transition matrix, an emission matrix, and an initial-state distribution. section 7.1.2
- Define δt(j) as the probability of ending in state j along the most probable path through the preceding time steps. section 7.1.2
- Initialize the recursion at the sequence start, propagate the best path probabilities through subsequent observations, and recover the maximum-likelihood state sequence. section 7.1.2
- Compute in log space so multiplication becomes addition and numerical underflow is reduced. section 7.1.2
From-scratch HMM inference
A small HMM implementation initializes transition and emission matrices, constructs sparse emission indicators, and exposes a viterbi function. After decoding a randomly initialized model, the returned state sequence gives the maximum-likelihood transitions for the observations. section 7.1.2
Figure 7.4 Hidden Markov model pseudo-code
Use the HMM pseudo-code to compare the Viterbi decoder with forward–backward inference and trace their distinct outputs. section 7.1.2
