Viterbi algorithm

Lore & Background

It has a history of multiple invention, with at least seven independent discoveries, including those by Viterbi, Needleman and Wunsch, and Wagner and Fischer. It is also commonly used in speech recognition, speech synthesis, diarization, keyword spotting, computational linguistics, and bioinformatics. In statistical parsing, a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, commonly called the 'Viterbi parse'. Another application is in target tracking, where the track is computed that assigns a maximum likelihood to a sequence of observations.

Reader's Guide

The Viterbi algorithm is significant because it provides an efficient method for finding the most probable sequence of hidden states in a hidden Markov model, given a sequence of observations. Its recurrence relation uses initial probabilities, transition probabilities, and emission probabilities to compute the maximum probability path, storing results in matrices P and Q for backtracking. The algorithm has been independently discovered at least seven times, highlighting its fundamental importance across disciplines. In digital communications, it is essential for decoding convolutional codes in technologies such as CDMA, GSM, satellite, and deep-space communications. In natural language processing, it enables part-of-speech tagging and statistical parsing. In bioinformatics, it is used for sequence analysis. The Viterbi path and Viterbi algorithm have become standard terms for dynamic programming applications to maximization problems involving probabilities. Its legacy lies in its broad applicability to problems where hidden causes must be inferred from observable data, from speech recognition to target tracking.

Did You Know?

• The algorithm has a history of multiple invention, with at least seven independent discoveries.

The Algebraic Skeleton of the Viterbi Semiring

The Viterbi semiring is formally a five-tuple comprising a carrier set, two binary operations, and two identity elements. The carrier set is the closed interval from zero to one, encompassing every possible probability value. Where ordinary algebra would use addition, this structure instead employs the maximum function: given any two values in the interval, their 'sum' is simply whichever one is larger. The multiplicative operation is the familiar product of real numbers. Zero serves as the additive identity, since taking the maximum of zero and any other interval element returns that element unchanged. One is the multiplicative identity, leaving any value it multiplies untouched. Zero also acts as the absorbing element for multiplication, annihilating whatever it meets. Because real-number multiplication is commutative, this particular semiring is commutative as well, and every standard semiring axiom—associativity of both operations, commutativity of both, and the distributive law of multiplication over addition—holds without exception.

Idempotence and the Built-in Ordering

A defining feature of this structure is that its additive operation is idempotent: combining any element with itself through the max operation simply returns that same element. This property carries a deep consequence—it induces a natural partial order across the entire carrier set. Concretely, one value is deemed no greater than another if and only if their max-combination equals the larger of the two. This ordering is not imposed externally; it emerges directly from the algebraic structure itself. Furthermore, because every element lies between zero and one, multiplying any two of them yields a result no greater than either factor. This gives rise to what the literature calls multiplicative subidempotence: for any value in the interval, the max of that value and its own square equals the value itself. In practical terms, extending a path by an additional step never increases its accumulated probability, which is precisely the behavior expected when chaining independent probabilistic events together.

The Bridge to Tropical Algebra

The Viterbi semiring is not an isolated curiosity; it occupies a tight algebraic relationship with the tropical, or min-plus, semiring widely employed in shortest-path and other optimization problems. The connection is established through a logarithmic transformation. Mapping each probability to its negative natural logarithm converts the operation of maximizing probabilities into minimizing a cost, and the multiplication of probabilities along a path into the addition of log-costs. In other words, the entire (max, ×) structure is isomorphic to a (min, +) structure under this mapping. This isomorphism means that any algorithm naturally expressed in the Viterbi semiring—such as identifying the highest-probability state sequence—possesses a direct counterpart in the tropical world of minimizing accumulated costs. The two perspectives are mathematically identical, merely rendered in different algebraic languages, and this duality allows techniques and insights to flow freely between probabilistic inference and combinatorial optimization.

The Dynamic Programming Engine

The Viterbi semiring supplies the precise algebraic machinery that makes dynamic programming effective for path-finding problems. In a dynamic programming setting, the additive operation (max) functions as the selection mechanism: at each decision point, it picks the best-scoring alternative among competing options. The multiplicative operation (×) functions as the accumulation mechanism: it chains together the weights of individual steps to produce a total score for a complete path. The classic Viterbi algorithm, which identifies the most probable sequence of hidden states in a probabilistic model, is precisely a dynamic programming computation carried out over this (max, ×) structure. The critical efficiency gain arises from the distributive law: rather than enumerating every possible state sequence and computing its total probability, the algorithm applies the semiring's distributivity to merge sub-solutions at each step, retaining only the best partial result for each state. This collapses what would otherwise be an exponential search into a polynomial-time procedure.