Is its answer always correct?

It is optimal under the specified model and recurrence assumptions, which does not ensure agreement with real-world truth.

Why retain backpointers?

The scores identify how good the best paths are. Backpointers recover the actual sequence of states that achieved the winning score.

AI Glossary / Natural language and speech / Intermediate

Viterbi algorithm

Definition

Definition: The Viterbi algorithm finds the highest-scoring complete sequence of hidden states in a model whose score decomposes into suitable local contributions. In a hidden Markov model, it finds the most probable state sequence given the observations, using dynamic programming rather than enumerating every possible sequence.

What it means

What it means: A sequence task may have several plausible labels at each position. Choosing the locally strongest label can lead to a poor overall sequence when transitions between labels matter. Viterbi keeps a best partial path for each possible current state, allowing a path that is not globally leading yet to become the final winner.
The guarantee is about the model and objective supplied. An optimal path under an inaccurate model can still be wrong in reality. Viterbi also does not generally produce the sequence obtained by choosing the most probable individual state at every position; those are different optimization objectives.

How it works

How it works: For an HMM, initialize each state's score using its start probability multiplied by the likelihood of the first observation. At the next position, compare all allowed predecessor states, multiplying the predecessor's best-path score by the transition probability and the current observation likelihood. Keep the maximum and a pointer to its predecessor.
After the final position, choose the best ending state, including any required end-transition score, and follow the pointers backward. Logarithms commonly turn products into sums and reduce numerical underflow. The method is exact when the state captures all history needed for future scoring. A densely connected model with T positions and N states takes O(TN²) time in the usual implementation.

Three practical examples

Three practical examples:
1. An HMM part-of-speech tagger combines word likelihoods with tag-transition probabilities to select a complete tag sequence.
2. A communication receiver decodes a sequence constrained by a finite-state code, combining evidence across multiple noisy observations rather than judging each symbol independently.
3. A sequence-labeling system with a linear-chain scoring structure chooses labels that respect permitted transitions. If an application adds arbitrary dependencies on the entire previous history, the simple state-based recurrence may no longer apply without changing the state representation.

Think of it this way

Think of it: Imagine traveling through successive stages, with several possible stations at each stage. For each station, keep the cheapest route that reaches it, because future travel options depend only on that station. You can discard more expensive routes to the same station. This analogy captures the key condition: if future costs depend on unrecorded route history, discarding those routes may be unsafe.

Worked example

Worked example: Consider two hidden states, A and B, and observations x then y. Start probabilities are A=0.6 and B=0.4. Each state stays unchanged with probability 0.9 and switches with probability 0.1. A emits x with 0.9 and y with 0.1; B emits x and y with 0.5 each. There is no additional end-state factor.
After x, the scores are A: 0.6 × 0.9 = 0.54 and B: 0.4 × 0.5 = 0.20. For y, the complete path scores are AA=0.0486, AB=0.027, BA=0.002 and BB=0.09. Viterbi keeps AA as the best path ending in A and BB as the best ending in B, then selects BB.
A greedy method that committed to A after x could only choose AA or AB, missing BB. All four products were checked in Python. The winning 0.09 is a joint path-and-observation probability, not a normalized posterior confidence. Dividing by the total observation probability 0.1676 gives a posterior of approximately 0.537 for BB.

Illustrative case study

Illustrative case study: Fictional Ridge Labels uses a small sequence model to tag structured text. Its first decoder selects the most attractive next label from one retained history. Reviewers find cases where an initially weaker state leads to a better complete sequence.
The team implements a best-path table with one survivor per state and explicit backpointers. For short test sequences, it compares the result with exhaustive enumeration. It also checks impossible transitions and ties. This invented case illustrates decoder verification; it does not imply that changing the decoder repairs incorrect training labels or guarantees accurate predictions on new documents.

Common misconceptions and mistakes

Common misconceptions and mistakes: Viterbi is not a training algorithm for estimating all model parameters. The forward algorithm sums over paths rather than maximizing over them. A maximum-probability path is not automatically the output that minimizes expected token error or edit distance. Greedy decoding is not equivalent to keeping one path per state. Beam pruning can make a decoder approximate if it removes needed states. Finally, a raw path score should not be presented as calibrated confidence without the required normalization and evaluation.

Business use

Business use: Viterbi is useful when a sequence model has a manageable state space and a clearly defined local scoring structure. Ask what the decoder optimizes, what constraints it enforces and whether pruning changes its guarantee. Keep model quality and search correctness separate during diagnosis. Validate small examples by enumeration and inspect representative errors under the business metric. The highest model score may differ from the choice that best manages the application's cost of mistakes.

Check your understanding

Check your understanding: A decoder retains only the single best partial sequence after every observation. Is it necessarily implementing exact Viterbi?

Answer: No. Exact Viterbi normally retains the best path for each relevant current state. A lower-scoring partial path in another state may become the best complete path after later observations.

Related terms

Hidden Markov model
Dynamic programming
Forward algorithm
Beam search
trellis
backpointer
sequence decoding
maximum a posteriori estimation

Learn next

compute a two-state example by listing all paths, then reproduce the result with a trellis. Compare max-based Viterbi updates with sum-based forward updates. Finally identify which assumptions make paths ending in the same state interchangeable for future scoring.

Sources

Sources: Jurafsky and Martin, Speech and Language Processing, Appendix A, Viterbi recurrence and backtrace: https://web.stanford.edu/~jurafsky/slp3/A.pdf . G. David Forney Jr., The Viterbi Algorithm, 1973, finite-state sequence-estimation formulation: https://www2.isye.gatech.edu/~yxie77/ece587/viterbi_algorithm.pdf . The two-state calculation was independently executed in Python; Ridge Labels is fictional.

Previous: Visualization (graphics) Next: Vivification