Hidden Markov Models (HMMs) are statistical models of sequential data that have been used successfully in many applications in artificial intelligence, pattern recognition, and speech recognition. The focus of this paper is on HMMs and many extensions or related models which have been recently proposed, such as hybrids of HMMs with artificial neural networks [&make_named_href('', "node31.html#Bourlard93","[1]"), &make_named_href('', "node31.html#Bengio_book96","[2]")], Input-Output HMMs [&make_named_href('', "node31.html#Chrisman92AAAI","[3]"), &make_named_href('', "node31.html#Cacciatore-nips94","[4]"), &make_named_href('', "node31.html#Bengio+Frasconi-nips7-iohmms","[5]"), &make_named_href('', "node31.html#Meila96","[6]")], weighted transducers [&make_named_href('', "node31.html#Riley94","[7]"), &make_named_href('', "node31.html#Pereira94","[8]"), &make_named_href('', "node31.html#Mohri96","[9]")], variable-length Markov models [&make_named_href('', "node31.html#Ron94","[10]"), &make_named_href('', "node31.html#Singer96","[11]")], Markov switching models [&make_named_href('', "node31.html#Hamilton89","[12]")] and switching state-space models [&make_named_href('', "node31.html#Shumway91","[13]"), &make_named_href('', "node31.html#Zoubin96b","[14]")]. In this paper, we will sometimes call ``learning'' what is also called parameter estimation in statistics and system identification in control and engineering.
The models discussed here, which we call Markovian models,
can be applied to sequential data which have a certain
property described here.
First let us remind the reader that the
joint probability distribution
of a sequence of observations
can always be factored
as
It would be intractable in general to model sequential
data in which the conditional distribution
of an observed variable
at time t depends on all the details of the previous values
. However, the models discussed in this paper share
the property that they assume that the past sequence
can be summarized concisely, often using an unobserved
random variable called a state variable,
which carries all the information from
that
is useful to describe the distribution of the next
observation
.
The most common of these models are the HMMs, which are best known for their contribution to advances in automatic speech recognition in the last two decades. A good tutorial on HMMs in the context of speech recognition is [&make_named_href('', "node31.html#Rabiner89","[15]")]. Algorithms for estimating the parameters of HMMs have been developed in the 60's and 70's [&make_named_href('', "node31.html#Baum67","[16]"), &make_named_href('', "node31.html#Baum70","[17]"), &make_named_href('', "node31.html#Baum72","[18]")]. The application of HMMs to speech was independently proposed by [&make_named_href('', "node31.html#Baker75","[19]")] and [&make_named_href('', "node31.html#Jelinek76","[20]")], and popularized by [&make_named_href('', "node31.html#Levinson83","[21]")], [&make_named_href('', "node31.html#Rabiner86","[22]")], and [&make_named_href('', "node31.html#Rabiner89","[15]")]. An early review of alternative methods based on HMMs or related to HMMs, also for speech recognition, can be found in the collection of papers [&make_named_href('', "node31.html#WL90","[23]")]. Recently, HMMs have been applied to a variety of applications outside of speech recognition, such as handwriting recognition [&make_named_href('', "node31.html#Nag86","[24]"), &make_named_href('', "node31.html#Kundu88","[25]"), &make_named_href('', "node31.html#Matan92","[26]"), &make_named_href('', "node31.html#Ha93","[27]"), &make_named_href('', "node31.html#Schenkel93","[28]"), &make_named_href('', "node31.html#schenkel95","[29]"), &make_named_href('', "node31.html#Bengio_LeCun95","[30]")], pattern recognition in molecular biology [&make_named_href('', "node31.html#Churchill89","[31]"), &make_named_href('', "node31.html#Baldi94","[32]"), &make_named_href('', "node31.html#JCB:Baldi95t","[33]")], and fault-detection [&make_named_href('', "node31.html#Smyth94","[34]")]. The variants and extensions of HMMs discussed here also include applications to natural language processing [&make_named_href('', "node31.html#Guyon95","[35]"), &make_named_href('', "node31.html#Guyon96","[36]"), &make_named_href('', "node31.html#Singer96","[11]")], econometrics [&make_named_href('', "node31.html#Hamilton89","[12]"), &make_named_href('', "node31.html#Shumway91","[13]"), &make_named_href('', "node31.html#Garcia-Perron96","[37]")], time series, and signal processing.
Even though many of the
models presented here are probabilistic, the probability
distributions they represent should not be confused with the
true probability distribution from which the data might have
been generated.
The problem of estimating the parameters of the models discussed
in this paper can be framed as follows. We are given a class of
models
parametrized by the different values of parameters
,
i.e., to each value of
corresponds a model, an element of
.
We are also given a training set
of N sequences of data sampled from an unknown distribution
,
and a criterion C for the quality
of a model for a set of data (i.e., a mapping from
to a real-valued scalar). The ultimate objective is to
choose a value of
(i.e., a model from
)
so as to maximize (or minimize) the
expected value of the criterion C on new data (with respect
to the true but unknown distribution
). The notation
P(.) or
used in this paper refers not to the true underlying
distribution
but to a model with parameters
.
For a general mathematical analysis of
the learning theory behind learning algorithms such
as those discussed here, see for example [&make_named_href('',
"node31.html#Vapnik95","[38]")].
These general results on statistical inference from
small-size samples help to support the view sometimes
presented in this paper that the models need not have
a probabilistic interpretation at every level, as
long as the criterion that is optimized during parameter
estimation is appropriate, and the capacity [&make_named_href('',
"node31.html#Vapnik95","[38]")]
of the models is not too large in comparison to the
number of training examples.
In some applications there is only one sequence
of observations
,
and the new data is simply a continuation of the training
data (e.g., time-series prediction, econometry). In
other applications there is a very large number
of training sequences of different lengths,
(e.g., thousands or tens of
thousands of sequences, as in speech recognition databases).
In some applications, the objective is to
model the distribution of a sequence,
e.g., in compression or clustering tasks one may want
to model
. In other applications, e.g., speech
recognition, DNA and other molecular biology sequences, the data
often consists of sequences of ``output'' variables
given ``input''
variables
, and the objective is to model
the conditional distribution
,
or to choose (``recognize'') a particular output
when the input
is given.
For example, in speech recognition, certain approaches are
based on modeling the distribution of acoustic sequences
given word sequences, whereas other approaches are based
on modeling the reverse (words given acoustics). In econometrics,
one may wish to predict the distribution of certain economical variables
of interest while observing other variables.
Note that in some of these applications the input and output
sequences do not have the same length. For example,
in speech recognition applications, word sequences are shorter
then acoustic sequences.
The next two sections of this paper review the basic elements of traditional HMMs (section 2) and their application to speech recognition (section 3). The remaining sections describe extensions of HMMs and Markovian models related to HMMs, i.e., hybrids with Artificial Neural Networks in section 4, Input-Output HMMs in section 5 (including Markov switching models in section 5.1, asynchronous Input-Output HMMs in section 5.3), generalizations of HMMs called weighted transducers in section 6 (useful to combine many Markovian models), and finally, state space models (Markovian models with continuous state) in section 7. A brief overview of the application of the EM algorithm to HMMs and IOHMMs is given in section 5.2.