3.1 Principal Component Analysis

This chapter starts the unsupervised learning module. From here on, there are no labels: just data, and the question of what structure it has.

Fair warning: this chapter is heavy on linear algebra. We will look at matrices in several ways: as tables that store data (the view you are used to), as linear transformations, sometimes row by row, and sometimes column by column. You don’t need to master every linear algebra fact behind the scenes, but take the steps below slowly.

Dimensionality reduction

Recall: feature transformations \(\phi : \mathbb{R}^d \to \mathbb{R}^k\), mapping data into an “embedding space,” can be helpful! For example, for visualization, or for better downstream prediction. We have already used several: bias lifting, polynomial features, and the implicit transformations behind kernels.

There are good reasons to want a lower-dimensional representation. High-dimensional data can be very noisy, and, as we saw in Chapter 2.3, distances lose their geometric meaning in high dimensions.

Task (dimensionality reduction). Given \(x_1, \dots, x_n \in \mathbb{R}^d\) and \(k < d\), find a “good” transformation \(\phi : \mathbb{R}^d \to \mathbb{R}^k\) to produce embeddings \[ z_i := \phi(x_i) \in \mathbb{R}^k. \] Think of \(d\) as very large, a thousand or a million, and \(k\) as very small. If you want to visualize the data, \(k = 2\).

Question: what does “good” mean here?

In supervised learning this was easy to answer: compare predictions with labels. Now there are no labels, so we need a new criterion.

Principal component analysis

Idea. A good embedding should keep enough information that we can reconstruct \(x_1, \dots, x_n \in \mathbb{R}^d\) from \(z_1, \dots, z_n \in \mathbb{R}^k\): \[ x \in \mathbb{R}^d \;\xrightarrow{\;\phi\;}\; z \in \mathbb{R}^k \;\xrightarrow{\;???\;}\; \hat x \in \mathbb{R}^d, \] with each reconstruction \(\hat x\) close to the original \(x\).

Without this requirement, the problem would be trivial. We could map every point to the same point in \(\mathbb{R}^k\): a perfectly valid transformation, and completely useless, because all information about the data is lost. A good transformation does the opposite.

Restricting to linear maps

This idea is still too abstract to optimize. So, as usual, we start with the simplest transformations we can parameterize: linear ones.

Let’s restrict to linear maps \(\phi(x) := Ux\) for some \(U \in \mathbb{R}^{k \times d}\) with orthonormal rows. \(U\) must be \(k \times d\) so that it maps \(\mathbb{R}^d\) to \(\mathbb{R}^k\).

Orthonormal rows mean:

For a general matrix, it is not obvious how to undo the transformation. With orthonormal rows there is a natural way, \(U^\top\): \[ x \in \mathbb{R}^d \;\xrightarrow{\;U\;}\; z \in \mathbb{R}^k \;\xrightarrow{\;U^\top\;}\; \hat x \in \mathbb{R}^d. \]

You can think of \(U^\top\) as an inverse of \(U\) for this special case. If this is not yet intuitive, it is worth working through on your own; Chapter 3.2 visualizes it.

The learning objective

Now “good” has a precise meaning. Encode each point with \(U\), decode with \(U^\top\), and measure how far the reconstruction is from the original:

\[ \min_U \sum_{i=1}^n \underbrace{\|x_i - U^\top U x_i\|^2}_{\text{reconstruction error}} \quad\text{where } U \in \mathbb{R}^{k \times d} \text{ has orthonormal rows}. \]

Think of \(U^\top U x_i\) as a “prediction” and \(x_i\) itself as its “label.”

Optimizing over matrices is hard. A first simplification (you will show this in Homework 3): the objective above is equivalent to \[ \max_U \sum_{i=1}^n \|Ux_i\|^2 \quad\text{where } U \in \mathbb{R}^{k \times d} \text{ has orthonormal rows}. \] That is, minimizing the reconstruction error is the same as maximizing the total squared length of the embeddings.

Designing \(U\) for \(k = 1\)

Let’s now design \(U\) for the simplest, and hardest, case: embedding the data onto a single line. Then \(U\) has one row: \[ U = \big[\; \text{---}\; u_1^\top \;\text{---} \;\big] \in \mathbb{R}^{1 \times d}. \] (Lowercase \(u_1\) is a vector; uppercase \(U\) is a matrix.)

Goal: \[ \max_{u_1} \sum_{i=1}^n \|u_1^\top x_i\|^2 = \max_{u_1} \sum_{i=1}^n (u_1^\top x_i)^2 \quad \text{where } u_1 \in \mathbb{R}^d \text{ with } \|u_1\| = 1. \] Since \(u_1^\top x_i\) is just a number, its squared norm is its square. We now look for a single unit vector, and no longer need to worry about orthogonality.

Observation.

So we want to solve \[ \max_{u_1} \|Xu_1\|^2 \quad \text{where } u_1 \in \mathbb{R}^d,\ \|u_1\| = 1, \quad Xu_1 \in \mathbb{R}^n. \]

This form invites another view of \(X\): not as a table of data, but as a transformation \(X : \mathbb{R}^d \to \mathbb{R}^n\). We are looking for the direction that \(X\) stretches the most. For a general matrix that is not easy to see directly, so we decompose \(X\) into pieces that are easier to reason about.

The singular value decomposition

Theorem (singular value decomposition)

Any matrix \(X \in \mathbb{R}^{n \times d}\) can be decomposed into \[ \underbrace{X}_{n \times d} = \underbrace{W}_{n \times n}\; \underbrace{\Sigma}_{n \times d}\; \underbrace{V^\top}_{d \times d}, \] where

Read \(X = W\Sigma V^\top\) from right to left: rotate, then scale each coordinate, then rotate again. A diagonal matrix is the easiest kind of matrix to work with. Multiplying by \(\Sigma\) just scales each coordinate by \(\sigma_j\). So the theorem says that in the right coordinates, every matrix behaves like a diagonal matrix.

Remark: how \(X\) acts on \(v_1, \dots, v_d\)

Notice what happens when we multiply \(X\) by \(v_1\). Multiply from right to left:

So \[ Xv_1 = W\Sigma V^\top v_1 = W\Sigma \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix} = W \begin{bmatrix} \sigma_1 \\ 0 \\ \vdots \\ 0 \end{bmatrix} = \sigma_1 w_1 \in \mathbb{R}^n. \] Similarly, \(Xv_j = \sigma_j w_j\) for \(j = 1, \dots, d\).

Multiplying \(X\) by one of these special directions involves no matrices at all: \(X\) simply stretches \(v_j\) by \(\sigma_j\) and points it along \(w_j\).

Try it yourself

Using \(Xv_j = \sigma_j w_j\), can you find the unit vector \(u_1\) that maximizes \(\|Xu_1\|^2\)? Hint: write \(u_1\) as a combination of \(v_1, \dots, v_d\). Chapter 3.2 finishes the derivation.