EM Algorithm for Gaussian Mixture Models and Principal Component Analysis – Stanford CS229 Lecture 10 (Spring 2026)

EM Algorithm for Gaussian Mixture Models

The EM algorithm provides a principled way to fit a Gaussian mixture model by iteratively constructing a lower bound on the log‑likelihood and maximizing it.

E‑Step: Constructing the Lower Bound via Jensen’s Inequality

The E‑step builds a surrogate function that is tight at the current parameters and lies below the true log‑likelihood everywhere else. For each data point we introduce a distribution Q over the latent variable Z. By writing the log‑likelihood as an expectation over Q and applying Jensen’s inequality to the concave log function we obtain a lower bound. The bound becomes tight when Q is chosen as the posterior P(Z|X,θ), i.e., the conditional probability of each component given the current parameter guess. This choice makes the surrogate touch the true likelihood at the current θ and guarantees that maximizing the surrogate cannot decrease the true likelihood.

M‑Step: Updating Means, Covariances, and Mixing Proportions

Given the responsibilities from the E‑step, the M‑step maximizes the expected complete‑data log‑likelihood, which reduces to weighted maximum‑likelihood estimates for a Gaussian.

  • The mean of component j is updated as the responsibility‑weighted average of the data points.
  • The covariance of component j is updated as the responsibility‑weighted second central moment around the new mean.
  • The mixing proportion π_j is updated as the average responsibility for component j (ensuring they sum to one, typically via a Lagrange multiplier). These updates are obtained by setting derivatives of the surrogate to zero.

Connection to K‑Means and Monotonic Convergence

EM with Gaussian mixtures generalizes K‑means: K‑means uses hard assignments and updates means only, whereas EM uses soft responsibilities and also estimates covariances and mixing weights. Because the surrogate is tight at the current parameters and concave, each EM iteration increases (or leaves unchanged) the true log‑likelihood, guaranteeing monotonic convergence to a local maximum or saddle point.

Principal Component Analysis (PCA)

PCA finds orthogonal directions that capture the largest variance in centered data, providing a low‑dimensional representation.

Centering, Scaling, and the Variance Maximization View

First, data are centered by subtracting the mean so that the first principal component describes directions of spread around the origin. Optionally, each feature is scaled to unit variance to prevent features with larger raw scales from dominating the variance criterion. After centering, PCA seeks a unit vector u that maximizes the variance of the projected data, equivalently minimizes the sum of squared perpendicular residuals.

Eigen‑Decomposition Interpretation and Component Selection

The maximization problem reduces to an eigenvalue problem of the empirical covariance matrix (XᵀX/(n‑1)). The eigenvectors are the principal components; the associated eigenvalues equal the variance explained by each component. Eigenvalues are ordered decreasingly, so the first eigenvector gives the direction of maximal variance, the second gives the next orthogonal direction of maximal residual variance, and so on. Projecting data onto the top k eigenvectors yields a k‑dimensional representation that retains the most variance.

Practical Caveats and When PCA Fails

PCA assumes that the directions of interest correspond to well‑separated eigenvalues of the covariance matrix. If eigenvalues are close, the estimated eigenvectors can be unstable, leading to different components on new data. The method also does not handle missing values; missing data must be imputed or discarded beforehand. Finally, PCA is only appropriate when the goal is to preserve variance; if the predictive signal lies in low‑variance directions, PCA may discard useful information.

Sources