DEV Community

Umesh Tharuka Malaviarachchi
Umesh Tharuka Malaviarachchi

Posted on

Expectation-Maximisation: Why Alternating Between Expectation and Maximisation Climbs the Likelihood

Some of the most useful models in statistics have a frustrating structure: the likelihood would be easy to maximise if we could see something we cannot see. A mixture model hides which component produced each point. A hidden Markov model hides the state sequence. A factor model hides the factors. Expectation-Maximisation, usually shortened to EM, is the algorithm that turns this frustration into a routine. It alternates between guessing the hidden quantities from the current parameters and updating the parameters from those guesses, and it never decreases the observed likelihood.

That guarantee is what makes EM worth understanding rather than just using. It is not a heuristic that happens to work. It is a principled way to climb a difficult objective by repeatedly optimising a simpler surrogate, and its failures are almost always failures of that surrogate logic: local optima, slow progress near flat regions, and model misspecification that no optimiser can fix.

The problem: a likelihood with a hole in it

Suppose we observe data x and posit latent variables z that we do not observe. The model has parameters theta. The observed-data likelihood is the marginal over the latent variables:

p(x∣θ)=∑zp(x,z∣θ) p(x | \theta) = \sum_z p(x, z | \theta)

For continuous latent variables, replace the sum with an integral. The difficulty is the logarithm. The log of a sum is not the sum of logs, so the complete-data log-likelihood, log⁡p(x,z∣θ)\log p(x, z | \theta) , which might factorise nicely, is trapped inside a logarithm of a marginal. Direct optimisation is therefore awkward, especially when the latent space is large or structured.

A Gaussian mixture model makes this concrete. Each point comes from one of K components, but we do not know which. If we knew the assignments, estimating each component mean, covariance, and mixing weight would be a set of weighted averages. Without them, the likelihood is a sum over K terms per point, and its gradient couples all the components together.

EM resolves this by refusing to maximise the observed log-likelihood directly. Instead, at each iteration it builds a lower bound that touches the true objective at the current parameters, maximises that bound, and thereby guarantees progress on the real objective.

The key idea: a lower bound built from the posterior

Fix current parameters θ(t)\theta^{(t)} . For any distribution q over the latent variables, Jensen's inequality gives a lower bound on the observed log-likelihood, often called the evidence lower bound or ELBO:

log⁡p(x∣θ)≥∑zq(z)log⁡p(x,z∣θ)q(z) \log p(x | \theta) \geq \sum_z q(z) \log \frac{p(x, z | \theta)}{q(z)}

The bound is tight when q equals the posterior p(z∣x,θ(t))p(z | x, \theta^{(t)}) . That observation gives the two steps of EM.

In the E-step, set q to the posterior under the current parameters and compute the expected complete-data log-likelihood, usually written Q:

Q(θ∣θ(t))=Ez∣x,θ(t)[log⁡p(x,z∣θ)] Q(\theta | \theta^{(t)}) = \mathbb{E}_{z | x, \theta^{(t)}}[\log p(x, z | \theta)]

In the M-step, choose the next parameters to maximise Q:

θ(t+1)=arg⁡max⁡θQ(θ∣θ(t)) \theta^{(t+1)} = \arg\max_{\theta} Q(\theta | \theta^{(t)})

Because Q plus an entropy term equals the ELBO, and because the ELBO touches the true log-likelihood at θ(t)\theta^{(t)} , maximising Q cannot decrease the observed log-likelihood. The formal statement is reassuringly simple:

log⁡p(x∣θ(t+1))≥log⁡p(x∣θ(t)) \log p(x | \theta^{(t+1)}) \geq \log p(x | \theta^{(t)})

This monotonicity is a property of the algorithm, not of a particular model. It holds whenever the E-step uses the exact posterior and the M-step genuinely maximises Q. When either condition is relaxed, as in variational EM or generalised EM, the guarantee weakens in exactly the way you would expect, and that is a useful diagnostic: if a variant of EM decreases the likelihood, something in its E-step or M-step is approximate.

A worked example: Gaussian mixtures

For a mixture of K Gaussians, the latent variable for point xix_i is its component assignment ziz_i . The parameters are mixing weights πk\pi_k , means μk\mu_k , and covariances Σk\Sigma_k .

The E-step computes responsibilities: the posterior probability that point i belongs to component k under the current parameters:

γik=πk N(xi∣μk,Σk)∑j=1Kπj N(xi∣μj,Σj) \gamma_{ik} = \frac{\pi_k \, \mathcal{N}(x_i | \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \, \mathcal{N}(x_i | \mu_j, \Sigma_j)}

A responsibility is a soft assignment. A point sitting between two clusters gets partial credit from both, which is exactly what a hard clustering method throws away.

The M-step then updates each parameter by weighted averages, with weights given by the responsibilities. Let Nk=∑iγikN_k = \sum_i \gamma_{ik} be the effective number of points assigned to component k. Then:

πk=NkN,μk=1Nk∑iγikxi,Σk=1Nk∑iγik(xi−μk)(xi−μk)T \pi_k = \frac{N_k}{N}, \quad \mu_k = \frac{1}{N_k} \sum_i \gamma_{ik} x_i, \quad \Sigma_k = \frac{1}{N_k} \sum_i \gamma_{ik} (x_i - \mu_k)(x_i - \mu_k)^T

That is the whole algorithm for mixtures: compute soft assignments, recompute weighted statistics, repeat. The same pattern recurs in hidden Markov models, where the E-step is the forward-backward algorithm, and in factor analysis, where the E-step computes posterior means and covariances of the factors. The machinery changes; the logic does not.

A minimal implementation sketch shows how little code the mixture case needs once the responsibilities are in place:

import numpy as np
from scipy.stats import multivariate_normal

def em_gmm(X, K, n_iter=100):
    N, D = X.shape
    pi = np.full(K, 1.0 / K)
    mu = X[np.random.choice(N, K, replace=False)]
    sigma = np.array([np.eye(D) for _ in range(K)])
    for _ in range(n_iter):
        # E-step: responsibilities
        resp = np.column_stack([
            pi[k] * multivariate_normal.pdf(X, mu[k], sigma[k])
            for k in range(K)
        ])
        resp /= resp.sum(axis=1, keepdims=True)
        # M-step: weighted averages
        Nk = resp.sum(axis=0)
        pi = Nk / N
        mu = (resp.T @ X) / Nk[:, None]
        for k in range(K):
            diff = X - mu[k]
            sigma[k] = (resp[:, k, None] * diff).T @ diff / Nk[k]
    return pi, mu, sigma
Enter fullscreen mode Exit fullscreen mode

Note what this code does not do: it never evaluates the observed log-likelihood directly during the update. It trusts the bound. In practice you should still track the log-likelihood across iterations, both as a convergence check and as a sanity check that the bound logic is actually holding in your implementation.

Why EM converges, and to what

EM is a minorisation-maximisation algorithm: it minorises the objective with a surrogate that touches it at the current point, then maximises the surrogate. Every iteration therefore climbs, but climbing is not the same as reaching the summit. EM converges to a stationary point of the observed log-likelihood, which may be a local maximum, a saddle point, or, in degenerate cases, a boundary point. It has no mechanism for escaping a local optimum, and its starting point matters a great deal.

Convergence speed is the second limitation. Near the optimum, EM typically converges linearly, and the rate depends on how much information the latent variables hide. When the posterior over z is nearly certain, the bound is tight and progress is fast. When the posterior is diffuse, the bound is loose, each step moves only a little, and EM can crawl. This is sometimes called the missing-information principle: the fraction of missing information controls the convergence rate. In mixture models, heavy overlap between components is therefore a double problem, because it makes both the statistical task harder and the optimisation slower.

A practical consequence is that stopping rules deserve care. A small change in parameters does not imply a small distance to the optimum when convergence is slow. Track the log-likelihood itself, use a tolerance on its change over several iterations rather than a single step, and run EM from multiple initialisations, keeping the run with the highest final likelihood. Random restarts are not inelegant here; they are the standard response to a local algorithm.

Common pitfalls

First, singularities. In a Gaussian mixture, a component can collapse onto a single data point, driving its variance toward zero and its likelihood toward infinity. The likelihood is then unbounded, and the "maximum" EM finds is a degenerate spike rather than a meaningful clustering. Regularisation, a minimum variance floor, or a Bayesian prior on the covariances prevents this, but the pitfall is a reminder that maximising likelihood is only as sensible as the model being maximised.

Second, choosing K. EM fits a mixture for a fixed number of components; it does not choose that number. Model selection criteria such as BIC, cross-validated likelihood, or a held-out clustering quality measure must do that job separately. Running EM for several values of K and comparing final likelihoods alone will always favour more components, because a larger model can always fit at least as well.

Third, confusing soft assignments with truth. Responsibilities are posterior probabilities under the fitted model, not ground-truth labels. Treating a point with responsibility 0.55 as "in cluster A" discards the uncertainty that made the soft approach valuable, and downstream analyses that hard-threshold responsibilities inherit that overconfidence silently.

Fourth, identifiability. Mixture components can be permuted without changing the likelihood, so component labels are arbitrary across runs. Comparing parameters across restarts or datasets requires matching components first, usually by proximity of means or by a Hungarian assignment on some similarity measure.

When to use EM, and when not to

EM shines when the E-step is tractable and the M-step has a closed form. Mixtures, hidden Markov models, factor analysis, and probabilistic PCA all satisfy this, which is why EM remains a workhorse despite being older than most deep learning methods. It also shines as a conceptual tool: many modern algorithms, from variational autoencoders to the wake-sleep algorithm, are best understood as approximations to the EM logic, with an approximate posterior in place of the exact one.

EM is the wrong tool when the posterior is intractable and no good approximation exists, when the M-step itself requires iterative optimisation that swamps the benefit of the decomposition, or when the likelihood surface is so multimodal that local climbing from a few starts is hopeless. In those settings, direct gradient methods on a reparameterised objective, or sampling-based inference, are usually more productive. The question is never whether EM is "good" in the abstract; it is whether the complete-data problem is genuinely easier than the observed-data problem for your model. When it is, EM is hard to beat for simplicity and stability. When it is not, the bound is just overhead.

Takeaway

Expectation-Maximisation works because it replaces a hard problem with a sequence of easy ones, each guaranteed not to make things worse. The E-step asks what the hidden variables probably were, given what you currently believe. The M-step updates your beliefs as if those guesses were data. Repeat, and the observed likelihood climbs monotonically to a local optimum. Understand that guarantee, its reliance on an exact posterior and an exact maximisation, and its silence about global optimality, and you understand both why EM is so widely used and why it sometimes needs help from restarts, regularisation, and careful convergence checks.


Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial

Top comments (0)