Viterbi Algorithm › The Viterbi Recursion

We've established that greedy decoding fails because local choices can force globally suboptimal sequences, and that exhaustive search is computationally impossible. How can we find the optimal path without examining every possibility? The answer lies in a beautiful insight from dynamic programming: we can build the optimal solution incrementally from smaller optimal solutions.

Imagine you're at position 3 in a sequence, and you want to know the best path that ends at the tag NOUN. The recurrence relies on this observation: regardless of how that path reached position 2, the best continuation to NOUN at position 3 depends only on:

1. What state we're in at position 2 (not how we got there)
2. The transition probability to NOUN
3. The emission probability of the observed word from NOUN

This property is called optimal substructure. If the best path through the entire sequence passes through state $s'$ at position 2 and then reaches NOUN at position 3, then the portion of that path from the start to $s'$ must itself be optimal. Why? If there were a better path to $s'$, we could substitute it and get a better overall path, contradicting our assumption that we had the best path.

This principle transforms our approach entirely. Instead of tracking complete paths (exponentially many), we only need to track the best score for reaching each state at each position. At any position, we have just $k$ values to maintain, one per possible state, rather than an exponentially growing set of paths.

Let's formalize this insight. We define $V_i(s)$ as the probability of the most likely path that:

• Ends at state $s$ at position $i$
• Generates the observations $w_1, \ldots, w_i$ seen so far

How do we compute $V_i(s)$? Consider any path ending at state $s$ at position $i$. That path must have come from some predecessor state $s'$ at position $i-1$. The probability of this path factors into three terms:

1. The probability of the best path to $s'$: This is $V_{i-1}(s')$, which we've already computed
2. The transition probability from $s'$ to $s$: This is $P(s | s')$
3. The probability of emitting the current observation from $s$: This is $P(w_i | s)$

Since we want the best path to $s$, we take the maximum over all possible predecessor states. This gives us the Viterbi recurrence:

$$V_i(s) = \max_{s'} \left[ V_{i-1}(s') \cdot P(s | s') \cdot P(w_i | s) \right]$$

where:

• $V_i(s)$: the probability of the best path ending at state $s$ at position $i$
• $\max_{s'}$: takes the maximum over all possible predecessor states $s'$
• $V_{i-1}(s')$: the best score for reaching state $s'$ at the previous position (already computed)
• $P(s | s')$: the transition probability from predecessor state $s'$ to current state $s$
• $P(w_i | s)$: the emission probability of observing word $w_i$ from state $s$

Notice that $P(w_i | s)$ appears inside the maximization but doesn't depend on the predecessor $s'$. This is because once we decide to be in state $s$ at position $i$, the emission probability is fixed regardless of how we arrived. We could factor it out:

$$V_i(s) = P(w_i | s) \cdot \max_{s'} \left[ V_{i-1}(s') \cdot P(s | s') \right]$$

This form is computationally equivalent but makes clear that we're choosing the best predecessor based solely on the accumulated path score and transition, then multiplying by the emission.

The recurrence needs a starting point. At position 1, there is no predecessor to consider. The probability of the best path ending at state $s$ after seeing just the first observation is simply:

$$V_1(s) = P(s) \cdot P(w_1 | s)$$

where:

• $P(s)$: the initial state probability (how likely the sequence starts in state $s$)
• $P(w_1 | s)$: the emission probability of the first observation from state $s$

This captures both how likely we are to start in state $s$ and how well state $s$ explains the first observed word.

Let's count the operations. At each of the $n$ positions (after the first), we compute $V_i(s)$ for each of the $k$ states. Computing each $V_i(s)$ requires examining $k$ predecessors. Total: $O(n \cdot k^2)$ operations.

Compare this to the $k^n$ paths we would examine exhaustively:

The exponential has become polynomial. This is the power of dynamic programming: by recognizing that we can solve the problem incrementally and that we only need to remember the best score per state (not every path), we collapse an intractable problem into an efficient algorithm.

It helps to visualize the Viterbi computation as filling a grid called a trellis. The horizontal axis represents positions in the sequence (1 through $n$), and the vertical axis represents possible states (the $k$ tags or labels). Each cell $(i, s)$ holds the score $V_i(s)$, the probability of the best path ending at state $s$ at position $i$.

Arrows connect cells at adjacent positions. Each arrow from $(i-1, s')$ to $(i, s)$ represents one term in the maximization: "if I came from state $s'$, what would my score be?" The algorithm fills this grid column by column, left to right, computing each cell from the cells in the previous column.