Viterbi Algorithm › Summary

The Viterbi algorithm solves the optimal path problem for sequence labeling. Given a sequence of observations and a model with transition and emission probabilities, it finds the single best sequence of hidden states in time linear in sequence length.

The key ideas covered in this chapter:

Dynamic programming makes the exponential search space tractable. By storing the best score for each state at each position, we avoid recomputing shared subsequences. The $O(n \cdot k^2)$ complexity enables real-time tagging of long documents.

Backpointer tracking enables path reconstruction. At each cell in the Viterbi table, we record which predecessor achieved the maximum score. After filling the table, we trace back from the best final state to recover the optimal path.

Log-space computation prevents numerical underflow. Working with log probabilities converts products to sums, keeping values in a representable range even for long sequences. This is essential for any practical implementation.

Constrained decoding enforces structural requirements. For BIO tagging, we set invalid transition probabilities to zero. This ensures the output is always a valid tag sequence regardless of what the model's raw scores suggest.

Beam search connects to Viterbi as an approximation. By keeping only the top $k$ hypotheses at each step, beam search trades optimality for speed. With beam width equal to the number of states, it recovers Viterbi exactly.

When implementing or using Viterbi decoding, these parameters control behavior:

• states: The set of possible hidden states (tags). Larger state sets increase computation quadratically
• transition_prob: Matrix or dictionary of $P(s_i | s_{i-1})$ values. Sparse matrices enable optimization
• emission_prob: Matrix or dictionary of $P(w_i | s_i)$ values. In neural models, these come from network outputs
• start_prob: Initial state distribution $P(s_1)$. Often uniform or learned from data
• beam_width: For approximate decoding, controls the number of hypotheses retained. Larger values approach exact Viterbi

The next chapter introduces Conditional Random Fields, which generalize HMMs by allowing arbitrary feature functions while still using Viterbi for efficient decoding.