The Viterbi algorithm is a dynamic programming algorithm that finds the most likely sequence of hidden events that would explain a sequence of observed events. The result of the algorithm is often called the Viterbi path. It is most commonly used with hidden Markov models (HMMs). For example, if a doctor observes a patient's symptoms over several days (the observed events), the Viterbi algorithm could determine the most probable sequence of underlying health conditions (the hidden events) that caused those symptoms. 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. It is also commonly used in speech recognition, speech synthesis, diarization, keyword spotting, computational linguistics, and bioinformatics. For instance, in speech-to-text (speech recognition), the acoustic signal is the observed sequence, and a string of text is the "hidden cause" of that signal. The Viterbi algorithm finds the most likely string of 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, however, 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 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. For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is 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.
Algorithm Given a hidden Markov model with a set of hidden states S {\displaystyle S} , a set of possible emissions (observations) M, and a sequence of T {\displaystyle T} observations o 0 , o 1 , … , o T − 1 {\displaystyle o_{0},o_{1},\dots ,o_{T-1}} , the Viterbi algorithm finds the most likely sequence of hidden states that could have produced those observations. At each time step t {\displaystyle t} , the algorithm solves the subproblem where only the observations up to o t {\displaystyle o_{t}} are considered. Two matrices of size T × | S | {\displaystyle T\times \left|{S}\right|} are constructed:
P t , s {\displaystyle P_{t,s}} contains the maximum probability of ending up at state s {\displaystyle s} at observation t {\displaystyle t} , out of all possible sequences of states leading up to it.
Q t , s {\displaystyle Q_{t,s}} tracks the previous state that was used before s {\displaystyle s} in this maximum probability state sequence. Let π s {\displaystyle \pi _{s}} and a r , s {\displaystyle a_{r,s}} be the initial and transition probabilities respectively, and let b s , o {\displaystyle b_{s,o}} be the probability of observing o {\displaystyle o} at state s {\displaystyle s} . Then the values of P {\displaystyle P} are given by the recurrence relation
… excerpt ends here. Continue reading the full article.
