Viterbi Decoding

The decoding problem asks for the most probable hidden state sequence $q^* = \arg\max_q P(q \mid O, \lambda)$ given $\lambda = (A, B, \pi)$ and observations $O$. Viterbi maintains the DP quantity $\delta_t(j)$ — the maximum probability over all paths that end in state $j$ at time $t$ after emitting $o_1 \dots o_t$ — via

with a backpointer table $\psi_t(j) = \arg\max_i \delta_{t-1}(i) a_{ij}$ storing the optimal predecessor; initialized by $\delta_1(j) = \pi_j b_j(o_1)$, it terminates with $P^* = \max_j \delta_T(j)$ and then walks the $\psi$ table backward (backtracking) to recover the full best sequence. Complexity is $O(N^2 T)$, the same order as the forward algorithm.

part-of-speech tagging, named-entity recognition, best-path search in speech and handwriting recognition; interviews often contrast Viterbi with the forward algorithm and with greedy/beam search.

enumerating $N^T$ paths is intractable; like forward, Viterbi caches subproblems but replaces summation with max and keeps predecessors to reconstruct the trajectory, guaranteeing a globally optimal path rather than greedy step-wise optima; the cost is $O(N^2)$ comparisons per step and retaining the full $\psi$ table for backtracking (it cannot be rolled over like evaluation).

Test Your Knowledge: Practice Questions for "Viterbi Decoding"

Single choice pitfall questions with instant feedback and mistake tracking.