Why EM Increases the Observed Likelihood

Why an EM step cannot lower the likelihood

With incomplete data, the observed-data likelihood is often difficult to maximize directly. The EM algorithm instead conditions on the unobserved part of the data, then maximizes an expected complete-data log likelihood. The important guarantee is precise but conditional: if the new parameter does not lower that expectation, and the relevant quantities satisfy suitable support and finiteness conditions, the observed-data likelihood cannot decrease.

The proof explains both why the algorithm works and where a careless version of the argument can fail. In particular, a difference of two expected log likelihoods is meaningful only when those expectations are finite; subtracting two values equal to negative infinity is not a valid operation.

Setup and regularity conditions

Write \(y\) for the observed data and \(u\) for the missing or latent data. Let \(g_\theta(y,u)\) be a joint density or mass function for the complete data, with respect to a fixed measure on the complete-data space. The observed-data likelihood is obtained by integrating or summing out \(u\). For a current parameter \(\theta_t\), assume the observed likelihoods below are positive and finite, and define the conditional density of \(U\) given \(y\) by \(p_t(u\mid y)=g_{\theta_t}(y,u)/h_{\theta_t}(y)\).

For discrete latent data, the integral is a sum. The EM auxiliary function is the conditional expectation of the complete-data log density under the current parameter:

The observed-data likelihood is \(h_\theta(y)\), so its log is \(\ell_{\mathrm{obs}}(\theta)=\log h_\theta(y)\). In a data set with multiple observations, \(y\) and \(u\) can denote the full observed and missing portions, and \(g_\theta\) their joint density.

The likelihood decomposition and monotonicity

Here is the standard decomposition in a form that makes its assumptions explicit. At the observed value \(y\), suppose \(h_{\theta_t}(y)\) and \(h_\theta(y)\) are positive and finite. Assume the two quantities \(Q(\theta\mid\theta_t)\) and \(Q(\theta_t\mid\theta_t)\) are each finite, and that \(g_\theta(y,u)>0\) wherever \(p_t(u\mid y)>0\). These conditions ensure the relevant log-density ratios are integrable under the current conditional distribution and avoid undefined expressions.

Proof. By the definitions of the two conditional densities,

Integrate both sides with respect to \(p_t(u\mid y)\). The second term on the right is constant in \(u\), and the first term integrates to the negative of the difference in the two finite \(Q\)-function values. Therefore

The divergence is nonnegative. Indeed, for \(x>0\), \(\log x\leq x-1\). Apply this with \(x=p_\theta(u\mid y)/p_t(u\mid y)\), multiply by \(p_t(u\mid y)\), and integrate. Since both conditional densities integrate to one, this gives

Rearranging the identity proves the decomposition. If \(Q(\theta\mid\theta_t)\geq Q(\theta_t\mid\theta_t)\), both the \(Q\)-function difference and the divergence are nonnegative, so \(\ell_{\mathrm{obs}}(\theta)\geq\ell_{\mathrm{obs}}(\theta_t)\). This proves the claimed monotonicity. \(\square\)

An exact maximization of \(Q\) is not required for the conclusion. It is enough that the update does not decrease \(Q\). This is why the monotonicity guarantee also applies to generalized EM steps.

A Jensen inequality version

There is a related argument that does not require writing the result as a difference of two finite \(Q\)-function values. Define the expected log-density ratio directly:

Suppose this expectation is finite, the ratio is positive \(p_t\)-almost surely, and its expectation under \(p_t\) is finite and positive. The integral below is over the support where \(g_{\theta_t}(y,u)>0\). Since \(p_t=g_{\theta_t}/h_{\theta_t}\), direct substitution gives

The inequality allows the candidate model to assign some mass to locations outside the current model’s support: that mass contributes to \(h_\theta(y)\), but not to the integral on the left. Taking logarithms preserves the inequality. Jensen’s inequality, applied to the logarithm, then gives

Thus a nonnegative, well-defined expected log-density ratio is another sufficient condition for nondecreasing observed log likelihood. When both \(Q\)-function values are finite, this expectation equals their difference. Without that finiteness, it is safer to state the argument using \(D\) directly than to subtract \(Q\)-values that may not be defined as a finite difference.

Worked examples

Common pitfall and practical meaning

A common mistake is to say that the likelihood change equals a \(Q\)-function difference plus a nonnegative divergence without checking that the two \(Q\)-values are finite. A finite expectation of the log-density ratio alone does not ensure either \(Q\)-value is finite: both can be negative infinity even when their ratio is identically one. The correction is to state the decomposition with finite \(Q\)-values, as in the theorem, or to work directly with the well-defined expected log-density ratio and its conditions.

A second issue is support. The exact posterior-divergence identity requires the candidate complete-data density to be positive wherever the current conditional distribution places positive probability. If the candidate assigns zero density on a set of positive current conditional probability, the divergence can be infinite, and the finite identity above does not apply. The Jensen argument can still provide a useful likelihood bound when its own assumptions hold, but a nonnegative \(Q\)-gain should not be asserted from undefined quantities.

The monotonicity result matters because it distinguishes a fundamental guarantee from a convergence claim. Each valid EM step is nondecreasing in observed likelihood, but this fact alone does not prove that the iterates converge to a global maximum, or even that every limit point is a maximum. It also does not guarantee a strict increase: the likelihood may stay unchanged, as can happen when the missing data contain no information about a parameter. These are separate questions from the stepwise inequality proved here.