This is where everything clicks into place.

Back in Part 1 & Part 2, we saw that our ultimate goal is to find these vectors defining the direction of the greatest variance. Given the insights we have learned so far, this process can only make sense now.

I assume you know the basics of linear transformations, eigenvectors and eigenvalues, since there’s no point of repeating what has been thoroughly established. But if you need some insight, watch this great tutorial.

Let’s dive in.

What Do You Want?

You can’t solve a problem you haven’t defined clearly, that’s why we should consider what do we exactly mean by finding the directions of greatest variance. It’s only natural to begin asking ourselves what variance is.

As we saw previously, the variance along the x-axis is the variance of the feature represented by that axis, i.e. the variance of the x-coordinates of the dataset. To generalize this notion to any line in space, a simple observation is in order:

The x-coordinates of the data points are merely their projections on the x-axis.

Using this fact, we can easily find the variance along any line by projecting our points on the unit vector representing the line, and then taking the variance of these projections.

If A is our (n x d) mean-centered data matrix, where n is the number of examples (points) and d is the number of dimensions (features), and v is the unit vector of our line, then, using Floor #1 from the Part 2, projecting the points becomes a snap:

where p is an (n x 1) column vector, in which each element is the length of projection for each point.

Now that we have the lengths in a column vector, we can use Floor #5 to find their variance:

Suddenly, the covariance matrix of our data, C, popped up! This extremely curious appearance will serve us greatly. Given our definition of variance along any line, we can reformulate our problem by saying that we want to find the vector v such that σ² is maximum. It’s evident from the above definition that this vector depends solely on the value of C, which compels us to a careful study of this curious matrix.

Curious Covariance

In the last part we learned that an (n x d) data matrix has a (d x d) covariance matrix, i.e. a 2D dataset has a 2x2 covariance matrix. As you should know, a matrix can be viewed as a linear transformation that maps vectors to other vectors by shearing or rotation. This is no different for our covariance matrix.

The best method to learn about a linear transformation matrix is to look at its eigenvectors — those vectors that aren’t rotated or sheared by the matrix but only scaled by an amount equal to their eigenvalues. If v is an eigenvector and λ is its eigenvalue, then:

However, the eigenvectors for the covariance matrix have special properties. The covariance matrix, being symmetric, has orthonormal eigenvectors — vectors of unit length and orthogonal to each other (proof). This gives rise to the following identities:

The elegance of eigenvectors comes from a simple fact: any vector in space can be expressed as a linear combination of the eigenvectors of a matrix. The reason behind this elegance is that we can now calculate the effect of the linear transformation, represented by matrix C, on any vector, u, in terms of the eigenvectors and eigenvalues. This turns the complicated matrix multiplication procedure, C.u, into simple vector scaling. To see how this is done, notice that a (2 x 2) covariance matrix has two orthonormal eigenvectors corresponding to each dimension. Any vector u can then be expressed in terms of the two eigenvectors v1 and v2 as:

So to find the effect of the covariance matrix on any vector u:

We can now write the quantity we want to maximize, (u^T)Cu, as:

Where we used the identities of orthonormality in the last step.

The Big Surprise

Finding u that maximizes σ²=(u^T)Cu is a matter of finding k1 and k2 — the coefficients of the eigenvectors that define u. But since we are only concerned with unit vectors that define the line of greatest variance, k1²+k2²=1. Can you now guess how to maximize σ²?

The key is to notice that if λ1>λ2, then the only way to maximize σ², given the constraint k1²+k2²=1, is to assign 1 to k1 and 0 to k2, so that the largest eigenvalue λ1 dominates the sum.

This leads us to the great surprise:

The direction of greatest variance is the eigenvector of the covariance matrix that has the largest absolute eigenvalue.

For if k1=1 and k2=0, then u becomes:

That is, u, the direction of greatest variance, is the eigenvector v1 itself that has the largest eigenvalue. A direct conclusion of this is that the second largest direction of variance corresponds to the eigenvector with the second largest eigenvalue, and so forth.

Another Big Surprise

What is even more interesting is that if you look at our problem statement:

and combine it with the fact that v is an eigenvector, then:

That is

The variances in the direction of the eigenvectors are their eigenvalues.

Now What?

Alright. We have finally found the vectors we all wanted. Now what?

If you recall from Part 1, we reduced a 2D dataset into a 1D line by projecting the points on the line of greatest variance. Now that we have all the quantities we need, namely, the data matrix A, the covariance matrix C, and its eigenvectors v1, v2 that define our lines, we can carry out the projection:

Generalizing to larger dimensions is only a matter of augmenting our matrices with the extra components. If we are in 3D, the covariance matrix has 3 eigenvectors, v1, v2, v3, ordered from largest to smallest λ. But to organize our problem more neatly, we use the properties of matrix multiplication. Our problem can now be stated, as:

Where E is a diagonal matrix of the variances (eigenvalues) and V is the orthonormal matrix of the eigenvectors, arranged column-wise. Take any number of principal components (eigenvectors) that have the largest eigenvalue and project our data on them to reduce the dimensionality. If we choose v1 and v2, the plane of highest variance is now defined by them, and projecting the points on the plane is equivalent to projecting onto v1 and v2 then combining the components:

A General Procedure

The process of finding the eigenvectors of the covariance matrix is called the Eigen-decomposition of the covariance matrix, and is one of the methods for solving PCA. The name comes from the fact that if we re-organize our problem statement as:

then the matrix C has been decomposed into its eigenvectors V and eigenvalues E.

How many eigenvectors should we choose to project our data on? A rule of thumb is to choose the first n eigenvectors such that the sum of their variances (eigenvalues) is larger than 95% of the total.

We can now summarize the procedure of reducing dimensionality using PCA:

1. Mean-center the data by subtracting each feature from its mean.
2. Find the covariance matrix of the centered data C =(A^T)A.
3. Apply eigen-decomposition to C.
4. Order the eigenvectors w.r.t the eigenvalues in descending order.
5. Choose the first n eigenvectors that explain 95% of the total variance.
6. Create a matrix V, where each column is one of the n chosen vectors.
7. Project the data onto the subspace defined by V:

What’s Next

Another very interesting approach to solve PCA is Singular Value Decomposition (SVD). It is similar to eigen-decomposition but is more general and widely used in practice. But this will suffice for now so I’ll leave that to the next part.

Dimensionality Reduction For Dummies — Part 3: Connect The Dots was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

You know what, we usually make fun of those people appearing on TV or otherwise who talk confidently about stuff they really know nothing about, all while forgetting that we do the exact same thing in our heads: We approach problems we can’t define clearly, we attempt solving them with tools we really don’t know how they work, and we think that knowing the name of a concept is the same as understanding it.

You can’t hope to construct a tenth floor without first ensuring the rigidity of all the nine underneath. You can’t expect to figure out a concept without getting the hang of all the underlying ones. For this reason, we shall build the necessary floors for our understanding in this article.

It’s futile to start from zero and reinvent the wheel — that would fill fat books. But I at least assume you have a basic understanding of preliminary linear algebra and statistics. Also, don’t go on until you have read Part 1.

Have you rolled up your sleeves yet?

Floor #1 — The Inner (Dot) Product

The dot product is the length of that red line segment. That’s it.

But the simplest of things usually have the greatest implications. You may be surprised when I tell you that everything we do thereafter can be interpreted in terms of a dot product. One reason for this is that the dot product can be seen in many ways:

• It’s the projection length of vector (or point) a, onto the line defined by the unit vector b.
• It’s the closest distance to a along the line defined by b.
• It’s the ‘amount’ or component of vector a contained in the direction of b.
• It’s a measure of how close a is to b (in terms of angle).

Even its calculation is deceptively simple: if a=(1,2), b=(0.8, 0.6), then this operation can be done using matrix multiplication:

The Dot Product On Steroids

Now that our lone vector has three more friends, we need to organize the party of projecting all of them onto the line. If we denote our vectors and the unit vector to project on by:

Then we can again utilize the neatness of matrix multiplication to get each length of projection, corresponding to each vector, on unit vector b:

Where the p’s are the lengths of projections for each point (vector).

Floor #2 — The Outer Product

It’s all fine and dandy until you realize the dot product gives only the length of a segment, not the vector representing it.

To find that vector, w, we simply scale the unit vector b by the length of projection (= the dot product of a and b):

The Outer Product On Steroids

Now watch what happens when we inject steroids as we did with the dot product, i.e. when we have multiple vectors:

We want to find w1, w2, w3, w4. Remember, they are the vectors representing the lengths of projections for each point onto unit vector b:

As complicated as it may seem, all what it does is scale the unit vector b successively with each length of projection (p1, p2, p3, and p4), and store these scaled vectors row-wise in matrix W.

Now we can define the outer product between vector p, representing the lengths of projections, and vector b, the unit vector we projected on, as:

Which gives us the “vectors of projections,” one in each row.

Floor #3 — Flip The Mat And Be A Cat

When you’re stuck, ask your cat. If it tilts its head sideways as the picture above, then it wants to tell you something:

“Change you perspective, and you shall discover many interesting things.”

Or “Meow”. Whatever, let’s see how we can do that. Suppose we have the following tiny weather temperature dataset consisting of 3 examples (Days) and 2 features (Cities), with its matrix representation and 2D scatter plot:

That’s not particularly inspiring. But if we tilt our head and look at the matrix like our cat would:

we arrive at a completely different interpretation of our dataset. Now our matrix has 2 points and 3 dimensions. It looks like this:

It’s crucial to completely understand what that implies:

• The new matrix has Days (examples) as axes and Cities (features) as points. The old one had them in reverse.
• Each row in the new matrix is a single point in 3D space.
• The first row contains the x-coordinates of every example (day), one in each column. This means that the x, y, and z coordinates of the first point are the values of the x-coordinate of Day 1, Day 2 and Day 3 in the old matrix, respectively. Likewise, the second row has the y’s.
• If we have more than three days (examples), the new matrix would require a 4+ dimensional plot. However, there would still be only two points, and the vectors representing them would define a single plane that we can easily draw on paper:

So from now on, we’re going to draw that plane only. If we draw that plane and the original scatter plot side by side, we have what is called a Biplot:

Floor #4 —A Vast New World

Now we can explore the vast new world of the dual space. In order to understand it better, we have to see the connection between the two worlds:

Claim #1: The variance of the dataset in the x-direction is the dot product of vector x with itself. Same for y.

Claim #2: The covariance of the dataset is the dot product of the two vectors.

Whoa.

These claims need serious justification.

Floor #5 — A Fresh Look

Let’s agree on something that will make our life easier: all dataset we’ll be dealing with are mean-centered. This means we subtract the mean of each feature from every point, so that the dataset will be centered at the origin. This doesn’t change the structure of our data at all, but eases calculations.

1. Variance

In the dual space, the vector x’s components are the x-coordinates of each example, i.e. Vx=(x1, x2, x3). Likewise, Vy=(y1,y2,y3). Remember that the variance along x is the average squared deviations of the x coordinates from their mean. But since the mean is zero, it’ll be:

But that’s exactly the dot product of vector x with itself, or, equivalently, its squared length:

Where I have intentionally ignored the factor 1/3 to make things easier, as we are now only interested in the relations of quantities.

2. Covariance

Remember from Part 1 that we interpreted covariance as a measure of how accurately one variable can be predicted from another. To put this in quantitative terms, we assume the simplest kind of relationship: y is a certain multiple of x, or y=mx (a line through the origin). The more faithfully our variables exhibit this relationship, the larger the covariance, and vice versa.

If you look closely at the animation above Claim #2, you’ll find that the more the data deviates from the line, the larger the angle between the two vectors, and hence the smaller the dot product. So the dot product is a very natural measure for covariance.

A small observation will make you realize this makes perfect sense. Remember that Vx=(x1,x2,x3) and Vy=(y1,y2,y3). If the data follows a linear relationship (y=2x), then Vy=(2*x1, 2*x2, 2*x3)=2*Vx. That is, the vectors are scalar multiples of each other, they’re collinear, and the dot product is maximum.

We can now formalize that claim by defining:

3. Covariance Matrix

The variance and covariance, both being merely dot products, can be summarized in a single matrix:

4. Generalization

Extending this idea to more that 3 point in the dataset is straightforward. We would need 4+ dimensional plot to represent the examples, but there will still be only two vectors for two features, x and y, and they will define a 2D plane that can be easily drawn, and the dot product performed. The same ideas will still hold.

The Brick House

At this point, our floors are made of bricks. You can’t live in a brick house, can you? No. We need to finish up. And we need a roof to stand on to view the big picture of how we can combine these ideas into a framework to solve PCA.

And that’s exactly what we’ll do in Part 3.

Dimensionality Reduction For Dummies — Part 2: Laying The Bricks was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.