next up previous
Next: Asynchronous IOHMMs Up: Input-Output HMMs Previous: Markov Switching Models

EM for HMMs and IOHMMs

 

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.


next up previous
Next: Asynchronous IOHMMs Up: Input-Output HMMs Previous: Markov Switching Models

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