In real-world data generation, many fundamental governing factors are never directly measured: unobserved disease sub-types in genomics, latent topics in text corpora, or hidden mixture components in clustering. In the presence of latent unobserved variables $Z$, the marginal log-likelihood involves the logarithm of a sum, destroying the analytical simplicity of maximum likelihood estimation. In 1977, Arthur Dempster, Nan Laird, and Donald Rubin formalized the definitive solution: the Expectation-Maximization (EM) Algorithm.
1. The Latent Variable Log-Likelihood Dilemma
Let $X = {x_1, dots, x_n}$ denote observed data and $Z = {z_1, dots, z_n}$ denote unobserved latent variables parameterized by $theta$. The marginal probability of the observed data marginalizes over all possible states of $Z$:
$$p(X mid theta) = sum_Z p(X, Z mid theta)$$
The goal is to maximize the incomplete-data log-likelihood:
$$ell(theta) = ln p(X mid theta) = sum_{i=1}^n ln left( sum_{z_i} p(x_i, z_i mid theta) right)$$
Notice the fatal obstruction: the summation appears inside the logarithm. The log does not distribute across the sum, coupling all parameters into an intractable non-linear objective with no closed-form solution.
2. Deriving the Evidence Lower Bound via Jensen’s Inequality
To overcome this, we introduce an arbitrary probability distribution $q(Z)$ over the latent variables ($q(Z) ge 0, sum_Z q(Z) = 1$). Multiplying and dividing by $q(Z)$ inside the sum:
$$ln p(X mid theta) = ln left( sum_Z q(Z) frac{p(X, Z mid theta)}{q(Z)} right) = ln mathbb{E}_{Z sim q}left[ frac{p(X, Z mid theta)}{q(Z)} right]$$
Because the logarithm is a strictly concave function ($ln” < 0$), we apply Jensen’s Inequality ($ln mathbb{E}[Y] ge mathbb{E}[ln Y]$):
$$ln p(X mid theta) ge sum_Z q(Z) ln left( frac{p(X, Z mid theta)}{q(Z)} right) equiv mathcal{L}(q, theta)$$
Function $mathcal{L}(q, theta)$ is the Evidence Lower Bound (ELBO). Expanding the logarithm:
$$mathcal{L}(q, theta) = sum_Z q(Z) ln p(X, Z mid theta) – sum_Z q(Z) ln q(Z) = mathbb{E}_q[ln p(X, Z mid theta)] + mathcal{H}(q)$$
The lower bound decomposes into the expected complete-data log-likelihood plus the Shannon entropy $mathcal{H}(q)$ of distribution $q$.
3. The Two Alternating Steps of EM
The EM algorithm alternates between two optimization steps on the ELBO surface:
- E-Step (Expectation): Maximize $mathcal{L}(q, theta^{(t)})$ with respect to distribution $q$ holding current parameters $theta^{(t)}$ fixed. The bound reaches equality with the true log-likelihood ($mathcal{L} = ln p(X mid theta^{(t)})$) when the KL divergence between $q$ and the posterior vanishes:
$$q^*(Z) = p(Z mid X, theta^{(t)})$$
We then construct the auxiliary $Q$-function:
$$Q(theta; theta^{(t)}) = mathbb{E}_{Z mid X, theta^{(t)}}left[ ln p(X, Z mid theta) right]$$
- M-Step (Maximization): Maximize $Q(theta; theta^{(t)})$ with respect to parameters $theta$:
$$theta^{(t+1)} = argmax_theta Q(theta; theta^{(t)})$$
Because the logarithm is now applied directly to the joint probability $p(X, Z mid theta)$, the objective belongs to an exponential family and admits simple closed-form updates!
4. Proof of Monotonic Convergence
Dempster, Laird, and Rubin proved that the EM algorithm never decreases the true marginal log-likelihood:
$$ell(theta^{(t+1)}) ge mathcal{L}(q^{(t+1)}, theta^{(t+1)}) ge mathcal{L}(q^{(t)}, theta^{(t+1)}) ge mathcal{L}(q^{(t)}, theta^{(t)}) = ell(theta^{(t)})$$
Every single iteration monotonically increases the incomplete-data log-likelihood until it converges to a local stationary maximum.
5. Exemplar: Gaussian Mixture Models (GMMs)
In a Gaussian Mixture Model with $K$ components, latent variable $z_{ik} in {0, 1}$ indicates component assignment. The EM steps yield closed-form updates:
- E-Step Responsibilities:
$$gamma_{ik} = mathbb{E}[z_{ik}] = frac{pi_k mathcal{N}(x_i mid mu_k, Sigma_k)}{sum_{j=1}^K pi_j mathcal{N}(x_i mid mu_j, Sigma_j)}$$
- M-Step Parameter Re-estimation:
$$N_k = sum_{i=1}^n gamma_{ik}, quad mu_k = frac{1}{N_k} sum_{i=1}^n gamma_{ik} x_i, quad Sigma_k = frac{1}{N_k} sum_{i=1}^n gamma_{ik} (x_i – mu_k)(x_i – mu_k)^T, quad pi_k = frac{N_k}{n}$$
The EM algorithm remains one of the most widely deployed probabilistic algorithms in computing, transforming intractable latent integrals into alternating closed-form expectations.
