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.