Content deleted Content added
→A concrete example: rm redundant link |
m references and external links |
||
Line 1:
The '''Viterbi algorithm''', named after its developer [[Andrew Viterbi]], is a [[dynamic programming]] [[algorithm]] for finding the most [[likelihood|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 model]]s. The '''forward algorithm''' is a closely related algorithm for computing the
The Viterbi algorithm was originally conceived as an [[error-correction]] scheme for noisy digital communication links, finding universal application in decoding the [[convolutional code]]s 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]], [[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.
Line 90:
This reveals that the total probability of <code>['walk', 'shop', 'clean']</code> is 0.033612 and that the Viterbi path is <code>['Sunny', 'Rainy', 'Rainy, 'Rainy']</code>. The Viterbi path contains four states because the third observation was generated by the third state and a transition to the fourth state. In other words, given the observed activities, it was most likely sunny when your friend went for a walk and then it started to rain the next day and kept on raining.
==References==
* Andrew J. Viterbi. Error bounds for convolutional codes and an asymtotically 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).
==External links==
* [http://www.ieee.org/organizations/history_center/oral_histories/transcripts/viterbi.html An interview with Andrew Viterbi, including some background on the discovery of the Viterbi algorithm]
[[Category:Algorithms]]
| |||