next up previous
Next: Speech Recognition with HMMs Up: Hidden Markov Models Previous: Parameter Estimation

The Viterbi Algorithm

In several applications of HMMs (as in speech recognition and molecular biology applications, for example), the hidden state variable is associated with a particular meaning (e.g., phonemes and words, for speech recognition). To each state corresponds a classification label (and several states are grouped together with the same label, as in Figure 4). To each state sequence corresponds a sequence of classification labels (e.g., words, characters, phonemes). It is therefore useful, given an observed sequence , to infer the most likely state sequence corresponding to it. This is achieved with algorithms that perform the following maximization:

The Viterbi algorithm [&make_named_href('', "node31.html#Viterbi67","[56]")] finds the above maximum with a relatively efficient recursive solution: its computational cost is proportional to the number of non-zero transitions probabilities times the sequence length. This is in fact an application of Bellman's dynamic programming algorithm [&make_named_href('', "node31.html#Bellman57","[57]")]. First let us define

which can be computed recursively as follows, using the Markov conditional independence assumptions (equations 1 and 2):

 

with the initialization . We therefore obtain at the end of the sequence . If the argmax in the above recursion is kept, then the optimal can also be obtained in a backward recursion, starting from , with . Like the forward phase, the computation cost of the Viterbi algorithm is O(T m) (where m is the number of non-zero transition probabilities at each time step). Note the structural similarity of equation 6 with the forward phase (equation 5): the sum has simply been replaced by a max operation.

  
Figure 4: This figure shows part of the topology of an HMM which may be used for recognizing connected words, with groups of state values (represented by nodes here) associated with a meaning, e.g., a word label. A word HMM is represented by an oval that groups the corresponding set of states. A state sequence also corresponds to a sequence of words. Transition probabilities between word models are given by the language model.

When the number of non-zero transition probabilities m is large, other graph search algorithms may be used in order to look for the optimal state sequence. Some are optimal (e.g., some instances of the search [&make_named_href('', "node31.html#Nilsson-71","[58]")]) and others are approximate but faster (e.g., the beam search [&make_named_href('', "node31.html#Ney92","[59]")]). For very large HMMs (e.g., for speech recognition with several tens of thousands of words), even these methods are not efficient enough. The methods that are employed for such large HMMs are based on progressive search, performing multiple passes. See [&make_named_href('', "node31.html#Alleva93","[60]"), &make_named_href('', "node31.html#Murveit93","[61]"), &make_named_href('', "node31.html#Aubert94","[62]"), &make_named_href('', "node31.html#Kubala94","[63]")] for more details.


next up previous
Next: Speech Recognition with HMMs Up: Hidden Markov Models Previous: Parameter Estimation

Yoshua Bengio
Tue Oct 7 08:34:36 EDT 1997