next up previous
Next: Hidden Markov Models Up: Markovian Models for Sequential Previous: Markovian Models for Sequential

Introduction

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.


next up previous
Next: Hidden Markov Models Up: Markovian Models for Sequential Previous: Markovian Models for Sequential

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