In many statistical problems, we aim to find the parameters $\theta$ that maximize the log-likelihood of our observed data, $X$. This is standard Maximum Likelihood Estimation (MLE). The problem becomes significantly more complex when our model includes latent variables, $Z$, which are unobserved.

Our goal is to maximize the marginal log-likelihood, often called the incomplete-data log-likelihood:

This marginalization often introduces complex dependencies or results in a sum within the logarithm, making direct optimization intractable. If we somehow knew the values of the latent variables $Z$, our problem would simplify to maximizing the complete-data log-likelihood, $\log p(X, Z | \theta)$, which is typically much easier to work with.

The Expectation-Maximization (EM) algorithm provides an iterative approach to handle this intractability. Instead of maximizing $\mathcal{L}(\theta)$ directly, it maximizes a more convenient lower bound on it.

To derive this lower bound, we introduce an arbitrary probability distribution $q(Z)$ over the latent variables. We can then rewrite the marginal log-likelihood and apply Jensen's inequality. Since the logarithm is a concave function, we know that $\log E[Y] \ge E[\log Y]$. This single mathematical property is the key to the entire EM derivation.

This result is the Evidence Lower Bound (ELBO), a foundational concept in variational inference and the EM algorithm. We denote it as $\mathcal{F}(q, \theta)$:

The gap between the ELBO and the true log-likelihood can be expressed using the Kullback-Leibler (KL) divergence, a measure of how one probability distribution differs from a second.

This decomposition is powerful. To maximize the log-likelihood, we can instead iteratively maximize the ELBO. The EM algorithm does this by coordinating updates to $q(Z)$ and $\theta$.

The algorithm proceeds in two alternating steps: maximizing the ELBO with respect to $q$ (E-step) and then with respect to $\theta$ (M-step).

The E-Step

In the E-step, we hold the parameters $\theta^{(t)}$ from the previous iteration constant and maximize $\mathcal{F}(q, \theta^{(t)})$ with respect to the distribution $q(Z)$. Looking at our decomposition, we see that the ELBO is maximized when the KL divergence term is minimized. The KL divergence $D_{\text{KL}}(q \|\| p)$ is zero if and only if $q = p$. Therefore, we set $q(Z)$ to be the true posterior distribution of the latent variables:

Let's expand the ELBO to see what we are actually maximizing. We can separate it into two terms:

Since the entropy term $H(q)$ does not depend on $\theta$, maximizing the ELBO is equivalent to maximizing the $Q$ function. This is the origin of the M-step's name: maximizing the expectation.

By alternating these two steps, we are guaranteed to increase the marginal log-likelihood $\log p(X|\theta)$ at each iteration, or leave it unchanged, until a local maximum is reached. The E-step makes the lower bound tight, and the M-step pushes the value of that bound up, which in turn pushes the true likelihood up.