Example: Principal Components Analysis

Lossy compression of points

Picture 1,000 pins strung along one straight road. Two numbers per pin (east, north) is more than you need; the distance along the road says almost everything.

Below, the decoder is a line through the origin. Drag across the cloud to swing it. The orange sticks are what gets lost.

Along the cloud, the sticks shrink. Across it, they grow. The lower chart plots the total squared stick length against the angle: one smooth valley.

Principal components analysis (PCA) is that idea as an algorithm. The book derives it from basic linear algebra, and so will we, one small step at a time.

• You have points , each a list of numbers, so lives in .
• For each point you store a shorter code in , with . Shorter means less memory.

• The encoder writes the code, . The decoder rebuilds a point, so that .
• The rebuild is not exact. This is lossy compression: less memory, a little precision gone. We want to lose as little as possible.

Encoder, decoder and constraints

A decoder is a recipe. PCA picks the simplest recipe there is, one matrix multiplication:

has rows and columns. Each column is an arrow in , and the code says how far to walk along each arrow. With one column, the walk stays on one line: the line from the demo.

Two rules keep the arrows tidy. The columns must be orthogonal, meaning every two different columns have dot product 0, which keeps the best code easy to find. Each column must also have unit norm, meaning length 1.

Entry of is the dot product of columns and . Zeros off the diagonal mean orthogonal, ones on it mean length 1. (The book notes that is still not an “orthogonal matrix” unless , because it is not square.)

Drag the big point and the tip of the teal arrow. Then slide the code until the purple dot lands on the hollow circle, the best possible rebuild.

The rebuilt point can only sit on the line, so the best one is the foot of the perpendicular. The lower chart is a parabola with one lowest point. Now stretch the arrow to length 2 and press Set the code to its best value: the hollow circle stays put, and the code value halves.

The optimal code

Given the decoder, which code rebuilds best? The book answers: the one that puts nearest to . Here means “the that makes what follows smallest”.

The book squares the norm. For non-negative numbers, squaring keeps the order of any two candidates, so the winner does not change:

Now expand the square. Step through the algebra, one line at a time. Each line is clickable too.

The trick of dropping a constant deserves a look before you trust it.

Same bowl, shifted down. To find its bottom, the book uses calculus (Section 4.3): at the bottom of a smooth bowl the gradient, the vector of slopes, is zero.

The slopes of the two terms are and . Setting their sum to zero gives

That is the whole result: the best code is the dot product of the point with each column. No search needed.

Check Equations 2.63 to 2.65 below. The demo takes and , a fixed point and a fixed . Drag the black point over the map. It compares the formula’s gradient with one measured by nudging each code entry.

The contours are circles around . The arrow always points uphill, directly away from the center, and is twice as long as the distance to it.

Encoder and reconstruction

The optimal code costs one matrix-vector product. That is the encoder:

Entry of says how far reaches along column of . Decode the code and you get the PCA reconstruction:

Think of as a lamp that casts every point’s shadow onto the line or plane spanned by the columns. A shadow of a shadow is the shadow again.

Here is a seeded 3D cloud. Drag on the picture to swing the first column, or use the sliders, and watch the sticks. Try both tabs.

With a plane, each point costs 2 numbers instead of 3, and the error is lower than with a line, since every line lies inside some plane. The last two columns of the table are equal: the shadow of a shadow.

Choosing the decoder for all points

The code was best for one point. But a single decodes every point, so now all of them vote. The book minimizes the total squared error over all coordinates of all points (the Frobenius norm, a square root of that total):

To find the algorithm, start with . Then is one column of length 1, and plugging in Equation 2.67 gives

Next, stack the points as rows of a design matrix , so row is . The whole sum becomes one matrix norm:

See it with your own eyes. Swing the line, then click a point to read its row of the error matrix.

All four forms give the same value at every angle, and it is the same valley as in Section 1. Equation 2.72 is the form we keep, because matrices obey the trace rules of Section 2.10.

The trace derivation

The goal: turn the error into one number that is easy to maximize. The tools are the trace rules of Section 2.10: the squared Frobenius norm is a trace (Equation 2.49), a trace survives a transpose (2.50), and you can rotate the factors of a product inside a trace (2.51, 2.52). Step through the chain.

Now check every line with numbers. The cloud is the seeded one from Section 1. Stretch away from length 1 and see which lines break.

At length 1, neighboring rows agree except where a step dropped a constant (2.77) or flipped a sign (2.83). Off length 1, rows 2.79 and 2.81 split, because 2.81 used the constraint. The last row is the quadratic form, and the verdict of the derivation: the best direction makes this one number as large as possible.

The first principal component

We want the unit vector that makes biggest. The book says to use eigendecomposition: the answer is the eigenvector of with the largest eigenvalue. It does not prove this. Here is a short argument, added for this lesson.

The matrix is symmetric, so (Section 2.7) it has orthonormal eigenvectors and real eigenvalues . Write in that basis and the quadratic form becomes

The weights are never negative and add up to 1. So the form is a weighted average of the eigenvalues, like a class average that can never beat the best grade. It reaches only when all the weight sits on , that is when .

Drag across the cloud to aim a line along what you think is its longest direction. The principal directions stay hidden until you tick Reveal.

The lower chart traces the quadratic form against your angle. Its peak, of height , sits at the first eigenvector, and its lowest point, , at the second. The error of the first component is .

Now provoke a failure. The derivation looks for directions through the origin. If the cloud sits far from the origin, the offset swamps the shape.

Several components and the algorithm

For the book states the pattern: holds the eigenvectors with the largest eigenvalues. It leaves the proof as an exercise (induction). A short argument, added here, follows the same steps as before and gives, for orthonormal columns,

So the error is a constant minus a quantity to maximize. That trace equals , where says how much of eigenvector lies inside the span of the columns. Each is between 0 and 1, and they add up to . To score highest, put full weight on the biggest eigenvalues. What is left over is the error:

The whole algorithm, with an eigendecomposition doing the heavy lifting:

1. Subtract the mean from the data and stack the points as rows of .
2. Form and compute its eigenvectors and eigenvalues.
3. Pick and let the columns of be the eigenvectors of the largest eigenvalues.
4. Encode each point with .
5. Reconstruct with . The error is the sum of the discarded eigenvalues.

At the first component leaves the two small eigenvalues as error. At only the third remains. At nothing is lost, because is only a rotation. Throw some random subspaces: none beats the PCA one, which is what the derivation promised.

• PCA compresses points in into codes in . The decoder is with .
• For a given decoder the best code is (Equations 2.54 to 2.65). Encoder , reconstruction .
• For all points, the error becomes a constant minus , so the best maximizes that form (Equations 2.72 to 2.84).
• The maximizer is the top eigenvector of . In general holds the top eigenvectors, and the error is the sum of the others.
• Center the data first.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 2.12 (pages 48–52), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.