10
$\begingroup$

Can somebody clarify how hidden Markov models are related to expectation maximization? I have gone through many links but couldn't come up with a clear view.

Thanks!

$\endgroup$
12
$\begingroup$

The EM algorithm (expectation maximization) is a general algorithm for optimization of the likelihood function in cases where the model is specified probabilistically in terms of an observed and an unobserved (latent) component. HMMs (hidden Markov models) are models of this form because they have an unobserved component, the hidden states, and the actual observations are often called the emissions in the HMM terminology. Hence, HMMs form a class of models for which the EM algorithm can be useful.

In generel, if the model consists of two components $(X,Y)$, which we assume take values in a finite space for simplicity, and if the probabilistic model specification consists of the joint point probabilities $p_{\theta}(x,y)$, parametrized by $\theta$, then the likelihood when observing only $X = x$ is $$L_x(\theta) = \sum_{y} p_{\theta}(x,y).$$ Though the sum looks innocent, it is not. For HMMs the sum will be over all possible transitions between the hidden states, which quickly becomes a formidable number when the length of the observed sequence grows. Fortunately there are algorithms for HMMs (forward-backward) for fast computation of the likelihood, and the likelihood could then, in principle, be plugged into any general purpose optimization algorithm for maksimum-likelihood estimation of $\theta$. The alternative is the EM-algorithm. This is an algorithm that iteratively alternates between

  • the E-step, which is a computation of a conditional expectation given the observed $x$ under the current estimate of $\theta$
  • the M-step, which is a maximization

The EM-algorithm makes most sense if the two steps above can be implemented in a computationally efficient way, e.g. when we have closed form expressions for the conditional expectation and the maximization.

Historically, the general EM-algorithm is credited to Dempster, Laird and Rubin, who proved in their 1977 paper, among other things, that the algorithm leads to a sequence of parameters with monotonely increasing likelihood values. They also coined the term "EM-algorithm". Interestingly, the EM-algorithm for HMMs was described already in 1970 by Baum et al., and is also often referred to as the Baum-Welch algorithm in the HMM literature (I don't know precisely what Welch did ...).

$\endgroup$
  • 3
    $\begingroup$ Welch invented what is now called Baum-Welch algorithm (he call it "the easy part"); Baum proves mathematically that algorithm works ("the hard part"). See courses.cs.tamu.edu/rgutier/cpsc689_s07/welch2003baumWelch.pdf for exact details. $\endgroup$ – Mikhail Korobov Mar 25 '13 at 23:01
  • $\begingroup$ @MikhailKorobov, thanks for this informative reference. $\endgroup$ – NRH Mar 26 '13 at 19:38
2
$\begingroup$

Expectation Maximization is an iterative method used to perform statistical inference on a variety of different generative statistical models, for example a mixture of Gaussians, and other Bayesian network type models. The only connection is that HMMs are also Bayesian networks. But one would probably not use EM on HMMs because there is an exact algorithm for inference within HMMs called the Viterbi algorithm. So although one could use EM to perform inference on a HMM, you wouldn't because there's no reason to.

$\endgroup$
  • 4
    $\begingroup$ This is not entirely accurate because you mix up two different kinds of "inference". EM is an algorithm for estimation of unknown parameters, Viterbi is the algorithm for computing the most probable sequence of hidden states. You would, indeed, use EM for HMMs for parameter estimation. I have given more details on the EM-algorithm with historical references explaining the relation between HMMs and EM in my answer. $\endgroup$ – NRH Sep 14 '11 at 19:39
0
$\begingroup$

In HMM, we try to estimate mainly three parameters:

  1. The initial state probabilities. This is a vector with $K$ elements, where $K$ is the number of states.

  2. The transition matrix. This is a square matrix of size $K\times K$.

  3. The conditional probabilities of observing an item, conditioned of some state. This is also a matrix of size $K\times N$, where $N$ is the number of observations.

Now, the EM part comes when you try to estimate the quantities/parameters stated above. Starting with some random guess, the likelihood of the observations are evaluated and the parameters are adjusted iteratively until we get maximum likelihood. So, through HMM, we model some process and for that we need to introduce some parameters. To estimate the parameters, EM is rendered.

This is a very brief answer. Implementing EM requires a bunch of other sub-problems to solve via a series of techniques. For in depth understanding, Rabiner classic tutorial paper is highly recommended.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.