Encyclopedia > Viterbi algorithm

  Article Content

Viterbi algorithm

The Viterbi algorithm, named after its developer Andrew Viterbi[?], is a way to find the most likely sequence of hidden states (or causes) that result in a sequence of observed events. It is commonly used in information theory, speech recognition and computational linguistics. 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 algrothim finds this hidden cause if it is 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.

More technically, the Viterbi algorithm is a dynamic programming algorithm to find the hidden sequence of observations given an observed sequence of observations in a hidden Markov model. The resulting path is called the Viterbi path.

Recently, the terms "Viterbi path" and "Viterbi algorithm" have been applied to related dynamic programming algorithms, such as parsing, as well.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Monty Woolley

... on Broadway in 1936. He was typecast as the wasp-tongued, supercillious sophisticate. His most famous role is that of the cranky professor forced to stay immobil ...

 
 
 
This page was created in 23.9 ms