Stanford CS229 Machine Learning | Spring 2026 | Lecture 9: K-Means and GMM (non-EM)
Summary
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.
Technical details
-
K-Means Algorithm
350s
Given $N$ points and an integer $K$, the algorithm initializes $K$ centers ($oldsymbol{ ext{mu}}_i$). It iteratively assigns point $oldsymbol{x}_i$ to cluster $J$ if it minimizes the distance (Euclidean distance) to $oldsymbol{ ext{mu}}_J$. The new center is then calculated as the arithmetic mean of all points assigned to that cluster. Convergence occurs when assignments and centers stabilize.
-
GMM Model Formulation
650s
The probability density function (PDF) for a point $oldsymbol{x}$ is modeled as a weighted sum of Gaussian components: $p(oldsymbol{x}) = rac{1}{Z} ext{Mixture}(oldsymbol{ ext{mu}}_j, oldsymbol{ ext{Sigma}}_j)$. The model assumes that the data are generated by multiple sources (Gaussian distributions) with different means and covariances.
-
EM Algorithm Steps
1050s
The EM algorithm iteratively estimates parameters ($oldsymbol{ ext{mu}}, oldsymbol{ ext{Sigma}}, oldsymbol{f}$): The E-step calculates the responsibility $W_{ij} = p(Z_i=j | oldsymbol{x}_i, heta^{ ext{old}})$, which is the probability that point $oldsymbol{x}_i$ belongs to source $j$. The M-step updates parameters by maximizing the expected complete log-likelihood using these responsibilities.
-
Optimization via Convex Relaxation
2000s
The optimization of the likelihood function is achieved by constructing a lower bound, $L_T( heta)$, which is guaranteed to be concave (convex relaxation). Maximizing this simpler surrogate function allows for an iterative estimation procedure that converges toward the maximum likelihood estimate.
Mentioned resources
Channel & topics
Watch on YouTube · Back to latest
This independent, AI-assisted summary is provided for commentary and informational purposes. It may contain errors or omit important context. Please watch the original video for the creator's complete presentation. Video, thumbnail, and related copyrights belong to their respective owners.