Viterbi Algorithm › Limitations and Practical Considerations

The Viterbi algorithm is optimal for first-order Markov models where the current state depends only on the previous state. Several limitations arise in practice:

• Higher-order dependencies exist in natural language. The optimal tag for a word might depend on tags two or three positions back. Extending Viterbi to second-order Markov models is possible but increases complexity to $O(n \cdot k^3)$ since we must track pairs of previous states.

• Non-local features are common in neural sequence models. A BiLSTM encodes the entire sentence before making predictions, so the score at each position depends on the previous tag and the full context. CRF layers on top of neural models use Viterbi for decoding, but the emission scores come from the neural network rather than simple probability tables.

• Approximate inference becomes necessary with large state spaces. In machine translation, the "states" are partial translations with exponentially many possibilities. Beam search provides a practical approximation, trading optimality for tractability.

• Label dependencies beyond transitions sometimes matter. In some tagging schemes, the entity type of a word might depend on the immediately preceding tag as well as entity types earlier in the sentence. Such long-range dependencies require more sophisticated inference methods.

Despite these limitations, Viterbi remains the workhorse algorithm for sequence labeling. Its efficiency, optimality guarantees for Markov models, and straightforward implementation make it the right choice for most POS tagging and NER systems. When combined with neural feature extractors and CRF output layers, it achieves state-of-the-art results on many benchmarks.