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).

Write the Viterbi recursion $\delta_t(j) = \max_i[\delta_{t-1}(i)a_{ij}]b_j(o_t)$ and the backtracking procedure; what is the complexity?

How do Viterbi and the forward algorithm differ (sum vs max, their outputs, and why Viterbi needs the backpointer table $\psi$)?

Why does Viterbi guarantee a global optimum, unlike greedy per-position choice or beam search?

Work through a concrete example (e.g. $N=2$, $T=3$) by hand, deriving the best path and explaining backtracking.

How is Viterbi used in CRF/MEMM inference (the same decoding DP with different score functions)?