Viterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events.
The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs.
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 Viterbi algorithm is named after Andrew Viterbi, who proposed it in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links.
[2] It has, however, a history of multiple invention, with at least seven independent discoveries, including those by Viterbi, Needleman and Wunsch, and Wagner and Fischer.
[3] It was introduced to natural language processing as a method of part-of-speech tagging as early as 1987.
Viterbi path and Viterbi algorithm have become standard terms for the application of dynamic programming algorithms to maximization problems involving probabilities.
, the Viterbi algorithm finds the most likely sequence of states that could have produced those observations.
If it is known which state transitions have non-zero probability, an improved bound can be found by iterating over only those
A doctor wishes to determine whether patients are healthy or have a fever.
The patients may report that they either feel normal, dizzy, or cold.
It is believed that the health condition of the patients operates as a discrete Markov chain.
From past experience, the probabilities of this model have been estimated as: In this code, init represents the doctor's belief about how likely the patient is to be healthy initially.
The transition probabilities trans represent the change of health condition in the underlying Markov chain.
In this example, a patient who is healthy today has only a 30% chance of having a fever tomorrow.
The emission probabilities emit represent how likely each possible observation (normal, cold, or dizzy) is, given the underlying condition (healthy or fever).
The probability that a patient will be healthy on the first day and report feeling normal is
Similarly, the probability that a patient will have a fever on the first day and report feeling normal is
This suggests it is more likely that the patient was healthy for both of those days, rather than having a fever and recovering.
Furthermore, there exists a sequence of states ending on "fever", of which the probability of producing the given observations is 0.01512.
The operation of Viterbi's algorithm can be visualized by means of a trellis diagram.
A generalization of the Viterbi algorithm, termed the max-sum algorithm (or max-product algorithm) can be used to find the most likely assignment of all or some subset of latent variables in a large number of graphical models, e.g. Bayesian networks, Markov random fields and conditional random fields.
With an algorithm called iterative Viterbi decoding, one can find the subsequence of an observation that matches best (on average) to a given hidden Markov model.
This algorithm is proposed by Qi Wang et al. to deal with turbo code.
[9] Iterative Viterbi decoding works by iteratively invoking a modified Viterbi algorithm, reestimating the score for a filler until convergence.
While the original Viterbi algorithm calculates every node in the trellis of possible outcomes, the Lazy Viterbi algorithm maintains a prioritized list of nodes to evaluate in order, and the number of calculations required is typically fewer (and never more) than the ordinary Viterbi algorithm for the same result.
SOVA differs from the classical Viterbi algorithm in that it uses a modified path metric which takes into account the a priori probabilities of the input symbols, and produces a soft output indicating the reliability of the decision.
The first step in the SOVA is the selection of the survivor path, passing through one unique node at each time instant, t. Since each node has 2 branches converging at it (with one branch being chosen to form the Survivor Path, and the other being discarded), the difference in the branch metrics (or cost) between the chosen and discarded branches indicate the amount of error in the choice.
This cost is accumulated over the entire sliding window (usually equals at least five constraint lengths), to indicate the soft output measure of reliability of the hard bit decision of the Viterbi algorithm.
