The Viterbi Algorithm
Given a hidden Markov model and a sequence of observations, the Viterbi algorithm finds the single most likely sequence of hidden states. It uses dynamic programming to avoid checking every possible path.
The combinatorial trap
With many states and a long sequence the number of possible state paths grows exponentially. Enumerating them is hopeless, so Viterbi reuses subproblem results instead.
The key recursion
Viterbi keeps, for each state at each time step, the probability of the best path that ends in that state. To extend one step it considers every previous state, multiplies by the transition and emission probabilities, and keeps only the maximum.
- It also records which previous state gave that maximum, a back pointer.
- At the end it picks the best final state and follows the back pointers backward.
- This backtracking reconstructs the optimal path.
Why it is efficient
Each step's cost depends on the number of states squared times the sequence length, far less than the exponential blow up of brute force. The trick is that the best path to a state never needs the suboptimal paths into it.
Max versus sum
Viterbi takes a maximum at each step, finding the single best path. Replacing the maximum with a sum gives the forward algorithm, which instead computes the total probability of the observations.
Key idea
Viterbi uses dynamic programming and back pointers to find the most likely hidden state path efficiently.