Skip to content
Last Dictionary
Plane
Machine LearningMathematics & StatisticsVision, Speech & Perception

Viterbi algorithm

noun/vit-ER-bee/Also: Viterbi decoding, Viterbi path, Viterbi decoder

In plain wordsA method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination.

  1. The standard decoding procedure for a hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds. or linear-chain conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time.: a dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step. recursion that, for a given observation sequence, returns the single assignment of hidden states with the highest joint probability (the Viterbi path). Working left to right, it records for every time step and state the probability of the best path ending there, computed from the best predecessor's score times the transition and emission probabilities, and keeps a back-pointer to that predecessor; tracing the pointers back from the best final state recovers the path. This costs time proportional to T·N² for T steps and N states, instead of the N^T needed to enumerate all paths, and is normally run with log probabilities to avoid underflow. It is the max-product counterpart of the sum-product forward algorithm, and was the decoding core of HMM-based speech recognitionspeech recognition, n.: Technology that turns spoken words into written text, as when a phone transcribes a voice message or captions appear automatically under a video., part-of-speech taggingpart-of-speech tagging, n.: Labeling each word in a sentence with its grammatical role — noun, verb, adjective and so on — as in 'Time (noun) flies (verb) like (preposition) an arrow'., gene finding and digital receivers for mobile phones and space probes.

    We replaced greedy per-token tagging with Viterbi decoding so the output always respects the transition constraints.

δt(j)=max⁡i[δt−1(i) aij] bj(ot)\delta_t(j) = \max_{i} \big[ \delta_{t-1}(i)\, a_{ij} \big]\, b_j(o_t)

Origin

Published by Andrew Viterbi in 1967 in the IEEE Transactions on Information Theory as an asymptotically optimal decoder for convolutional error-correcting codes. Jim Omura (1969) recognized it as dynamic programming, and G. David Forney Jr.'s 1973 tutorial, titled 'The Viterbi Algorithm', presented it as the optimal estimator of the state sequence of any finite-state Markov process observed in memoryless noise, spreading it beyond coding. Closely related dynamic programs arose independently in speech recognition and sequence alignment.

Usage note

Viterbi decoding returns the single best whole sequence, which can differ from picking the most probable state at each position separately (posterior decoding with forward–backward). In neural text generation, where exact search over sequences is intractable, beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility. plays the analogous role.

Related

See also
  • hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
  • dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step.
  • conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time.
  • beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility.
  • speech recognitionspeech recognition, n.: Technology that turns spoken words into written text, as when a phone transcribes a voice message or captions appear automatically under a video.
  • decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones.
Contrast with
  • beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility.
  • greedy decodinggreedy decoding, n.: The simplest way for a language model to write: always pick the single most likely next word. It is fast and predictable but can produce dull or repetitive text.

Sources

  1. Viterbi, A. J. (1967). Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE Transactions on Information Theory 13(2), 260–269.
  2. Forney, G. D., Jr. (1973). The Viterbi Algorithm. Proceedings of the IEEE 61(3), 268–278.

Mentioned in

conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time., hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds., belief propagationbelief propagation, n.: A way for a network of uncertain quantities to reach conclusions by having each node pass short messages to its neighbors about what it currently believes, until the beliefs settle down.