Viterbi algorithm

The Viterbi algorithm is a dynamic programming algorithm to determine the most likely sequence of hidden states for a given Hidden Markov Model (HMM) and an observed sequence of symbols. This state sequence is also referred to as Viterbi path.

It was developed in 1967 by Andrew J. Viterbi decoding of convolutional codes, it was as a side product during the analysis of the error probability of the convolutional code from. GD Forney 1972 deduced the optimum receiver for distorted and disturbed channels ago. The Viterbi algorithm is used today, for example in mobile phones or wireless LANs for error correction of the radio transmission, as well as in hard disks because when recording on the magnetic disks are also formed transmission error.

The algorithm is widely used in communications engineering and computer science: The information theory, bioinformatics, speech recognition and computational linguistics often use the Viterbi algorithm.

Markov model

Given an HMM with

  • - Amount of the hidden states
  • - Alphabet of observable symbols (emissions)
  • - State transition matrix
  • - Observation matrix
  • - Initial probability distribution

Task

Is the observed sequence of symbols. It is the most likely state sequence are calculated. So that the sequence of hidden states that maximizes the value of all sequences of length, which is the probability that the model is run by the production conditions at the output.

According to the rules for computing conditional probabilities apply:

In addition, since does not depend on, the following applies:

Are now accepted for the actual calculation of two different types of variables - and - used:

In the maximum composite likelihood is saved at the point in the observation of the prefix to be run by a state sequence of length and end in the state:

The variable, however, remembers for each time point and each state which predecessor state was involved in the maximum generation.

Algorithm

The variables and can be determined recursively:

Complexity

The table of required memory, the matrix is of the same extent. For each cell of the two matrices is optimized over alternatives, so the term is.

In order to halve the storage space of the path alternatively even after the termination by backtracking in the matrix of all - that is, without the additional variables - can be determined. Since, however, caused the calculation of any extra effort in practice, the required computing time is slightly extended in the backtracking approach.

Applications

, The Viterbi algorithm is the optimum algorithm for decoding convolutional codes in accordance with the block error rate ( Maximum Likelihood Sequence Estimation ). The optimal in terms of the symbol error rate decoding algorithm is the BCJR algorithm.

As you can see from the description of the algorithm, it can be used almost anywhere to recognize patterns. This is a wide field, as living beings must constantly interpret sensory stimuli and classify from the already learned these signals. The Viterbi algorithm does exactly also and is thus an important component of artificial intelligence.

An important priority is also the algorithm in bioinformatics, because it can be concluded, among others, the actual sequence of a DNA segment for possible hidden states based on the Viterbi algorithm. May be examined, for example, if it is present a sequence probably is a particular structural motif ( CpG island, the promoter, ...) or not. Advantage of this recursive algorithm is in this case the linearly rising with the sequence length effort in contrast to the exponential cost of the underlying Hidden Markov Model.

806536
de