The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. The forward algorithm is a closely related algorithm for computing the probability of a sequence of observed events.
The Viterbi algorithm was originally conceived as an error-correction scheme for noisy digital communication links, finding universal application in decoding the convolutional codes used in CDMA and GSM digital cellular, dial modems, satellite and deep-space communications, and 802.11 wireless LANs. It is now also commonly used in information theory, speech recognition, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text speech recognition, the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.
The algorithm is not general; it makes a number of assumptions. First, both the observed events and hidden events must be in a sequence. This sequence often corresponds to time. Second, these two sequences need to be aligned, and an observed event needs to correspond to exactly one hidden event. Third, computing the most likely hidden sequence up to a certain point t must only depend on the observed event at point t, and the most likely sequence at point t − 1. These assumptions are all satisfied in a first-order hidden Markov model.
The terms "Viterbi path" and "Viterbi algorithm" are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observation. For example, in stochastic parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is sometimes called the "Viterbi parse".
A concrete example
T = {}
for state in X:
## prob. V. path V. prob.
T[state] = (sp[state], [state], sp[state])
for output in y:
U = {}
for next_state in X:
total = 0
argmax = None
Extensions
With the algorithm called Iterative Viterbi Decoding one can find the subsequence of an observation that matches best (on average) to a given HMM. Iterative Viterbi Decoding, developed by M.C.Silaghi (1998) works by iterating the call to a modified Viterbi algorithm, reestimating the score for a filler until convergence.
An alternate algorithm, called the Lazy Viterbi algorithm, has been recently proposed. This works by not expanding any nodes until it really needs to, and usually manages to get away with doing a lot less work (in software) than the ordinary Viterbi algorithm for the same result - however, it is not so easy to parallelize in hardware.
References
- Andrew J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 13(2):260–267, April 1967. (The Viterbi decoding algorithm is described in section IV.)
- G. D. Forney. The Viterbi algorithm. Proceedings of the IEEE 61(3):268–278, March 1973.
- L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2):257–286, February 1989. (Describes the forward algorithm and Viterbi algorithm for HMMs).
- J Feldman, I Abou-Faycal and M Frigo. A Fast Maximum-Likelihood Decoder for Convolutional Codes.