Viterbi Algorithm

Given a hidden Markov model and an observed sequence $X_1,\dots ,X_T$, the Viterbi algorithm finds ${\hat{Z}}_{1:T}=\arg {\max }_{z_{1:T}}P(Z_{1:T}=z_{1:T}\mid X_{1:T})$, the single hidden state sequence maximizing the joint posterior probability. It uses dynamic programming, defining ${\delta }_t(i)={\max }_{z_{1:t-1}}P(z_{1:t-1},Z_t=i,X_{1:t})$, the highest joint probability of any path ending in state $i$ at time $t$, computed recursively as ${\delta }_t(j)=\left[{\max }_i{\delta }_{t-1}(i)a_{ij}\right]b_j(X_t)$, while tracking backpointers recording which predecessor state $i$ achieved the maximum at each step. After the forward recursion reaches $t=T$, backtracking through the stored pointers recovers the complete optimal state sequence. Like the forward-backward algorithm, Viterbi runs in $O(T{N}^2)$ time via dynamic programming, replacing sums with maximizations at each step (a substitution known more generally as the max-product, rather than sum-product, algorithm).

• The Viterbi algorithm's answer and the forward-backward algorithm's state-by-state most-likely answers can genuinely disagree, stitching together each time point's individually most likely state does not always produce a path that is itself internally consistent under the transition probabilities, only Viterbi's global optimization guarantees the single best whole sequence.
• Speech recognition systems historically used Viterbi decoding to convert a stream of acoustic observations into the single most likely sequence of phonemes or words, and the same algorithm (often called Viterbi decoding in this context) is separately central to error-correcting convolutional codes in digital communications.
• In bioinformatics, Viterbi decoding of profile HMMs is a standard technique for gene finding and sequence alignment, identifying the single most likely alignment or annotation of a DNA or protein sequence against a known statistical model of gene structure.