Viterbi algorithm: Difference between revisions

Revision as of 18:44, 17 October 2005

Revision as of 04:39, 21 October 2005

Line 1:

The '''Viterbi algorithm''', named after its developer [[Andrew Viterbi]], is a [[dynamic programming]] [[algorithm]] for finding the most [[likelihood function|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 probability of a sequence of observed events.

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-up]] modems, satellite and deep-space communications, and [[802.11]] wireless LANs. It is now also commonly used in [[information theory]], [[speech recognition]], [[keyword spotting]], [[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.

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 depend only on the observed event at point ''t'', and the most likely sequence at point ''t'' − 1. These assumptions are all satisfied in a first-order hidden Markov model.

Line 11:

{{HMM example}}

You talk to your friend three days in a row and discover that on the first day he went for a walk, on the second day he went shopping, and on the third day he cleaned his apartment. You have two questions: What is the overall probability of this sequence of observations? And what is the most likely sequence of rainy/sunny days that would explain these observations? The first question is answered by the forward algorithm; the second by the Viterbi algorithm. These two algorithmalgorithms are structurally so similar (in fact, they are both instances of the same abstract algorithm) that they can be implemented in a single function:

def forward_viterbi(y, X, sp, tp, ep):