Understanding Viterbi Algorithm
Filtering and smoothing answer questions about one time step at a time. Asking instead for the whole history that best explains the observations is a different question, and answering it by taking the most likely state at each step separately is wrong: the per-step winners need not form a possible sequence, let alone a likely one.
The Viterbi algorithm fixes this with one change to the forward recursion. Where filtering sums over the ways of reaching a state, Viterbi takes the maximum, carrying the probability of the best path to each state rather than the total probability of all paths. Recording which predecessor achieved that maximum gives a back-pointer, and following the pointers back from the best final state reconstructs the sequence.
The saving is the same one dynamic programming always buys. There are 2^t histories over t binary states, and the recursion touches each state once per step, so the cost is linear in t and quadratic in the number of states. Nothing is approximated: the answer is the exact maximiser.
Which question to ask is a modelling decision rather than a technicality. Per-step marginals are right when each step will be acted on separately; Viterbi is right when the states have to hang together, as in decoding a message, aligning a sequence or reconstructing a route, where a physically impossible transition in the middle of the answer is worse than a slightly less likely one.
How to Calculate
m_{1:t+1} = P(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1}) \max_{\mathbf{x}_t} \big( P(\mathbf{X}_{t+1} \mid \mathbf{x}_t)\, m_{1:t} \big)
where
- m_{1:t}
- the probability of the best path ending in each state at time t
- P(\mathbf{X}_{t+1} \mid \mathbf{x}_t)
- the transition model
- P(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1})
- the sensor model
Example of Viterbi Algorithm
In the umbrella world - rain persists with probability 0.7, an umbrella appears on 90 per cent of rainy days and 20 per cent of dry ones - take the three observations no umbrella, umbrella, no umbrella.
Smoothing day two on its own gives a probability of rain of 0.554, so the per-step answer says it rained. The most likely three-day history, found by Viterbi and confirmed by enumerating all eight, is dry on all three days, with probability 0.402.
There is no contradiction. Rain on day two is the single most likely value for that day when the other days are averaged over; the all-dry history is the most likely combination when they are not. The two questions have different answers because the days are not independent.
Frequently Asked Questions
Is the Viterbi path the same as the path of smoothed maxima?
Not in general, and the umbrella example above is a counterexample found by enumeration rather than asserted. The smoothed maxima can even form a sequence with probability zero if some transition is impossible.
Does it work in log space?
It is usually run there. The recursion multiplies probabilities, which underflows over a long sequence; taking logarithms turns the products into sums, and the maximum is unaffected because the logarithm is increasing.
The Bottom Line
Replace the sum in the forward recursion with a maximum, keep a back-pointer, and you get the single most likely history in linear time. Just be clear that it answers a different question from the one smoothing answers, and that the two can genuinely disagree.