How the Viterbi algorithm works

What problem does the Viterbi algorithm solve?

Many situations hide their causes. A doctor hears how a patient feels but cannot see the illness directly. A phone receives a stream of bits that noise has partly scrambled. A speech recogniser hears sound, but the words that produced it are what it actually wants. In each case there is a sequence of observations and, behind it, a sequence of hidden states that produced them.

A hidden Markov model describes that setup with two kinds of probability: how likely each hidden state is to follow the previous one, and how likely each observation is given the current hidden state. The Viterbi algorithm takes such a model and a list of observations and returns the one hidden sequence most likely to have produced them. That answer is called the Viterbi path.

How does it avoid checking every possibility?

The number of possible hidden sequences grows explosively with length, so trying them all is hopeless. Viterbi uses dynamic programming instead. At each step, for each hidden state, it asks one question: of all the paths that could end in this state right now, which is most probable? It keeps that probability and a note of which state came just before. Every other path into that state is thrown away, because whatever happens next, a weaker path into the same state can never overtake the stronger one.

When the observations run out, the algorithm picks the state with the highest final probability and follows the stored notes backwards to recover the whole path. The work grows with the length of the sequence times the square of the number of states, rather than exponentially. Drawn as a grid of states over time, called a trellis, the Viterbi path is essentially the best route through that grid.

A worked example: healthy or feverish?

A standard illustration has a doctor who can only ask patients how they feel: normal, cold or dizzy. The hidden states are healthy and fever. The model says a patient starts healthy with probability 0.6 and feverish with 0.4. A healthy patient stays healthy the next day with probability 0.7 and develops a fever with 0.3. A healthy patient feels normal half the time and dizzy only 0.1 of the time, while a feverish one feels dizzy with probability 0.6.

One patient reports feeling normal, then cold, then dizzy. On day one, healthy and normal has probability 0.6 times 0.5, which is 0.3; fever and normal has 0.4 times 0.1, which is 0.04. For day two, the best way to be healthy and feel cold is to have been healthy the day before, scoring 0.084, far ahead of the 0.0064 route through an earlier fever. Continuing to day three, the strongest final entry ends in fever with probability 0.01512, and tracing back gives healthy, healthy, fever.

So the most likely story is that the patient was well on the first two days, despite feeling cold on the second, and fell ill on the third. In this case the best path also matches the best single guess for each day, but that is a coincidence. In general the most likely sequence and the sequence of individually most likely states can differ.

Where is it used?

Andrew Viterbi proposed the algorithm in 1967 to decode convolutional codes sent over noisy digital links, and that remains its signature use: it decodes the error-correcting codes in CDMA and GSM mobile networks, dial-up modems, satellite and deep-space communication, and 802.11 wireless networks. It is also standard in speech recognition and synthesis, keyword spotting, working out who spoke when in a recording, computational linguistics and bioinformatics. It was applied to part-of-speech tagging in language processing as early as 1987.

The method has been discovered independently at least seven times, including by Needleman and Wunsch and by Wagner and Fischer, and its name has become shorthand for this style of dynamic programming whenever the goal is the most probable explanation. A generalisation, the max-sum or max-product algorithm, does the same job on other graphical models such as Bayesian networks, provided their variables are linked in a roughly chain-like way.

What are its limits?

Viterbi is only as good as the model it is given. If the transition or observation probabilities are wrong, it will confidently return the most likely path under the wrong assumptions. The standard version also returns a single hard answer with no sense of how close the runner-up was. The soft output variant, known as SOVA, adds a measure of how reliable each decision is.

Cost can matter too. The original algorithm evaluates every node of the trellis. The Lazy Viterbi algorithm keeps a prioritised list of nodes and typically needs fewer calculations for the same result, and never more, though it is harder to run in parallel on hardware.

What does it teach about thinking?

When reasoning about a chain of events, judge whole explanations, not isolated moments. The most plausible story overall can include a step that looks unlikely on its own. And you rarely need to weigh every possible story: at each point, keep the best account of how you could have got here and let the rest go.

Questions people ask

The thinking behind it

• bayesian thinking
• signal vs noise
• local vs global optimum

More algorithms, explained

• How a Bayesian network works
• How a greedy algorithm works
• How an inverted index works
• How proof of work works