The Viterbi Algorithm

An HMM defines a joint distribution over a hidden state sequence $q_1, \dots, q_T$ and an observation sequence $o_1, \dots, o_T$, parameterized by an initial distribution $\pi$, a transition matrix $A$ (with $a_{ij} = P(q_t = j \mid q_{t-1} = i)$), and an emission distribution $B$ (with $b_j(o_t) = P(o_t \mid q_t = j)$). Given a fixed observation sequence, decoding means recovering the hidden states that produced it. There are two distinct decoding questions one might ask, and it is essential not to conflate them. The first question — answered by the Forward Algorithm — is "what is the total probability of this observation sequence, summed over all possible hidden paths?" The second question — answered by Viterbi — is "what is the single hidden path with the highest joint probability?" These differ because summing over many moderately-probable paths can outweigh one highly-probable path; the forward algorithm answers a marginal-probability question, while Viterbi answers a MAP (maximum a posteriori) question over entire sequences. Formally, Viterbi computes

where $\lambda = (\pi, A, B)$ is the HMM. A naive solution would enumerate all $N^T$ possible state sequences (for $N$ hidden states and $T$ time steps) and score each one — computationally infeasible even for modest $T$. Viterbi avoids this by exploiting the Markov property: the probability of being in state $j$ at time $t$, having taken the best possible path so far, depends only on which state was occupied at time $t-1$, not on the full history before that. This licenses a dynamic-programming recurrence in which the best partial path ending in each state is built incrementally from the best partial paths one step earlier.

The central data structure is a trellis: a grid with one column per time step $t = 1, \dots, T$ and one row per hidden state $s = 1, \dots, N$. Each cell $(s, t)$ will hold two numbers: $\delta_t(s)$, the probability of the most likely path that ends in state $s$ at time $t$ and accounts for observations $o_1, \dots, o_t$; and $\psi_t(s)$, a backpointer recording which state at time $t-1$ was used to achieve that maximum. The algorithm fills this trellis left to right, then reconstructs the optimal path by walking backpointers from the best final cell back to time 1.

Initialization. At $t=1$ there is no predecessor, so the best path ending in state $s$ is simply the prior probability of starting in $s$ times the probability of emitting $o_1$ from $s$:

Recursion. For $t = 2, \dots, T$ and every state $s$, consider every possible predecessor state $s'$. The best path landing in $s$ at time $t$ must have come from whichever predecessor $s'$ maximizes (best path to $s'$) × (transition $s' \to s$), and then it emits $o_t$ from $s$:

Termination. The probability of the single best sequence overall is the maximum over $\delta_T(s)$ across all final states, and the last state of that optimal sequence is the argmax:

Backtrace. Starting from $q_T^\star$, repeatedly follow $\psi$ backward: $q_{t-1}^\star = \psi_t(q_t^\star)$, for $t = T, \dots, 2$, producing the full optimal state sequence. In practice, probabilities are replaced by log-probabilities and products become sums, both to avoid numerical underflow over long sequences and to turn multiplications into additions for speed. ``` function VITERBI(observations o[1..T], states S, initial π, transitions A, emissions B): N ← number of states allocate delta[1..N][1..T] # delta[s][t] = best path score ending in state s at time t allocate psi[1..N][1..T] # psi[s][t] = backpointer: best predecessor state

# --- Initialization (t = 1) --- for s in 1..N: delta[s][1] ← log(π[s]) + log(B[s][o[1]]) psi[s][1] ← NONE

# --- Recursion (t = 2 .. T) --- for t in 2..T: for s in 1..N: best_score ← -infinity best_prev ← NONE for s_prev in 1..N: score ← delta[s_prev][t-1] + log(A[s_prev][s]) if score > best_score: best_score ← score best_prev ← s_prev delta[s][t] ← best_score + log(B[s][o[t]]) psi[s][t] ← best_prev

# --- Termination --- best_final_score ← -infinity best_final_state ← NONE for s in 1..N: if delta[s][T] > best_final_score: best_final_score ← delta[s][T] best_final_state ← s

# --- Backtrace --- path[T] ← best_final_state for t in T .. 2: path[t-1] ← psi[path[t]][t] return path[1..T], best_final_score ``` Two edge cases deserve care. If some emission or transition probability is exactly zero, its log is $-\infty$; the max-search must handle this without crashing (representable as a very large negative sentinel, not literal division). If $T = 1$, the recursion loop never executes and the answer is simply the argmax of the initialization row — the pseudocode above handles this correctly since termination reads directly from column 1 in that case.

Time complexity. The recursion fills $N$ cells at each of $T$ time steps, and computing each cell's $\delta_t(s)$ requires scanning all $N$ possible predecessor states $s'$. This gives $O(N^2 T)$ time overall for the forward fill. The termination step is $O(N)$ and the backtrace is $O(T)$, both dominated by the fill. So total time is $\Theta(N^2 T)$ in the worst case (dense transition matrix), with no better general algorithm possible without additional structure, since every transition weight may in principle matter to the optimum.

Space complexity. The full trellis of $\delta$ and $\psi$ values requires $O(NT)$ space. This can be reduced: if only the final best probability is needed (not the path), only the current and previous columns of $\delta$ need to be kept, giving $O(N)$ space — but the backpointer table $\psi$ must still be stored in full ($O(NT)$) if the actual path is to be recovered, since backtracing needs a complete history of choices.

Correctness. The proof is an induction on $t$ establishing the invariant: > Invariant: For every state $s$ and every time $t$, $\delta_t(s)$ equals the probability of the single most likely state sequence $q_1, \dots, q_t = s$ that is consistent with observations $o_1, \dots, o_t$. Base case ($t=1$): There is only one "path" of length 1 ending in state $s$: start there. Its probability is exactly $\pi_s \cdot b_s(o_1)$, matching the initialization, so the invariant holds trivially. Inductive step: Assume the invariant holds at $t-1$, i.e., $\delta_{t-1}(s')$ is truly the best score for every predecessor $s'$. Any path ending in state $s$ at time $t$ passes through some state $s'$ at time $t-1$. By the Markov property, the probability of the full path factors as

i.e., the score up through $s'$ times the transition into $s$ times the emission at $s$. Because this factorization holds for every choice of predecessor $s'$ independently of the internal structure of the path before time $t-1$, the overall best path ending in $s$ at $t$ must use, as its prefix, the best possible path ending in some $s'$ at $t-1$ — otherwise substituting a better prefix (which exists, by the definition of "best") would strictly increase the total probability, contradicting optimality. This is precisely the optimal substructure property required for dynamic programming to be valid: the global optimum decomposes into optimal solutions to subproblems. Hence

is correct, matching the recurrence, completing the induction. At termination, $\max_s \delta_T(s)$ is therefore the true maximum over all complete paths, and backtracing $\psi$ reconstructs an actual sequence achieving it (each $\psi_t(s)$ was chosen precisely to be the predecessor realizing that max, so following pointers backward reconstructs a fully consistent, globally-optimal path).

Tradeoffs. Viterbi is exact and efficient given correct HMM parameters, but it inherits any mis-specification in $\pi$, $A$, $B$ — a poorly estimated emission distribution yields a confidently wrong path. It also commits to a single best sequence; if the application actually wants marginal state probabilities (e.g., "what's $P(q_t = \text{NOUN})$ regardless of the rest of the path?") the Forward-Backward Algorithm is the right tool, not Viterbi. Finally, the $O(N^2T)$ cost becomes a real bottleneck when $N$ is large (e.g., large tagsets), motivating beam-pruned approximate variants that trade exactness for speed — this is the same tension that shows up in neural sequence decoding via Beam Search.

Consider a minimal part-of-speech HMM with two hidden states, $\{N, V\}$ (noun, verb), and the observation sequence "flies like flowers" reduced for simplicity to two tokens: flies, like. Suppose the parameters are:

• Initial: $\pi_N = 0.6,\ \pi_V = 0.4$
• Transitions: $a_{NN}=0.3,\ a_{NV}=0.7,\ a_{VN}=0.6,\ a_{VV}=0.4$
• Emissions: $b_N(\text{flies})=0.4,\ b_V(\text{flies})=0.3,\ b_N(\text{like})=0.1,\ b_V(\text{like})=0.5$

Step 1 — Initialization ($t=1$, word = "flies"):

Step 2 — Recursion ($t=2$, word = "like"): for each state, check both predecessors. For state N at $t=2$:

Tie — take either (say, the first, N, by convention); $\delta_2(N) = 0.072 \times b_N(\text{like}) = 0.072 \times 0.1 = 0.0072$, $\psi_2(N) = N$. For state V at $t=2$:

Max is $0.168$ from N; $\delta_2(V) = 0.168 \times b_V(\text{like}) = 0.168 \times 0.5 = 0.084$, $\psi_2(V) = N$.

Step 3 — Termination: compare $\delta_2(N)=0.0072$ vs $\delta_2(V)=0.084$. The maximum is $0.084$, at state V.

Step 4 — Backtrace: $q_2^\star = V$; $\psi_2(V) = N$, so $q_1^\star = N$.

Result: the optimal tag sequence is N, V — "flies" tagged as noun, "like" tagged as verb — with joint probability $0.084$. This matches intuition: "flies" as a noun (the insects) followed by "like" as a verb (the action) is indeed the natural reading, and the algorithm found it by comparing all four candidate two-step paths implicitly via just $N^2 T = 2^2 \times 2 = 8$ multiply-operations, rather than enumerating $N^T = 4$ full paths from scratch and rescoring each (a saving that becomes exponential in longer sequences).

The algorithm is named for Andrew Viterbi, an electrical engineer who devised it in the context of decoding convolutionally-encoded signals over noisy communication channels — a problem structurally identical to HMM decoding, since a convolutional code's trellis and an HMM's state trellis share the same mathematical skeleton. The technique was independently discovered and rediscovered across several fields — coding theory, speech recognition, and computational biology — because dynamic programming over a Markov trellis is a naturally recurring structural pattern wherever hidden sequential state must be inferred from noisy observations.

Viterbi decoding is the inference backbone of classical statistical speech recognition systems, where hidden phoneme or word states must be recovered from acoustic observations frame by frame. It is equally central to statistical part-of-speech tagging, where the hidden states are grammatical tags and observations are words — a direct precursor to the tagging and span-labeling techniques used in Named-Entity Recognition, where a similar trellis recovers the most likely sequence of entity tags (e.g., B-PER, I-PER, O) given a sentence. In bioinformatics, Viterbi decoding recovers the most probable sequence of gene/intron states along a DNA strand from an HMM trained on sequence data. In digital communications — its original home — it remains the standard decoder for convolutional and trellis codes in cellular standards. Even modern neural architectures that stack a Conditional Random Field on top of a BiLSTM or Transformer encoder still invoke Viterbi decoding at inference time, because the CRF layer imposes exactly the Markovian tag-transition structure that makes the algorithm both applicable and exact; understanding Viterbi is therefore a prerequisite for understanding how such hybrid neural/structured models actually produce their output sequences at prediction time.

Ask the tutor: How does the Viterbi algorithm's dynamic-programming recurrence change when moving from a generative HMM to a discriminative linear-chain CRF used in modern NER systems?