Viterbi Algorithm › The Optimal Path Problem

Consider a hidden Markov model for part-of-speech tagging. You observe a sequence of words $w_1, w_2, \ldots, w_n$ and want to find the sequence of tags $t_1, t_2, \ldots, t_n$ that maximizes the joint probability of seeing both the tags and the words together. The HMM factors this joint probability into a product of simpler terms:

$$P(t_1, \ldots, t_n, w_1, \ldots, w_n) = P(t_1) \prod_{i=2}^{n} P(t_i | t_{i-1}) \prod_{i=1}^{n} P(w_i | t_i)$$

where:

• $t_1, \ldots, t_n$: the sequence of hidden states (POS tags) we want to infer
• $w_1, \ldots, w_n$: the observed sequence of words
• $P(t_1)$: the initial state probability, capturing how likely the sentence starts with tag $t_1$
• $P(t_i | t_{i-1})$: the transition probability from tag $t_{i-1}$ to tag $t_i$, encoding grammatical patterns like "determiners often precede nouns"
• $P(w_i | t_i)$: the emission probability of word $w_i$ given tag $t_i$, capturing which words are typical for each tag

The first product captures transition probabilities: how likely is each tag given the previous one? The second product captures emission probabilities: how likely is each word given its tag? This factorization embodies the Markov assumption: each tag depends only on its immediate predecessor, not on the full history.

A greedy approach picks the best tag at each position independently, considering only the previous tag. At each position $i$, greedy decoding selects:

$$t_i^* = \arg\max_{t_i} P(w_i | t_i) \cdot P(t_i | t_{i-1}^*)$$

where:

• $t_i^*$: the greedily chosen tag at position $i$
• $\arg\max_{t_i}$: selects the tag $t_i$ that maximizes the following expression
• $P(w_i | t_i)$: the emission probability of the current word given candidate tag $t_i$
• $P(t_i | t_{i-1}^*)$: the transition probability from the previously chosen tag $t_{i-1}^*$ to candidate tag $t_i$

This seems reasonable but can produce suboptimal sequences. The problem is that a locally good choice might force bad choices later. Consider tagging "The can can hold water." A greedy tagger might assign MODAL to the first "can" because modals are common after determiners. But this makes the second "can" difficult: modals rarely follow modals. The globally optimal solution assigns NOUN to the first "can" and VERB to the second, even though NOUN isn't the highest-probability tag for "can" in isolation.

This example demonstrates why greedy decoding fails. The locally optimal choice of MD for the first "can" yields score 0.180, beating NN's 0.125. But this decision creates a problem: the second "can" must follow a modal, and modals rarely follow modals (P(MD|MD) = 0.05). The alternative path through NN enables a much higher score at the next position (0.060 vs 0.030), potentially yielding a better overall sequence probability.

Let's trace the cumulative scores for both paths:

The greedy path starts stronger (0.180 vs 0.125) because MD has higher emission probability for "can." But this local advantage creates a problem: the MD→VB transition at position 3 yields only 0.0216, while NN→VB would have enabled a score of 0.0075. The globally optimal path requires looking ahead, something greedy decoding cannot do.

If greedy decoding doesn't work, why not try all possible tag sequences? With $k$ possible tags and a sequence of length $n$, there are $k^n$ possible sequences. For a modest vocabulary of 45 tags and a 20-word sentence, that's $45^{20} \approx 10^{33}$ sequences, far more than the number of atoms in the observable universe.