Why is the expectation maximization algorithm used?

Question

From what little I know the EM algorithm can be used to find the maximum likelihood when setting to zero the partial derivatives with respect to the parameters of the likelihood gives a set of equations that cannot be solved analytically. But is the EM algorithm needed instead of using some numerical technique to try to find a maximum of the likelihood with respect to the constraint of the set of equations mentioned.

Answer 1

The question is legit and I had the same confusion when I first learnt the EM algorithm.

In general terms, the EM algorithm defines an iterative process that allows to maximize the likelihood function of a parametric model in the case in which some variables of the model are (or are treated as) "latent" or unknown.

In theory, for the same purpose, you can use a minimization algorithm to numerically find the maximum of the likelihood function for all parameters. However in real situation this minimization would be:

1. much more computationally intensive
2. less robust

A very common application of the EM method is fitting a mixture model. In this case considering the variable that assign each sample to one of the component as "latent" variables the problem is greatly simplified.

Lets look at an example. We have N samples $s = \{s_i\}$ extracted from a mixture of 2 normal distributions. To find the parameters without EM we should minimize:

$$-\log \mathcal{L}(x,\theta) = -\log\Big[ a_1 \exp\Big( \frac{(x-\mu_1)^2}{2\sigma_1^2}\Big) + a_2 \exp\Big(\frac{(x-\mu_2)^2}{2\sigma_2^2}\Big) \Big]$$

On the contrary, using the EM algorithm, we first "assign" each sample to a component (E step) and then fit (or maximize the likelihood of) each component separately (M step). In this example the M-step is simply a weighted mean to find $\mu_k$ and $\sigma_k$. Iterating over these two steps is a simpler and more robust way to minimize $-\log \mathcal{L}(x,\theta)$.

Answer 2

EM is not needed instead of using some numerical technique because EM is a numerical method as well. So it's not a substitute for Newton-Raphson. EM is for the specific case when you have missing values in your data matrix. Consider a sample $X = (X_{1},...,X_{n})$ which has conditional density $f_{X|\Theta}(x|\theta)$. Then the log-likelihood of this is $$l(\theta;X) = log f_{X|\Theta}(X|\theta)$$ Now suppose that you do not have a complete data set such that $X$ is made up of observed data $Y$ and missing (or latent) variables $Z$, such that $X=(Y,Z)$. Then the log-likelihood for the observed data is $$l_{obs}(\theta,Y)=log \int f_{X|\Theta}(Y,z|\theta)\nu_{z}(dz)$$ In general you cannot compute this integral directly and you will not get a closed-form solution for $l_{obs}(\theta,Y)$. For this purpose you use the EM method. There are two steps which are iterated for $i$ times. In this $(i + 1)^{th}$ step these are the expectation step in which you compute $$Q(\theta|\theta^{(i)}) = E_{\theta^{(i)}}[l(\theta;X|Y]$$ where $\theta^{(i)}$ is the estimate of $\Theta$ in the $i^{th}$ step. Then compute the maximization step in which you maximize $Q(\theta|\theta^{(i)})$ with respect to $\theta$ and set $\theta^{(i+1)} = max Q(\theta|\theta^{i})$. You then repeat these steps until the method converges to some value which will be your estimate.

If you need more information on the method, its properties, proofs or applications just give a look at the corresponding Wiki article.

Answer 3

EM is used because it's often infeasible or impossible to directly calculate the parameters of a model that maximizes the probability of a dataset given that model.