Viterbi

The Viterbi algorithm is a dynamic programming method used to decode the most likely sequence of hidden states in a hidden Markov model, given a sequence of observed events. It is widely used to decode convolutional codes in digital communications and is foundational in many pattern recognition tasks, including speech recognition and bioinformatics.

The algorithm operates on a trellis diagram representing possible state transitions. It computes, for each time step and state, the maximum probability of any path that ends in that state, using a recurrence that combines the best path to a previous state with the transition and emission probabilities. This is typically implemented in the log domain to prevent underflow. A backpointer array records, for each time and state, the previous state that yielded the maximum value. After processing all observations, the final most likely state is chosen, and the most likely state sequence is obtained by tracing the backpointers from the final state to the start.

Complexity-wise, if the hidden Markov model has N states and T observations, the standard Viterbi pass runs in O(T N^2) time and O(T N) memory for storing backpointers; optimized implementations can reduce memory to O(N). Variants include numerical stability improvements, such as working in log probabilities or using scaling factors.

History and impact: The algorithm was introduced by Andrew J. Viterbi in 1967 in the context of decoding convolutional codes. It has since become a standard tool in digital communications, speech processing, and computational biology, where it is used for sequence estimation under Markov assumptions.