Stanford CS229 Machine Learning | Spring 2026 | Lecture 9: K-Means and GMM (non-EM)
This lecture provides a deep dive into unsupervised machine learning algorithms, focusing on K-Means clustering and its probabilistic extension, Gaussian Mixture Models (GMM). The core mathematical framework for solving GMM is the Expectation-Maximization (EM) algorithm. Key concepts include understanding how to model structure without explicit labels, utilizing latent variables, and employing convex analysis via Jensen's inequality to derive the iterative estimation procedure.
Key takeaways
-
Unsupervised vs. Supervised Learning
2:00
Unlike supervised learning (where labels define separation), unsupervised learning aims to model inherent structure or clusters within unlabeled data, making it a fundamentally more challenging problem that requires stronger assumptions and accepting weaker guarantees.
-
K-Means Clustering
5:50
K-Means is an iterative algorithm where points are assigned to the nearest cluster center ($oldsymbol{ ext{mu}}_i$). The process involves two steps: (1) assigning each point to its closest $oldsymbol{ ext{mu}}$, and (2) recalculating the new cluster centers based on the arithmetic mean of all assigned points. Finding the optimal clustering is NP-hard, meaning initialization matters.
-
Gaussian Mixture Models (GMM)
10:50
GMMs are a probabilistic relaxation of K-Means, modeling data as mixtures of Gaussian distributions. Instead of hard assignments, points are assigned probabilities to belong to each source/cluster. The model is defined by means ($oldsymbol{ ext{mu}}$), covariances ($oldsymbol{ ext{Sigma}}$), and mixing proportions ($oldsymbol{f}$).
-
Expectation-Maximization (EM) Algorithm
17:30
The EM algorithm is used to estimate the parameters of latent variable models like GMM. It alternates between two steps: the E-step (calculating the probability $W_{ij}$ that each point belongs to each source given current parameter estimates) and the M-step (re-estimating all model parameters, including means and covariances, based on these probabilities).
-
Convexity and Jensen's Inequality
30:00
The EM algorithm relies on convex analysis. Convex functions are those where the line segment connecting any two points lies above the function graph (e.g., $x^2$). Jensen's inequality is used to derive a lower bound for the log-likelihood function, allowing the complex optimization problem to be solved iteratively.