This chapter reviews the unsupervised learning module: PCA (3.1–3.2), k-means (3.3) and Gaussian mixture models (3.4). Each method is summarized the same way: the data, the learning objective, and the learning algorithm. Practice problems with fold-out answers are at the end.
Different notions of “structure” give different methods. In this module we looked at two:
Why the objective is a reconstruction error. The rows \(u_1, \dots, u_k\) of \(U\) are unit vectors that are pairwise orthogonal, so they form a coordinate system for a \(k\)-dimensional subspace of \(\mathbb{R}^d\).
So \(U^\top U x_i\) is the reconstructed input, and we can compare it with \(x_i\) directly. Without orthonormal rows, \(U^\top\) would not undo \(U\) in this geometric way.
Why the SVD helps. For \(k = 1\), the PCA objective is \(\max_{\|u_1\|_2 = 1} \|X u_1\|^2\). The data matrix itself has no special structure, but the SVD writes it as a product of three matrices that do. Read the product from right to left:
| matrix | shape | structure |
|---|---|---|
| \(V^\top\) | \(d \times d\) | orthonormal rows \(v_1^\top, \dots, v_d^\top\) (directions in \(\mathbb{R}^d\)) |
| \(\Sigma\) | \(n \times d\) | diagonal; the \(\sigma_1, \dots, \sigma_d\) are the singular values |
| \(W\) | \(n \times n\) | orthonormal columns \(w_1, \dots, w_n\) |
Since \(X v_j = \sigma_j w_j\), writing \(u_1\) in the basis \(v_1, \dots, v_d\) makes the objective easy to maximize: put all the weight on \(v_1\), the direction with the largest singular value. For centered data, these directions are also the directions of maximum variance.
You should know that the SVD exists and what each of the three matrices looks like. You don’t need to know how to compute it.
PCA only finds linear dimensionality reductions. Like ridge regression and the SVM, PCA can be kernelized, which gives a nonlinear dimensionality reduction method (kernel PCA). We didn’t cover it in this course, but you now have all the ingredients.
This is the same objective as in 3.3, written with the assignments as explicit variables: minimizing over \(c_i\) for fixed centers gives back \(\min_j \|x_i - \mu_j\|^2\).
The centers are continuous variables, but the assignments are discrete, which makes the problem non-convex and NP-hard; gradient-based methods don’t apply. Lloyd’s algorithm splits the variables into two sets and alternately improves one set while holding the other fixed. The result depends on the initialization and can be far from optimal.
k-means gives a hard label to every point, even ones we aren’t sure about. To reason about uncertainty, we write down a probabilistic model. The mixture part says the data has distinct clusters, and the Gaussian part says each cluster is described by a Gaussian.
Like Lloyd’s algorithm, EM depends on the initialization and can converge to a poor solution.
| PCA | k-means | GMM | |
|---|---|---|---|
| structure | \(k\)-dim. linear subspace | \(k\) clusters | \(k\) clusters |
| output | \(U \in \mathbb{R}^{k \times d}\); embeddings \(U x_i\) | centers \(\mu_j\); hard labels \(c_i \in [k]\) | \(\theta\); soft labels \(w_i^{(j)} \in (0, 1)\) |
| objective | min. reconstruction error | min. squared distance to centers | max. likelihood |
| algorithm | SVD (exact, closed form) | Lloyd’s (approximate) | EM (approximate) |
| depends on init.? | no | yes | yes |
These problems were written for this book; they are not from past exams.
1. PCA by hand. Consider the four points \((3, 3)\), \((-3, -3)\), \((1, -1)\), \((-1, 1)\) in \(\mathbb{R}^2\).
Yes: the four points sum to \((0, 0)\).
\(X^\top X = \begin{bmatrix} 20 & 16 \\ 16 & 20 \end{bmatrix}\). Its eigenvectors are \(\tfrac{1}{\sqrt2}(1, 1)\) with eigenvalue \(36\) and \(\tfrac{1}{\sqrt2}(1, -1)\) with eigenvalue \(4\). The right singular vectors of \(X\) are the eigenvectors of \(X^\top X\), and \(\sigma_j^2\) are the eigenvalues, so \(v_1 = \tfrac{1}{\sqrt2}(1, 1)\) with \(\sigma_1^2 = 36\). You can also see this without any algebra: the points spread out much more along the line \(y = x\).
Projecting onto \(v_1\) keeps the first two points exactly. Each of the last two points lies entirely in the direction \(\tfrac{1}{\sqrt2}(1, -1)\), at distance \(\sqrt2\), so each contributes \(2\). The total reconstruction error is \(4 = \sigma_2^2\). (In general, the reconstruction error with \(k\) components is \(\sigma_{k+1}^2 + \dots + \sigma_d^2\).)
2. Lloyd’s algorithm. Run k-means with \(k = 2\) on \(x = 0, 1, 4, 9, 10\), starting from \(\mu_1 = 0\), \(\mu_2 = 1\). (No ties occur.) Give the final assignments, centers and objective.
| round | assignments | centers after update |
|---|---|---|
| 1 | \(\{0\}\), \(\{1, 4, 9, 10\}\) | \(\mu_1 = 0\), \(\mu_2 = 6\) |
| 2 | \(\{0, 1\}\), \(\{4, 9, 10\}\) | \(\mu_1 = 0.5\), \(\mu_2 \approx 7.67\) |
| 3 | \(\{0, 1, 4\}\), \(\{9, 10\}\) | \(\mu_1 \approx 1.67\), \(\mu_2 = 9.5\) |
| 4 | \(\{0, 1, 4\}\), \(\{9, 10\}\) | no change: stop |
In round 3, the point \(4\) switches clusters: it is \(3.5\) from \(\mu_1 = 0.5\) but \(3.67\) from \(\mu_2 = 7.67\). The final objective is \((5/3)^2 + (2/3)^2 + (7/3)^2 + 0.5^2 + 0.5^2 \approx 9.17\).
3. Can the objective go up? Explain why the k-means objective never increases during Lloyd’s algorithm.
Each step solves its half of the problem exactly. With the centers fixed, assigning each point to its closest center gives the smallest possible value of \(\|x_i - \mu_{c_i}\|^2\) for every \(i\), so the objective can’t go up. With the assignments fixed, the mean of the points in \(S_j\) is the point that minimizes \(\sum_{i \in S_j} \|x_i - \mu\|^2\) (set the gradient \(2 \sum_{i \in S_j} (\mu - x_i)\) to zero), so this step can’t increase the objective either. Since there are only finitely many possible assignments, the algorithm must eventually stop. But it stops at a local optimum, which can be poor.
4. Choosing \(k\). Why can’t we choose \(k\) for k-means by picking the value with the smallest objective, or by cross-validation as in supervised learning? What can we do instead?
The optimal objective never increases as \(k\) grows, and with \(k = n\) it is \(0\) (every point is its own center), so the smallest objective always favors the largest \(k\). Cross-validation needs labels to measure performance on held-out data, and there are none. Instead, we can use the elbow method (plot the objective against \(k\) and look for where improvement slows down), or domain knowledge about how many groups are meaningful for the application.
5. The E-step and the prior. Consider a GMM with \(d = 1\), \(k = 2\), \(\pi = (0.2, 0.8)\), \(X \mid C = 1 \sim N(0, 1)\), \(X \mid C = 2 \sim N(2, 1)\). Compute \(w^{(1)}\) for (a) \(x = 1\) and (b) \(x = 0\). Use \(\tfrac{1}{\sqrt{2\pi}} \approx 0.399\) and \(e^{-2} \approx 0.135\).
\(x = 1\) is equally far from both means, so the two conditional densities are equal and cancel: \(w^{(1)} = \frac{0.2}{0.2 + 0.8} = 0.2\). The prior decides.
\(p(0 \mid 1) \approx 0.399\) and \(p(0 \mid 2) \approx 0.399 e^{-2} \approx 0.054\). So \[ w^{(1)} \approx \frac{0.2(0.399)}{0.2(0.399) + 0.8(0.054)} \approx \frac{0.080}{0.080 + 0.043} \approx 0.65. \] Even a point sitting exactly at the center of cluster 1 is only about 65% likely to belong to it, because cluster 2 is four times as common.
6. The M-step. Two points have soft assignments \(x_1 = -1\) with \(w_1 = (0.9, 0.1)\) and \(x_2 = 2\) with \(w_2 = (0.2, 0.8)\). Compute the updated \(\pi_1\), \(\mu_1\) and \(\mu_2\).
\[ \pi_1 = \tfrac{0.9 + 0.2}{2} = 0.55, \qquad \mu_1 = \frac{0.9(-1) + 0.2(2)}{0.9 + 0.2} \approx -0.45, \qquad \mu_2 = \frac{0.1(-1) + 0.8(2)}{0.1 + 0.8} \approx 1.67. \] Remember to divide by the total weight of the cluster (\(1.1\) and \(0.9\)), not by \(n\).
7. Counting parameters. How many numbers does it take to specify a GMM with \(k\) clusters in \(\mathbb{R}^d\), with full covariance matrices? How does this compare with k-means?
That’s \((k - 1) + kd + k\,d(d+1)/2\) in all. k-means only has the \(kd\) numbers for the centers. For large \(d\), the covariances dominate, which is one reason people often restrict GMMs to diagonal or spherical covariances.
8. Hard versus soft. Two points lie exactly halfway between two k-means centers. What does k-means say about them, and what would a GMM say?
k-means breaks the tie arbitrarily, so the two points may end up in different clusters, with nothing in the output indicating that either assignment was a coin flip. If the two clusters have the same prior and covariance, a GMM gives each point weights \((0.5, 0.5)\), making the uncertainty explicit. With different priors or covariances, the GMM weights would lean toward the larger or wider cluster.