Representation learning: compress, project, find the best line

The course begins with unsupervised learning, and within it with representation learning. The starting goal is deliberately vague: given a set of data points, understand something useful about them. Three words need pinning down: data points, understand and useful.

Data points are the easy part. Each is a vector of \(d\) real numbers, its features. Record the height, weight and age of 100 people and each person becomes a point in \(\mathbb{R}^3\), one coordinate per feature.

\(n\) is the number of data points (people, images, …) and \(d\) the number of features recorded for each.

The lecture answers "what does it mean to understand?" with a quote from the computer scientist and philosopher Gregory Chaitin: comprehension is compression. Here, comprehending, understanding and learning are treated as the same thing. If you can compress information so that only its important part remains, and that part is enough to explain the data to someone else, you have learnt from the data.

Ask of every algorithm in this course: where exactly is the compression happening?

How many numbers does it take to store these four points?

The naive answer is \(4 \times 2 = 8\). But in every point the second coordinate is twice the first. So store one representative \([1, 2]^\top\) and, for each point, one coefficient: \(-7,\ 2.5,\ 0.5,\ 0\). That is 6 numbers, and the data comes back exactly: \(\mathbf{x}_2 = 2.5 \times [1, 2]^\top = [2.5, 5]^\top\).

Two points from this example matter later.

• The representative is not unique. Any nonzero vector on the line works. With \([1/\sqrt5,\ 2/\sqrt5]^\top\) the coefficients become \(-7\sqrt5,\ 2.5\sqrt5,\ 0.5\sqrt5,\ 0\) and reconstruction is still exact. The zero vector is not allowed, because nothing can be rebuilt from it. 14:03
• The general count. \(n\) points in \(d\) dimensions take \(d \times n\) numbers raw. If they all lie on one line through the origin, \(d + n\) numbers suffice: \(d\) for the representative and one per point.

Take four points on \(y = x\), for example \([-5,-5]\), \([1,1]\), \([7,7]\) and \([10,10]\), and add one more, \(\mathbf{x}_5 = [5, 6]\), which is not on the line. One representative can no longer rebuild every point. There are three ways out:

Exact reconstruction and fewer representatives cannot both be kept. The lecture gives up exactness 21:26. Pretend the data set contained a proxy for \(\mathbf{x}_5\) on the line instead of \(\mathbf{x}_5\) itself, and compress as before.

The best proxy is the point on the line where we lose the least: the error vector we would have to add back to the proxy to recover \(\mathbf{x}\) should be as short as possible. A line through the origin is every multiple \(c\,\mathbf{w}\) of a nonzero representative \(\mathbf{w}\), so we choose the scalar \(c\):

Setting the derivative with respect to \(c\) to zero (the lecture leaves this as an exercise): \(-2w_1(x_1 - c w_1) - 2w_2(x_2 - c w_2) = 0\), so

The numerator is the dot product of \(\mathbf{x}\) and \(\mathbf{w}\); the denominator is the squared length of \(\mathbf{w}\). The same formula holds in any dimension.

Nobody tells us which points lie on the line. Off-line points are the rule, not the exception: plot height against weight for a class of 100 people and perhaps no point sits exactly on the line we would draw. An exact linear relationship between features is a myth outside physical laws. So we always use proxies, and the line itself must be found from the data.

Any line gives the same compression: one representative plus one coefficient per point. What differs is how much we lose. The red line in the lecture beats the blue one because rebuilding the data from its proxies gives a smaller reconstruction error.

Goal: find the line through the origin with the least reconstruction error.

For a line given by a unit vector \(\mathbf{w}\), add up each point's squared error. The lecture uses the average rather than the sum; the same \(\mathbf{w}\) minimizes both, and the average is easier to interpret later.

Write the squared length as a vector dotted with itself and expand. Using \(\mathbf{w}^\top\mathbf{w} = 1\):

The first term does not involve \(\mathbf{w}\), so dropping it does not change the minimizer. Minimizing \(-\tfrac1n\sum(\mathbf{x}_i^\top\mathbf{w})^2\) is the same as maximizing it without the minus sign. Finally, \((\mathbf{x}_i^\top\mathbf{w})^2 = \mathbf{w}^\top\mathbf{x}_i\,\mathbf{x}_i^\top\mathbf{w}\), and \(\mathbf{w}\) does not depend on \(i\), so it comes out of the sum:

\(\frac1n\sum \mathbf{x}_i\mathbf{x}_i^\top\) is the usual covariance matrix only when the data has mean zero. Lecture 5 adds that step (centring) for a different reason. The lecture says more about why a covariance appears in an error-minimization problem later; for now the takeaway is that the problem has a well-understood eigenvector solution.

Treat the best-line solver as a black box: data goes in, a line comes out. That line is not always satisfying. Suppose 3-D data points all lie on a plane. The best line will lie in that plane (a line outside it would cost more to project onto), but the plane is the real structure, and a single line misses half of it.

The part we have been calling "error" may then carry information. Pure noise would point every which way. Here the error vectors, the residues \(\mathbf{x}_i - (\mathbf{x}_i^\top\mathbf{w})\mathbf{w}\), all line up along one direction.

A possible algorithm L5 · 7:42

1. Repeated best-line fitting
2. Input \(\{\mathbf{x}_1, \dots, \mathbf{x}_n\}\), \(\mathbf{x}_i \in \mathbb{R}^d\).
3. Find the best line \(\mathbf{w}_1\): minimize the reconstruction error, equivalently maximize \(\mathbf{w}^\top C\mathbf{w}\).
4. Replace each point by its residue: \(\mathbf{x}_i \leftarrow \mathbf{x}_i - (\mathbf{x}_i^\top\mathbf{w}_1)\,\mathbf{w}_1\).
5. Repeat on the residue data set to get \(\mathbf{w}_2\), then \(\mathbf{w}_3\), and so on, at most \(d\) times.

Every line here passes through the origin, because a proxy is a coefficient times the representative and a coefficient of 0 must give the origin. If the data sits far from the origin, the best line through the origin can miss the direction in which the data is spread. The lecture's example: the x-axis can beat the line that follows the data.

The fix is to centre the data before anything else: compute the mean and subtract it from every point. The new data set has its mean at the origin, so lines through the origin now follow the spread.

L5 ends with four questions. Answering them turns the procedure into the first algorithm of the course, a representation learning algorithm for unsupervised learning.

1. How do we solve \(\max_{\lVert\mathbf{w}\rVert=1} \mathbf{w}^\top C\mathbf{w}\)? (The hint: an eigenvector.)
2. How many times should the residue step be repeated?
3. Where exactly is the compression happening once there are several lines?
4. With several lines and several coefficients per point, what representation are we actually learning?

Representation learning

Finding a compact description of data points that keeps what matters.

Comprehension is compression

The course's running theme: learning means keeping only the important part of the data.

Representative

One vector shared by the whole data set that spans the chosen line.

Coefficient

The single number per point that scales the representative, \(\mathbf{x}^\top\mathbf{w}\) for unit \(\mathbf{w}\).

Proxy

The point on the line that stands in for an off-line point: its projection \((\mathbf{x}^\top\mathbf{w})\mathbf{w}\).

Projection

The closest point on a line to a given point; the error is perpendicular to the line.

Reconstruction error

Average squared distance between points and their proxies, \(f(\mathbf{w})\).

Covariance matrix \(C\)

\(\frac1n\sum\mathbf{x}_i\mathbf{x}_i^\top\) for centred data; the best line is its top eigenvector.

Residue

What is left of a point after removing its proxy: \(\mathbf{x} - (\mathbf{x}^\top\mathbf{w})\mathbf{w}\).

Centring

Subtracting the mean from every point so lines through the origin follow the data.