Understanding the details of Expectation Maximization(EM) for estimating the parameters? When using the Expectation Maximization(EM) for estimating the parameters, every time I came across a different problem I see a totally different representation of the likelihood/Expectation function and a different formula in the E-step & M-step i.e. one guy adds extra terms, another remove some terms, yet another bring new ways (tricks) to solve it.


*

*Is there a standard way which we can use it as a rule, not like saying E-step is the Expectation of the Likelihood and M-step is maximizing it?

*in EM algorithm there is an expectation of the log-likelihood with respect to the posterior/conditional distribution of the hidden variables i.e. $E_{p(y|x,\theta)}(log(p(x,y|\theta))$. And we know that $p(x,y|\theta)=p(y|x,\theta)\times p(x|\theta)$ i.e. it should be sufficient to find a formula of $p(y|x,\theta)$ for calculating $p(x,y|\theta)$ because $p(x|\theta)$ is the frequency of x in the dataset which should be known. However,  I have come through several EM applications/examples and I did not find anyone using this rule, rather all of them use a different and direct (i.e. without depending on $p(y|x,\theta)$ ) formula for $p(x,y|\theta)$. So what is the reason behind that? Isn't it easier to use this rule for finding $p(x,y|\theta)$ instead of trying to find two unique formulas for $p(y|x,\theta)$ and $p(x,y|\theta)$ for caluclating the expectation.

 A: The EM method is a generalized algorithm that solves maximum-likelihood problems with latent variables. Suppose that you have a model with some random variables $y$ that you have observed (measurements) and some random variables $z$ that are unknown. We write this model as a joint probability distribution
$$ p_\theta(y,z)$$
where $\theta$ are the parameters that you want to estimate.
The problem now is that we cannot do maximum likelihood on this model because we do not known what to put in for the $z$ variables.
One way to solve this problem is marginalization: we remove the unknown random variables from the model by integrating them out with
$$ p_\theta(y) = \int p_\theta(y,z) \mathrm{d} z.$$
In most interesting cases this integral cannot be solved in closed form. This is where the EM method comes to help. It is an iterative procedure that starts from any initial estimate $\theta^{(0)}$ and iterates two steps.
In the first (the E-step) we create a lower bound on the likelihood function $\log p_\theta(y)$ by computing
$$ Q(\theta,\theta^{(k)}) = \mathbf{E}\{\log p_\theta(y,z)\}$$
where the expectation is taken with respect to the best estimate of the conditional distribution of the latent variables $p_{\theta^{(k)}}(z|y)$.
In the second step (the M-step) we maximize the lower bound to update the parameter estimate:
$$\theta^{(k+1)} = \arg \max_\theta Q(\theta,\theta^{(k)}).$$
Under some regularity conditions, $\theta^{(k)} \to \theta_0$ where $\theta_0$ is a local maximum of the marginal likelihood $p_\theta(y)$.
There are a lot of tricks you can use to solve the E-step and the M-step. Most notably

*

*if $p_\theta(y,z) = q_\theta(y,z)g(y,z)$ where $g(y,z)$ is independent of $\theta$, you can disregard the whole $g(y,z)$ in computing $Q(\theta,\theta^{(k)})$ because that part will not impact the successive maximization step. This is very useful in hierarchical models: suppose that the joint model is $p_\theta(y,z) = p(y|z_1)p(z_2|z_3)p_\theta(z_3|z_4)p(z_4)$, in the E-step we just need to consider
$$ Q(\theta,\theta^{(k)}) = \mathbf{E}\{\log p_\theta(z_3|z_4)\}$$
because all other factors are independent of $\theta$!

*You can freely add as many variables as you want to the model: these will anyway be integrated out by the EM method! This is especially useful if you can separate parameters given a variable. Suppose that your model depends on two parameters $p_{\theta_1,\theta_2}(y)$. If there is a random variable $z$ such that $p_{\theta_1,\theta_2}(y,z) = p_{\theta_1}(y|z)p_{\theta_2}(z)$, then the EM method gives you two functions
$$Q_1(\theta_1,\theta^{(k)}) = \mathbf{E}\{\log p_{\theta_1}(y|z)\}$$
and
$$Q_2(\theta_2,\theta^{(k)}) = \mathbf{E}\{\log p_{\theta_2}(z)\}$$
(where all expectations are taken with respect to $p_{\theta^{(k)}}(z|y)$. Similarly, the M-step splits into two different optimization problems:
$$\theta_1^{(k+1)} = \arg\max_{\theta_1} Q_1(\theta_1, \theta^{(k)}),$$
and
$$\theta_2^{(k+1)} = \arg\max_{\theta_2} Q_2(\theta_2, \theta^{(k)}).$$
Sadly (as you may guess from my examples) there is no general way to solve a problem with EM... it all depends on the structure: How easy is it to compute $p(z|y)$? How easy is it to take expectations with respect to it? Which latent variables $z$ may I need to make the problem simpler? Which part can I disregard?

Additional answer to point 2:
WARNING: notation changes w.r.t. the previous section!
What formulas you use really depend on your model; all in all what you want to solve is
$$\hat \theta = \arg \max \log p(x|\theta)$$
where $x$ is the data. The key assumption is that $p(x|\theta)$ is not available in closed form or is complicated to work with (if it were easy, you would just maximize it and be happy!). Instead, you have access to $p(x,y|\theta)$ and you use the EM method to solve
$$\hat \theta = \arg \max \log \int p(x,y|\theta) \mathrm d y.$$
In this example the variable $y$ is the latent variable which you introduce to make the problem tractable. Consider for instance the mixture of two Gaussians
$$p(x|\theta) = \alpha N(x|m_1,\sigma_1^2) + (1-\alpha)N(x|m_2,\sigma_2^2).$$
Estimating $\theta = {\alpha,m_1,\sigma_1,m_2,\sigma_2}$ from data can be either done directly using numerical optimization; or introducing a latent variable $y$ that tells you which of the mixtures the datapoint belongs to. Then we have the conditional densities (the likelihoods)
$$p(x|y=1,\theta) = N(x|m_1,\sigma_1^2)\qquad p(x|y=2, \theta) = N(x|m_2,\sigma_2^2).$$
We apply the EM method by computing, at each iteration, the probability that a sample belongs to either mixture (i.e. $p(y=i|x,\hat\theta^{(k)}$) and then maximizing the likelihood of the parameters using this probability assignment.
I hope this more explicit example answers your question.

Additional remark about discrete latent variables
If $z$ are discrete random variables (say, the outcome of a draw of cards), then the expectation with respect to the latent variables is effectively a sum:
$$ \mathbf E\{\log p_\theta(y,z)\} = \sum_{i=1}^M r_i \log p_\theta(y,z_i) $$
where $r_i$ denotes the probability of outcome $z_i$ given the observed data (for the parameter value $ \theta^{(k)}$):
$$ r_i = p(z_i | y; \theta^{(k)}).$$

Additional remark about discrete i.i.d. observations
In the previous discourse, $y$ denoted a set of observations. In case we have $y = \{y_j\}_{j=1}^N$ where each measurement $y_j$ is drawn from some distribution $p_\theta(y)$, then we have that the joint distribution is
$$\log p_\theta(y) = \sum_{j=1}^N \log p_\theta(y_j).$$
In this case,
$$Q(\theta,\theta^{(k)}) = \mathbf{E}\{ \log p_\theta(y,z)\} = \sum_{j=1}^N \mathbf{E}\{\log p_\theta(y_j,z)\}.$$
Combining this with the discussion at the previous point, we have that in case $z_i$ are discrete outcomes,
$$Q(\theta, \theta^{(k)}) = \sum_{j=1}^N\sum_{i=1}^M r_{i,j} \log p_\theta(y_j,z_i).$$
where $r_i = p(z_i|y_j;\theta^{(k)}).$$
