In this section we will sketch the application of the EM
(Expectation-Maximization) algorithm [&make_named_href('',
"node31.html#Dempster77","[52]")] to
HMMs [&make_named_href('',
"node31.html#Baum67","[16]"), &make_named_href('',
"node31.html#Baum70","[17]"), &make_named_href('',
"node31.html#Baum72","[18]")] and IOHMMs. The papers by Baum et al. present
a special case of the EM algorithm applied to discrete emissions HMMs, but
were written before the general version of the EM algorithm was
described [&make_named_href('',
"node31.html#Dempster77","[52]")]. Here
will represent a set of input
sequences of the form
(each may be of a different length
). Similarly,
is a corresponding set of output sequences of the
form
, and
is a corresponding set of state sequences
. For the presentation of EM in this section, we will consider the
case of a conditional distribution
(whereas usually
only the unconditional case is described), since it will give results both for
HMMs and IOHMMs. In the case of HMMs, there are simply no such conditioning
variables so all the x's (
) can be ignored, and the
``output'' sequence
is the observed sequence. Apart from this
distinction, the mathematical formulation of HMMs and IOHMMs are identical,
but the practical consequences on the model are deep.
See also [&make_named_href('',
"node31.html#Lindgren78","[94]")] for a treatment of parameter estimation
with EM, for switching regressions (which are like IOHMMs).
The basic idea of the EM algorithm is to use a hidden variable Q whose joint
distribution with the observed (output) variable Y is ``simpler'' than the
marginal distribution of the observed variable itself. In HMMs and IOHMMs,
the hidden variable is the state path
. We have already seen in
section 2.1 in the case of HMMs that
is simpler
to compute and represent than
.
Because the hidden variable is not given, the EM algorithm looks at the
expectation (over all values of the hidden variable) of the log-probability of
the joint distribution. This expectation, called the auxiliary
function, is conditioned on the previous values of the parameters,
, and on the training observations.
The EM algorithm is an iterative algorithm successively
applying the E-Step and the M-step.
The E-Step of the algorithm
consists in forming this conditional expectation:
where
is the set
of N output sequences, and similarly
and
are respectively sets of N input and
N state sequences. It is supposed that the sequences are
sampled i.i.d. from a distribution
but we are only really interested in modeling
or
.
The M-Step consists in finding the parameters
which maximize the auxiliary function. At
the
iteration,
It can be shown [&make_named_href('',
"node31.html#Dempster77","[52]")] that an increase of U brings
an increase of the likelihood, and this algorithm converges
to a local maximum of the likelihood
.
When the above maximization cannot be done exactly (but U increases
at each iteration), we have a GEM (Generalized EM) algorithm.
The maximization can in general be done by solving
the system of equations
For HMMs, IOHMMs and state space models
with simple enough emission and transition distributions,
this can be done analytically. We will discuss here the
case of discrete states, where the expectation
in equation 14 corresponds to a sum over
the values of the state variable, and the solution
of equation 16 can be
obtained efficiently with recursive
algorithms. To see this, we will first rewrite the
joint probability of states and observations by introducing indicator
variables
with value 1 when the state variable
at time t takes the value i,
and 0 otherwise:
The overall joint log-probability for the whole training set is a sum over the training sequences of the above sums. Moving the expectation in equation 14 inside these sums, and ignoring the p indices for sequences within the training set (which would make the notation very heavy):
Note how in this expression the maximization of U with respect
to the parameters
of the emission and transition probabilities
have been completely decoupled in two separate sums.
To simplify the notation (and because they are often ignored in practice by
forcing all state sequences to start from the same state) we have ignored
the initial state probabilities. In the M-Step, the problem becomes one of
simple likelihood maximization for each of the different types
of distributions, but with weights for each the probabilities
in the above sums.
These weights are the state posterior probabilities
and the transition posterior probabilities
Let us now see how these posterior probabilities, which we will note
and
[4]
to lighten the notation, can be computed with the
Baum-Welch forward and backward recursions [&make_named_href('',
"node31.html#Baum67","[16]"), &make_named_href('',
"node31.html#Baum70","[17]"), &make_named_href('',
"node31.html#Baum72","[18]")].
We have already introduced the forward recursion
(equations 5 and 11), which
yields
recursively.
Note that
can be normalized
to perform the filtering operation (equation 13).
Using the two Markov assumptions (the equivalent of equations 1 and 2 conditioned on the input sequence), the Baum-Welch backward recursion can be obtained:
By multiplying the results of the forward and backward recursion (equations 5 and 17) and normalizing by the output sequence probability, we obtain the state posteriors (i.e., the smoothed estimates of the state distribution):
Similarly, the transition posteriors can be obtained from these two recursions and from the emission and transition probabilities as follows:
Some care must be taken in performing the forward and backward recursions in order to avoid numerical over or under flow (usually this is accomplished by performing the computation in a logarithmic scale with a small base).
The details of the parameter update algorithm depend on the particular form of the emission and transition distributions. If they are discrete, in the exponential family, or a mixture thereof, then exact (and simple) solutions for the M-Step exist (by using a weighted form of the maximum likelihood solutions for these distributions). As a simple example, we will provide the re-estimation formulae for unconditional multinomial distributions for both transitions and emissions (as in many HMM applications). The formulae for other cases can be easily derived from the solution of equation 16. See also for example [&make_named_href('', "node31.html#Rabiner86","[22]"), &make_named_href('', "node31.html#Rabiner89","[15]")] for other common distributions.
Let us first consider unconditional (multinomial)
transition probabilities parametrized
by
[0]
(with indices i and j running across
the possible values of the state variable
),
and the constraint
.
The transition parameters at iteration
of the
EM algorithm can be obtained from the parameters
iteration k as follows, using the transition
posteriors from equation 19:
Note this corresponds to a simple normalization of the transition posteriors. Like before, p represents the index over training sequences and it has not been attached to the variables on the right hand side.
The case of unconditional multinomial
emission distributions is similar: let us consider
parameters
[0]
with the constraint
.
The emission parameters at iteration
of
the EM algorithm can be obtained from the parameters
at iteration k as follows, using
the state posteriors from equation 18:
where
is the indicator function, whose value is 1 when e
is true and 0 otherwise. Note again this corresponds to a simple
normalization of the transition posteriors (for the case when
is observed), or to a weighted frequency count of
the occurence
while in state
.
For distributions such as those incorporating an artificial neural network to compute conditional discrete probabilities or the conditional mean of a Gaussian, one can use a GEM algorithm or the maximization of the observations likelihood by numerical methods such as gradient ascent. Note that maximizing the auxiliary function U by gradient ascent is equivalent to maximizing the likelihood by gradient ascent. This can be shown by noting that the quantities computed in the backward pass are in fact gradients of the likelihood with respect to the quantities computed in the forward pass:
This interesting observation is useful in the computation of the parameter gradient (equation 10), for sophisticated models, such as those using parametrized non-linear functions, e.g., with artificial neural networks, section 4.
Another problem that may occur with certain models, when the representation of the state variable is more complicated than in ordinary HMMs or IOHMMs, e.g., with multiple state variables, is that the exact E-Step computation may be too expensive because at each time step the hidden variable can take many values. See for example the models discussed in section 7.1.