Hidden Markov models and expectation maximization algorithm 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!
 A: 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 ...). 
A: 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.
A: In HMM, we try to estimate mainly three parameters:


*

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

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

*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.
