The Viterbi algorithm is a dynamic programming algorithm that identifies the most likely sequence of hidden states that could have produced a given sequence of observed events. The resulting sequence is often called the Viterbi path. It is most commonly applied to hidden Markov models (HMMs), where the underlying states are not directly observable but influence the observations. For instance, a doctor observing a patient's symptoms over several days could use the algorithm to infer the most probable sequence of underlying health conditions that caused those symptoms.
The algorithm has found universal application in decoding convolutional codes used in CDMA and GSM digital cellular networks, dial-up modems, satellite and deep-space communications, and 802.11 wireless LANs. It is also widely used in speech recognition, speech synthesis, speaker diarization, keyword spotting, computational linguistics, and bioinformatics. In speech-to-text systems, the acoustic signal serves as the observed sequence, and the text string is the hidden cause; the Viterbi algorithm finds the most likely text given the acoustic signal.
History
The Viterbi algorithm is named after Andrew Viterbi, who proposed it in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. 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 was introduced to natural language processing as a method for part-of-speech tagging as early as 1987.
The terms "Viterbi path" and "Viterbi algorithm" have become standard for dynamic programming approaches to maximization problems involving probabilities. In statistical parsing, a dynamic programming algorithm can discover the single most likely context-free derivation (parse) of a string, commonly called the "Viterbi parse." Another application is target tracking, where the algorithm computes the track that assigns maximum likelihood to a sequence of observations.
Algorithm Overview
Given a hidden Markov model with a set of hidden states S, a set of possible emissions (observations) M, and a sequence of T observations o0, o1, ..., oT-1, the Viterbi algorithm finds the most likely sequence of hidden states that could have produced those observations. At each time step t, the algorithm solves the subproblem where only observations up to ot are considered.
Two matrices of size T × |S| are constructed. The matrix Pt,s contains the maximum probability of ending up at state s at observation t, out of all possible sequences of states leading up to it. The matrix Qt,s tracks the previous state that was used before s in this maximum probability state sequence.
Let πs and ar,s be the initial and transition probabilities respectively, and let bs,o be the probability of observing o at state s. Then the values of P are given by a recurrence relation. At time t = 0, Pt,s equals πs multiplied by bs,o0. For t > 0, Pt,s equals the maximum over all previous states r of (Pt-1,r × ar,s × bs,ot). After filling the matrices, the algorithm traces back from the state with the highest probability at the final time step using the Q matrix to reconstruct the most likely state sequence.
Applications in Communications
The algorithm is a cornerstone of modern digital communications. It decodes convolutional codes, which are error-correcting codes used in many wireless and wired systems. In CDMA and GSM cellular networks, the Viterbi algorithm helps recover transmitted data despite noise and interference. Dial-up modems, satellite links, and deep-space communication systems also rely on it. The 802.11 wireless LAN standard incorporates Viterbi decoding for reliable data transmission.
The algorithm's efficiency comes from its dynamic programming nature: it avoids exhaustive enumeration of all possible state sequences by storing intermediate probabilities and using the principle of optimality. This makes it feasible to decode long sequences in real time, even on resource-constrained devices.
Applications in Speech and Language
In speech recognition, the Viterbi algorithm aligns acoustic features with phonetic or word models. The acoustic signal is the observed sequence, and the text string is the hidden cause. The algorithm finds the most likely string of text given the acoustic signal, enabling accurate transcription. It is also used in speech synthesis to select the most natural sequence of speech units, and in speaker diarization to determine who spoke when.
In computational linguistics, the algorithm is applied to part-of-speech tagging, where hidden states are grammatical categories and observations are words. It also supports statistical parsing, where it finds the most likely parse tree for a sentence. In bioinformatics, it helps align biological sequences and predict gene structures, treating DNA or protein sequences as observations and functional elements as hidden states.
Related Techniques
The Viterbi algorithm is closely related to other dynamic programming methods, such as the forward-backward algorithm, which computes probabilities over all possible state sequences rather than just the most likely one. It also shares conceptual foundations with Beam Search, a heuristic search technique used in sequence generation. In modern Machine learning and Artificial intelligence systems, especially those involving Sequence-to-Sequence (Seq2Seq) models and Large language models, beam search is often preferred over exact Viterbi decoding due to the large state spaces involved.
Despite the rise of Neural network approaches, the Viterbi algorithm remains relevant in hybrid systems. For example, it can be used to decode outputs from Neural network acoustic models in speech recognition, or to enforce structural constraints in Natural language processing tasks. Its mathematical clarity and efficiency ensure its continued use in both classical and contemporary applications.