Viterbi algorithm: Difference between revisions

Revision as of 19:50, 2 June 2003

Revision as of 03:47, 8 December 2003

Line 1:

The '''Viterbi [[algorithm]]''', named after its developer [[Andrew Viterbi]], is a way to find the most [[likelihood|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 algrothimalgorithm 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.