Why the EM algorithm instead of a more direct computation? [duplicate]

Question

Assume we have a probability distribution $P(y,z|\theta)$, where $x$ is the total set of variables divided into observable variables $y$ and hidden variables $z$, and data on observable variables $y$. We wish to determine $\theta$ that maximizes the likelihood $P(y|\theta)$.

This tutorial (after my breaking their total set of variables $x$ into $y,z$ for clarity) presents the EM algorithm as choosing an arbitrary $\theta^0$ for a probabilistic model's parameters and then repeatedly solving for $m=1,2,\dots$ until convergence:

\begin{eqnarray*} \theta^m &=& \text{argmax}_\theta \sum_z \text{ log }p(y,z|\theta)p(z|y,\theta^{m-1}) \end{eqnarray*}

That requires maximizing $\theta$ over a summation over $z$.

My question is: why not simply more directly solve the problem "what is the most likely value $\theta^*$ for $\theta$ given $y$," that is:

\begin{eqnarray*} \theta^* &=& \text{argmax}_\theta P(y|\theta) & \\ &=& \text{argmax}_\theta \sum_z P(y,z|\theta) \end{eqnarray*}

which also needs to solve a maximization of $\theta$ over a summation over $z$, but does it in a single shot and is conceptually simpler?

In other words, why do we need the iterative algorithm, and why do we need the log?

Update: it's been suggested that this is duplicate of Why should one use EM vs. say, Gradient Descent with MLE?. It is indeed highly related, but the answer there says that EM is better but does not provide an explanation as for why. Also, it does not address the need to use the logarithm.

Answer 1

Stating that the MLE solves the optimisation program $$\hat{θ}=\arg\max_θ f(y|θ)$$ does not explain how one proceeds in practice to achieve this derivation. It is simply stating an inference principle.

Above is the log-likelihood surface of the likelihood $$L(\mu_1,\mu_2)=\prod_{i=1}^n \left\{\frac{3}{10} \varphi(x_i;\mu_1,1) + \frac{7}{10} \varphi(x_i;\mu_2,1/2) \right\}$$ for a sample of size $n=92$. This is a mixture of two Gaussian distributions with unknown means. This is a smooth surface but from an optimisation perspective, it is not regular enough, offering saddle points, plateaus, multiple modes. This means that an off-the-shelf minimisation method like the gradient method or Newtwon-Raphson algorithm is unable to find the global maximum without a sufficiently fine partition of the parameter space. Optimising this non-convex function is a difficult problem, which is not easily tackled as a purely mathematical maximisation problem.

As for the question about the log, i.e., about maximising repeatedly $$\mathbb{E}_{\theta^m}[\log P(y,Z|\theta)|Y=y]$$ instead of once $$\int P(y,z|\theta)\text{d}z$$ using the logarithm implies that the target likelihood $P(y|\theta)$ increases at each iteration of EM as $$\mathbb{E}_{\theta^m}[\log P(y,Z|\theta^{m+1})|Y=y]\ge\mathbb{E}_{\theta^m}[\log P(y,Z|\theta^m)|Y=y]$$and $$\mathbb{E}_{\theta^m}[\log P(y,Z|\theta)|Y=y]=\log P(y|\theta)+\mathbb{E}_{\theta^m}[\log P(Z|y,\theta)|Y=y]$$and $$\mathbb{E}_{\theta^m}[\log P(Z|y,\theta^m)|Y=y]\ge \mathbb{E}_{\theta^m}[\log P(Z|y,\theta^{m+1})|Y=y]$$

Answer 2

The log is present because of the notion that it's often easier to maximize the log-likelihood $\log p(y\mid\theta)$ than the raw likelihood $p(y\mid\theta)$. In the case where we have a hidden variable $z$, the summation over $z$ prevents the log from acting on $p(y,z\mid\theta)$: $$\log p(y\mid\theta)=\log\sum_zp(y,z\mid\theta),\tag1$$ so applying the log is no help in maximizing the expression (1). The insight in the EM algorithm is to get past this roadblock by approximating $\log p(y\mid\theta)$ by its expectation over the hidden variable: $$ \log p(y\mid\theta)\approx E_z \log p(y,z\mid\theta)\tag2 $$ where $E_z$ denotes expectation over $p(z\mid y,\theta)$, the posterior distribution of the hidden variable $z$ given $y$ and $\theta$. This leads us to consider $$ E_z \log p(y,z\mid\theta) = \sum_z \log p(y,z\mid\theta)\, p(z\mid y,\theta)\tag3 $$ where now the log acts directly on the likelihood of the total data. The EM algorithm then proceeds iteratively, by alternating between: [E step] evaluating $p(z\mid y,\theta)$ using an initial guess for $\theta$ and plugging into (3); and: [M step] maximizing (3) over $\theta$ to obtain a revised guess for $\theta$. The maximization that takes place in the M step is made more tractable by the fact that the log now acts directly on $p(y,z\mid\theta)$.

The theory behind EM assures us that this algorithm generates a sequence $\{\theta^m\}$ for which the log likelihood (1) increases with every iteration.