Viterbi Algorithm

The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states — the Viterbi path — in a hidden Markov model, given a sequence of observed emissions. Invented by Andrew Viterbi in 1967, it is the canonical example of how exponential search spaces can be tamed by optimal substructure: the most likely path to any state at time t depends only on the most likely paths to all states at time t-1.

The algorithm operates by maintaining a probability matrix where each cell represents the maximum probability of reaching a particular hidden state while emitting the observed sequence up to that point. The recurrence is:

v_t(j) = max_i [v_{t-1}(i) * a_{ij} * b_j(o_t)]

where a_{ij} is the transition probability from state i to j and b_j(o_t) is the emission probability of observation o_t from state j. The maximization over i is the key insight: instead of tracking all possible paths, we track only the best path to each state, discarding suboptimal prefixes with the guarantee that they cannot lead to an optimal full path.

This structure — maintain only the best partial solution at each step — is identical to the logic of Dijkstra (best-first pathfinding), Floyd-Warshall (all-pairs shortest paths), and sequence alignment. The Viterbi algorithm is not a speech recognition technique. It is a pattern: the optimal path through a layered graph can be found by dynamic programming because the problem has optimal substructure and overlapping subproblems.

The algorithm's applications extend far beyond its original use in digital communications. It is used in bioinformatics (gene finding, protein structure prediction), natural language processing (part-of-speech tagging, named entity recognition), and computational linguistics (morphological analysis). In each domain, the hidden states represent structural hypotheses and the observations represent surface evidence; the Viterbi algorithm finds the best structural parse.

The Viterbi algorithm is a demonstration that the most likely explanation of a sequence is not found by evaluating all explanations. It is found by recognizing that suboptimal explanations can be discarded at every step, provided the problem has the right structure. This is not merely an optimization. It is an epistemic principle: the best global hypothesis is composed of the best local hypotheses, and the search space collapses accordingly.