Gaussian Mixture Models and the EM Algorithm

• Explain how a Gaussian mixture model generalizes k-means by assigning each point a soft probability of cluster membership instead of a single hard assignment.
• State the EM algorithm's two steps (E-step and M-step) and explain what each one computes.
• Trace one full E-step and M-step by hand on a small worked example.
• Explain the sense in which k-means is a special, simplified case of a Gaussian mixture model fit by EM.

K-means, just covered, assigns each point to exactly one cluster — a hard assignment with no notion of uncertainty. Real clusters, however, often overlap: a point sitting between two visually distinct groups is genuinely ambiguous, and forcing it into one cluster or the other discards real information. A Gaussian mixture model (GMM) makes this softer and more expressive: instead of k cluster centers, it fits k full Gaussian distributions — reusing the normal distribution already covered in foundations/probability-statistics, now in its multivariate form — and instead of a hard 0/1 assignment, gives each point a probability of belonging to each cluster.

The model

A GMM assumes the data is generated by a mixture of k Gaussian distributions, each with its own mean μⱼ, covariance Σⱼ, and mixing weight πⱼ (the overall proportion of data coming from cluster j, with Σⱼ πⱼ = 1). The overall probability density at a point x is:

text
p(x) = Σⱼ πⱼ · N(x; μⱼ, Σⱼ)

Fitting a GMM means estimating all the πⱼ, μⱼ, and Σⱼ parameters from unlabeled data — a genuinely harder estimation problem than fitting a single Gaussian (as GDA did earlier in this discipline, with known class labels), because the "which cluster generated this point" assignment is now itself unknown and must be estimated jointly with the distributions' parameters.

The EM algorithm

The Expectation-Maximization (EM) algorithm fits a GMM by alternating between two steps, directly paralleling k-means's assign/update loop but in a soft, probabilistic form:

• E-step (Expectation): given the current parameter estimates, compute, for every point and every cluster, the probability that point belongs to that cluster (its "responsibility") — a soft assignment, not a hard one.
• M-step (Maximization): given these soft assignments, recompute each cluster's mean, covariance, and mixing weight as a weighted average over all points, weighted by their responsibility for that cluster.

These two steps are repeated until the parameters stop changing meaningfully, exactly as k-means repeats assign/update until convergence — EM is provably guaranteed to never decrease the data's overall likelihood at each step, the same monotonic-improvement guarantee that made k-means's convergence provable.

K-means as a special case of GMM/EM

K-means can be seen as a simplified, "hard" limit of a GMM fit by EM: if every cluster's covariance is forced to be the same fixed, spherical shape, and the E-step's soft responsibilities are forced to be either exactly 0 or exactly 1 (rounding each point to its single most probable cluster) rather than genuine probabilities, the EM procedure above reduces exactly to k-means's assign/update loop. GMM/EM is the more general, probabilistic version, at the cost of a harder-to-fit model with more parameters (a full covariance matrix per cluster, rather than just a center).

Example 1: A soft responsibility computation

Suppose a point x has likelihood 0.8 under cluster 1's fitted Gaussian and 0.2 under cluster 2's, with equal mixing weights π₁ = π₂ = 0.5. The E-step computes the responsibility of cluster 1 for this point using Bayes' theorem — the same formula already used for GDA and Naive Bayes earlier in this discipline:

text
responsibility(cluster 1) = (π₁ · 0.8) / (π₁ · 0.8 + π₂ · 0.2) = 0.4 / (0.4 + 0.1) = 0.4/0.5 = 0.8
responsibility(cluster 2) = 1 − 0.8 = 0.2

This point is assigned 80% to cluster 1 and 20% to cluster 2 — a soft assignment k-means could never express, since k-means would have forced this point entirely into cluster 1.

Example 2: One M-step update using soft responsibilities

Suppose 3 points have responsibilities for cluster 1 of 0.9, 0.8, 0.1 respectively, with positions x₁=(2,2), x₂=(3,3), x₃=(9,9). The M-step recomputes cluster 1's mean as a responsibility-weighted average:

text
μ₁ = (0.9·x₁ + 0.8·x₂ + 0.1·x₃) / (0.9 + 0.8 + 0.1)
   = (0.9·(2,2) + 0.8·(3,3) + 0.1·(9,9)) / 1.8
   = ((1.8+2.4+0.9)/1.8, (1.8+2.4+0.9)/1.8)
   = (5.1/1.8, 5.1/1.8) ≈ (2.83, 2.83)

The distant point x₃ still contributes to the mean, but only weighted by its small 0.1 responsibility — a much smaller pull than the two points more confidently assigned to this cluster, exactly the kind of gradual, probability-weighted influence a hard k-means assignment cannot represent.

• "GMM/EM always finds a better clustering than k-means." GMM is more expressive (it can fit elongated, overlapping, differently-shaped clusters that k-means's spherical assumption cannot), but it also has more parameters to estimate and is correspondingly more prone to overfitting on small datasets, and just like k-means, EM only guarantees convergence to a local optimum, not the global one.
• "The E-step and M-step are two independent computations that could be run in either order." They are strictly sequential and interdependent — the E-step needs the current parameter estimates to compute responsibilities, and the M-step needs those responsibilities to update the parameters — each step's output is the direct input to the next.
• "Soft responsibilities are just a minor refinement of hard cluster assignments." As Example 1 shows, soft responsibilities carry genuinely different information (uncertainty about ambiguous points near a cluster boundary) that a hard 0/1 assignment discards entirely — this is the real, substantive difference between k-means and GMM, not merely a cosmetic one.

A Gaussian mixture model generalizes k-means by fitting k full Gaussian distributions instead of k single points, and assigning each point a soft, probabilistic responsibility for each cluster rather than a hard assignment. The EM algorithm fits this model by alternating an E-step (computing responsibilities given current parameters, via the same Bayes'-theorem machinery used for GDA and Naive Bayes) and an M-step (updating parameters as responsibility-weighted averages), directly paralleling — and provably generalizing — k-means's assign/update loop, with k-means recoverable as a special, hard-assignment case of this more general framework.