GMM and EM Algorithm

A Gaussian Mixture Model (GMM) assumes the data is generated by $K$ underlying clusters, each Gaussian with its own mean and covariance: where $\pi_k \geq 0$ and $\sum_k \pi_k = 1$ are mixture weights. GMMs are *soft-clustering* — each point has a probability of belonging to each cluster, not a hard label. They generalize $k$-means (which is roughly a GMM with shared spherical covariances) and are the go-to tool for density estimation and model-based clustering.

Fitting a GMM by maximum likelihood is hard: the log-likelihood $\sum_n \log \sum_k \pi_k \mathcal{N}(\mathbf{x}_n; \boldsymbol\mu_k, \Sigma_k)$ has no closed-form maximum because of the $\log \sum$. Enter the Expectation-Maximization (EM) algorithm — an iterative procedure that monotonically increases the likelihood by alternating two steps. EM is the workhorse for any model with latent variables.

The E-step computes, for each point $n$ and cluster $k$, the responsibility (posterior probability of cluster $k$ given the point under current parameters): Responsibilities are soft cluster assignments — if a point clearly belongs to cluster 3, $r_{n3} \approx 1$; if it lies between clusters 1 and 2, it splits mass between them.

The M-step updates the parameters to maximize the expected complete-data log-likelihood, using the responsibilities as weights: These are exactly the weighted sample mean, weighted sample covariance, and weighted sample proportion. The closed-form update is the payoff for introducing latent variables.

EM is guaranteed to monotonically increase the likelihood and converges to a local maximum. Initialization matters: random starts can land in poor local optima, so $k$-means++ seeding is common. Singularities also lurk — if a Gaussian collapses to a single point, its variance $\to 0$ and likelihood $\to \infty$. Regularize by adding $\epsilon I$ to each covariance or by Bayesian priors. Beyond GMMs, EM trains HMMs, latent Dirichlet allocation, factor analysis, and countless other latent-variable models.

Worked example — one EM iteration on 1D data: Data $\{-2, -1.8, 2.1, 2.3\}$, initialize $K=2$ with $\mu_1 = -1, \mu_2 = 1, \sigma_1^2 = \sigma_2^2 = 1, \pi_1 = \pi_2 = 0.5$. E-step: for $x = -2$, $\mathcal{N}(-2; -1, 1) \propto e^{-0.5}$, $\mathcal{N}(-2; 1, 1) \propto e^{-4.5}$, so $r_{1,1} = e^{-0.5}/(e^{-0.5} + e^{-4.5}) \approx 0.982$. By symmetry $r_{4,2} \approx 0.982$. M-step (cluster 1): $N_1 \approx 0.982 + 0.982 + 0.018 + 0.018 = 2$, $\mu_1 \approx (-2 \cdot 0.982 + (-1.8) \cdot 0.982 + 2.1 \cdot 0.018 + 2.3 \cdot 0.018)/2 \approx -1.83$. The mean snapped to the left cluster's empirical average.