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

Hidden Markov Models

 

In this section we remind the reader of the basic definition of an HMM in a tutorial-like way. We formalize the assumptions that are made, and describe the basic elements of algorithms for HMMs. The algorithms to estimate the parameters for HMMs will be discussed in section 5.2 after we have generalized HMMs to Input-Output or conditional HMMs.


Since summarizes all the relevant past information, is generally called a state variable. Because of the above conditional independence property, the joint distribution of a whole sequence can be decomposed into the product

  
Figure 1: Probabilistic graphical model representing the independence assumptions of a Markov model of order 2: , where . Each variable depends directly only the previous two, and .

A probabilistic graphical model (or Bayesian network) [&make_named_href('', "node31.html#Pearl88","[40]"), &make_named_href('', "node31.html#whittaker90","[41]"), &make_named_href('', "node31.html#wermuth+lauritzen90","[42]"), &make_named_href('', "node31.html#wermuth+cox92","[43]"), &make_named_href('', "node31.html#Spiegelhalter93","[44]"), &make_named_href('', "node31.html#Buntine94","[45]"), &make_named_href('', "node31.html#Lauritzen96","[46]")] is a graphical representation of conditional independencies between random variables. The probabilistic graphical model corresponding to a Markov model of order 2 is shown in Figure 1. The figure shows a directed acyclic graph (DAG), in which each node corresponds to a random variable. An edge from variable A to variable B implies a direct influence of A on B. The absence of an edge between A and B implies a conditional independence between variables A and B, even though there may exist a path between A and B. Conditioning on intermediate variables on paths between A and B can make A and B independent.


See [&make_named_href('', "node31.html#Pearl88","[40]"), &make_named_href('', "node31.html#whittaker90","[41]"), &make_named_href('', "node31.html#wermuth+lauritzen90","[42]"), &make_named_href('', "node31.html#wermuth+cox92","[43]"), &make_named_href('', "node31.html#Spiegelhalter93","[44]"), &make_named_href('', "node31.html#Buntine94","[45]"), &make_named_href('', "node31.html#Lauritzen96","[46]")] for more formal definitions, and pointers to related literature on graphical probabilistic models and inference algorithms for them. Note that most of the models described in this paper can be cast in the framework of probabilistic graphical models. Despite the use of the word ``Bayesian'' in ``Bayesian networks'', in many cases the parameters of these models (such as HMMs) are estimated within the maximum likelihood framework.

In many Markovian models, the transition probabilities are assumed to be homogeneous, i.e., the same for all time steps. For example, for Markov models of order 1, , . With homogeneous models, the number of parameters is much reduced, and the model can be trained on sequences of certain lengths and generalize to sequences of different lengths. It makes sense to use such models on sequential data which shows temporal translation invariance. Other models, such as Input-Output (or conditional) HMMs (section 5), are inhomogeneous: different transition probabilities are used at different time steps. However, since the transition probabilities are not directly the parameters of the model but are instead obtained as a time-independent parametrized function of the previous state and other conditioning variables, the same advantages stated above apply, with more ability to deal with some of the changes in dynamics observed in different parts of the sequences.

In most applications, the state variable is discrete and the conditional distribution of the state variable at time t is given by a multinomial distribution. An exception to this approach is briefly discussed in section 7, with ``continuous-state HMMs'', more often called state-space models.




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

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