Viterbi Algorithm (1967) › The Problem: Finding Needles in Exponential Haystacks

The core challenge that motivated the Viterbi algorithm appears whenever you need to determine the most likely hidden sequence from observations. In error-correcting codes, the hidden sequence is the original message bits, and the observations are the noisy received signal. In speech recognition, the hidden sequence is the words or phonemes being spoken, and the observations are acoustic features extracted from audio. In part-of-speech tagging, the hidden sequence is the grammatical categories of words, and the observations are the words themselves.

In each case, the challenge is the same: given an observation sequence of length $T$, how do you find the hidden state sequence that most likely produced those observations? If you have $N$ possible states at each time step, there are $N^T$ possible sequences to consider. For even modest values.say, $N = 50$ states and $T = 20$ observations.you're dealing with $50^{20}$ possible sequences, a number so large that enumerating all possibilities is computationally impossible.

The naive approach would be to compute the probability of each possible sequence given the observations and select the one with the highest probability. But this requires evaluating an exponential number of sequences. Even if each evaluation took only a microsecond, examining all $50^{20}$ sequences would take longer than the age of the universe. Clearly, a different approach was needed.

The problem becomes even more challenging when you consider that observations can be ambiguous. In speech recognition, the same acoustic feature might be consistent with multiple different phonemes. In part-of-speech tagging, the word "bank" could be a noun (financial institution) or a verb (to deposit). The system must use context.both the transition probabilities between states and the observation probabilities for each state.to resolve these ambiguities. But doing so requires reasoning about sequences, not just individual decisions.

Before the Viterbi algorithm, researchers attempted various approximations. Some systems made greedy decisions, choosing the most likely state at each time step independently without considering how these choices affected later decisions. This local optimization often led to globally suboptimal sequences. Other systems explored only a subset of possible sequences using heuristics, but couldn't guarantee finding the true optimal solution. What was needed was an algorithm that could efficiently find the globally optimal sequence without exhaustive enumeration.