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.