Gaussian Mixture Models & EM

A Gaussian Mixture Model (GMM) is a probabilistic version of k-means: instead of assigning each point to a single cluster, it models the data as a mixture of Gaussian densities and produces soft assignments. The Expectation-Maximization (EM) algorithm — used to fit GMMs — generalises far beyond clustering, becoming a universal recipe for maximum-likelihood estimation with latent variables.

The model

A $K$-component GMM is

$$p(\mathbf{x})=\sum _{k=1}^K{\pi }_k\mathcal{N}(\mathbf{x};{\mathit{\mu }}_k,{\mathrm{\Sigma }}_k),$$

with mixing weights ${\pi }_k\ge 0$, $\sum _k{\pi }_k=1$. Generative story: pick a component $k$ with probability ${\pi }_k$, then sample $\mathbf{x}\sim \mathcal{N}({\mathit{\mu }}_k,{\mathrm{\Sigma }}_k)$.

The latent variable $z\in \{1,\dots ,K\}$ — which component generated $\mathbf{x}$ — is not observed. This is what makes the likelihood non-convex and EM necessary.

The EM algorithm

We want $\arg \underset{\theta }{max}\log p(\mathbf{X};\theta )=\arg \underset{\theta }{max}\sum _i\log \sum _k{\pi }_k\mathcal{N}({\mathbf{x}}_i;{\mathit{\mu }}_k,{\mathrm{\Sigma }}_k)$. The log-of-sum is intractable. EM exploits the latent-variable structure.

E-step. Compute the responsibilities — posterior probabilities of each component given the data:

$${\gamma }_{ik}=P(z_i=k\mid {\mathbf{x}}_i;{\theta }^{\text{old}})=\frac{{\pi }_k^{\text{old}}\mathcal{N}({\mathbf{x}}_i;{\mathit{\mu }}_k^{\text{old}},{\mathrm{\Sigma }}_k^{\text{old}})}{\sum _j{\pi }_j^{\text{old}}\mathcal{N}({\mathbf{x}}_i;{\mathit{\mu }}_j^{\text{old}},{\mathrm{\Sigma }}_j^{\text{old}})}.$$

M-step. Update parameters as if the responsibilities were the labels:

$$N_k=\sum _i{\gamma }_{ik},{\mathit{\mu }}_k=\frac{1}{N_k}\sum _i{\gamma }_{ik}{\mathbf{x}}_i,{\mathrm{\Sigma }}_k=\frac{1}{N_k}\sum _i{\gamma }_{ik}({\mathbf{x}}_i-{\mathit{\mu }}_k)({\mathbf{x}}_i-{\mathit{\mu }}_k{)}^{\mathrm{\top }},{\pi }_k=N_k/N.$$

Iterate until the log-likelihood converges.

Why EM works: the ELBO

EM is coordinate ascent on a lower bound of the log-likelihood. For any distribution $q(z)$,

$$\log p(\mathbf{x};\theta )\ge {\mathbb{E}}_q[\log p(\mathbf{x},z;\theta )]-{\mathbb{E}}_q[\log q(z)]\equiv \mathcal{L}(q,\theta ).$$

This is the ELBO — also the centre of VAE training.

• E-step sets $q(z)=p(z\mid \mathbf{x};{\theta }^{\text{old}})$, making the bound tight.
• M-step maximises $\mathcal{L}$ over $\theta$ with $q$ fixed.

Each iteration cannot decrease $\log p(\mathbf{x};\theta )$ — EM monotonically improves the likelihood until a stationary point. (It does not necessarily find the global optimum; multiple restarts and good initialisation matter.)

GMM vs k-Means

GMM with isotropic, equal-variance Gaussians and "hard" responsibilities reduces to k-means. The differences:

• Soft assignments. ${\gamma }_{ik}$ is a probability, not a one-hot — points near a cluster boundary contribute to multiple clusters proportionally.
• Anisotropic clusters. Full ${\mathrm{\Sigma }}_k$ captures elongated, oriented cluster shapes that k-means cannot.
• Probabilistic output. GMMs give a density estimate $p(\mathbf{x})$, useful for outlier detection and generative sampling.
• Higher computational cost. $O(K{d}^2)$ per E-step instead of $O(Kd)$.

Initialisation and degeneracies

EM is sensitive to initialisation:

• Run k-means first; use its centroids and per-cluster covariance as the GMM init.
• Multiple random restarts; pick the highest-likelihood solution.

GMMs have a famous degeneracy: a Gaussian centred on a single training point with vanishing covariance achieves infinite likelihood (the density blows up). Standard fix: add a small regularisation to each ${\mathrm{\Sigma }}_k$ (${\mathrm{\Sigma }}_k\leftarrow {\mathrm{\Sigma }}_k+ϵI$) or use a Bayesian prior (Bayesian GMM, variational mixture of Gaussians).

Beyond clustering

EM works for any latent-variable model with tractable conditional posteriors:

• Hidden Markov Models (see HMM) — the latent is a sequence; EM is the Baum-Welch algorithm.
• Probabilistic PCA — Gaussian latent, Gaussian likelihood; EM gives PCA in the limit.
• Topic models (LDA) — EM-style variational inference over latent topic assignments.

The EM template — bound the log-likelihood with the ELBO, alternate E and M — is one of the most general inference recipes in machine learning.

What to read next

• k-Means — the hard-assignment special case.
• Bayes Nets — graphical models where EM applies broadly.
• Variational Autoencoders — modern amortised EM with neural networks.