Home / MLT / Week 1

Week 1 · PCA: finding the best view of your data

Official syllabus line: Introduction; Unsupervised Learning - Representation learning - PCA

About 80 minQuiz 1 material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 3 (projection), week 4 (eigenvectors) and week 5 (symmetric matrices). If you have not done them, read the "Quick refresher" box below first.

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine taking a photo of a cool 3D statue for a flat postcard. Most pictures make it look squashed or boring. But there's one special angle where the statue looks its widest and clearest, so you can still easily tell what it is. PCA is like finding that perfect angle for your data.
Imagine describing each student with 100 quiz marks. That's too many numbers! Many quizzes might even measure similar things. PCA helps us find just a few new numbers, like two or three, that capture most of the important information. It finds directions where our data changes the most, keeping only what truly matters.
Let's see how much information we keep! If our data has 'spread' values of five, three, and two, the total spread is ten. Keeping the first direction explains 50% of the spread. Keeping the first two directions explains 80%. So, to keep at least 75% of the information, we need two directions!
For exams, remember to always 'centre' your data first! And, reconstruction error means the information you *discarded*, not what you kept. PCA is unsupervised, finding hidden patterns. It picks directions with the most 'spread,' making complex data simple and clear, like finding the best view of a statue!

The one-minute story

Think of it like this

A museum wants to put a 3D statue on a postcard, which is flat. Photograph it from the front, the top, the side... Most angles make the statue look squashed and boring. But one angle shows it spread out as widely as possible, so you can still tell what it is. PCA finds that best angle for any cloud of data.

Now imagine each student is described by 100 numbers (marks in 100 quizzes). You cannot picture a point in 100 dimensions, and many of the quizzes say nearly the same thing. PCA finds a handful of new numbers (maybe 2 or 3) that keep most of the information. Fewer numbers means faster models, cleaner pictures and less noise.

The idea in one line: look for the directions along which the data varies the most, and keep those.

The idea

Quick refresher from MLF (skip if fresh).

A projection onto a direction $\mathbf w$ (unit length) gives the coordinate $\mathbf w^T\mathbf x$ ; the "shadow" is $(\mathbf w^T\mathbf x)\mathbf w$ .
A symmetric matrix has real eigenvalues and perpendicular eigenvectors.
$\mathbf w^TC\mathbf w$ is a quadratic form; for the top eigenvector it equals the largest eigenvalue.

By the end of this week you can:

explain what unsupervised learning and representation learning mean;
run PCA step by step: centre, covariance, eigen-analysis, project;
compute variance explained and reconstruction error;
explain why "maximise variance" and "minimise reconstruction error" are the same.

Words you need

Unsupervised learning - finding structure in data that has no labels.
Representation learning - turning raw data into a better set of numbers (features) for later use.
Data matrix $X$ - here $d\times n$ : each column is one data point with $d$ features.
Centring - subtracting the mean so the cloud is centred at the origin.
Covariance matrix $C$ - how the features vary and move together.
Principal component (PC) - a unit direction of high variance; PC1 has the most, PC2 the next, and PC2 is perpendicular to PC1.
Reconstruction - rebuilding a data point from its few PCA coordinates.

Idea 1: The setup

You have $n$ data points $\mathbf x_1,\dots,\mathbf x_n\in\mathbb R^d$ . Stack them as the columns of $X\in\mathbb R^{d\times n}$ .

Step 1: Centre. Compute the mean $\bar{\mathbf x}=\frac1n\sum\mathbf x_i$ and replace every point by $\mathbf x_i-\bar{\mathbf x}$ . From now on the data has mean zero.

Step 2: Covariance.

C=\frac1n\sum_{i=1}^n\mathbf x_i\mathbf x_i^T=\frac1nXX^T\qquad(d\times d,\;\text{symmetric},\;\text{PSD})

(If your paper stores points as rows, the same matrix is $\frac1nX^TX$ . Read the convention in the question.)

Step 3: The question PCA answers. Project onto a unit direction $\mathbf w$ : each point becomes the number $\mathbf w^T\mathbf x_i$ . The spread (variance) of those numbers is

\frac1n\sum_i(\mathbf w^T\mathbf x_i)^2=\mathbf w^TC\mathbf w

Which unit $\mathbf w$ makes this largest? Maximise $\mathbf w^TC\mathbf w$ subject to $\mathbf w^T\mathbf w=1$ . The Lagrange method (MLF week 9) gives $C\mathbf w=\lambda\mathbf w$ : $\mathbf w$ is an eigenvector of $C$ , and the variance achieved is its eigenvalue $\lambda$ . So the best direction is the eigenvector with the largest eigenvalue. That is PC1. The next best direction perpendicular to PC1 is the eigenvector with the second largest eigenvalue, and so on.

The idea

The PCA recipe

Centre the data.
Form $C=\frac1nXX^T$ .
Find its eigenvalues $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_d\ge0$ and unit eigenvectors $\mathbf w_1,\dots,\mathbf w_d$ .
Keep the top $k$ eigenvectors: $W=[\mathbf w_1\cdots\mathbf w_k]$ .
New coordinates of a point: $\mathbf z=W^T\mathbf x$ ( $k$ numbers). Reconstruction: $\hat{\mathbf x}=W\mathbf z=WW^T\mathbf x$ .

Idea 2: How good is the squashed version?

Variance explained. The total variance is $\lambda_1+\dots+\lambda_d=\operatorname{trace}(C)$ . Keeping $k$ components retains

\frac{\lambda_1+\dots+\lambda_k}{\lambda_1+\dots+\lambda_d}

of it. People pick the smallest $k$ that keeps, say, 90% or 95%.

Reconstruction error. The average squared distance between points and their reconstructions is

\frac1n\sum_i\|\mathbf x_i-\hat{\mathbf x}_i\|^2=\lambda_{k+1}+\dots+\lambda_d\qquad(\text{the discarded eigenvalues})

Think of it like this

Why are "most spread out" and "least squashing loss" the same question? Each point has a length from the centre. That length splits into the shadow on your axis and the leftover sticking out sideways, and Pythagoras says $\text{length}^2=\text{shadow}^2+\text{leftover}^2$ . The total length of the cloud is fixed. So whatever you gain in shadow you lose in leftover. Maximising shadow-spread is the same as minimising leftover.

Solved example: 1. Full PCA by hand

Question. Three points in the plane are $(0,-1)$ , $(3,5)$ , $(6,2)$ . Find the principal components, the variance explained by PC1, and the reconstruction error if we keep only PC1.

Solution.

Mean: $\big(\frac{0+3+6}3,\frac{-1+5+2}3\big)=(3,2)$ . Centred points: $(-3,-3),\,(0,3),\,(3,0)$ .
Covariance: $\sum x^2=9+0+9=18$ , $\sum y^2=9+9+0=18$ , $\sum xy=9+0+0=9$ . With $n=3$ : $C=\dfrac13\begin{pmatrix}18&9\\9&18\end{pmatrix}=\begin{pmatrix}6&3\\3&6\end{pmatrix}$ .
Eigenvalues: trace $12$ , determinant $36-9=27$ : $\lambda^2-12\lambda+27=0$ , so $\lambda_1=9$ , $\lambda_2=3$ .
Eigenvectors: for 9: $(C-9I)=\begin{pmatrix}-3&3\\3&-3\end{pmatrix}$ gives $\mathbf w_1=\frac1{\sqrt2}(1,1)$ . For 3: $\mathbf w_2=\frac1{\sqrt2}(1,-1)$ .
Variance explained by PC1: $\frac9{9+3}=\mathbf{75\%}$ .
Reconstruction error with only PC1: the discarded eigenvalue, $\lambda_2=\mathbf3$ . Check it directly. Coordinates on PC1: $-3\sqrt2,\;\frac3{\sqrt2},\;\frac3{\sqrt2}$ (that is $-4.24,\,2.12,\,2.12$ ). Reconstructions: $(-3,-3)$ , $(1.5,1.5)$ , $(1.5,1.5)$ . Errors $^2$ : $0$ , $(0-1.5)^2+(3-1.5)^2=4.5$ , $4.5$ . Average $=\frac{0+4.5+4.5}3=3$ . ✓

Solved example: 2. Variance explained from eigenvalues

Question. A covariance matrix has eigenvalues $5,\,3,\,2$ . (a) Variance explained by PC1? (b) By the first two? (c) Minimum $k$ for at least 75%?

Solution. Total $=10$ . (a) $50\%$ . (b) $\frac{8}{10}=80\%$ . (c) one component gives $50\%<75\%$ , two give $80\%\ge75\%$ , so $k=2$ .

Solved example: 3. Variance along a given direction

Question. $C=\begin{pmatrix}6&3\\3&6\end{pmatrix}$ . What is the variance of the data along $\mathbf u=(1,0)$ and along $\mathbf v=\frac1{\sqrt2}(1,-1)$ ?

Solution. Variance along a unit direction is $\mathbf u^TC\mathbf u$ . For $\mathbf u=(1,0)$ : $C_{11}=6$ . For $\mathbf v$ : $\frac12\,(6-3-3+6)=3$ (it is PC2, so its variance is the smaller eigenvalue, $\lambda_2=3$ ).

Idea 3: Practical notes and limits

Centre first. Without it the "first component" just points at the average and the covariance formula is wrong.
Scale matters. PCA chases variance, so a feature measured in thousands drowns out one measured in fractions. Standardise (divide each feature by its standard deviation) when units differ.
Components are uncorrelated. The new coordinates $z_1,z_2,\dots$ have zero covariance with each other, and $\operatorname{Var}(z_j)=\lambda_j$ .
At most $\min(d,n-1)$ useful components (centred data of $n$ points has rank at most $n-1$ ).
PCA is linear: it can only find straight directions. A curved structure (like two concentric rings) fools it. The fix is kernel PCA (next week).
It is unsupervised: it never looks at labels, so the directions it keeps need not help classification.
PCA is not regression. Regression minimises vertical errors to predict $y$ . PCA minimises perpendicular distances and treats every feature alike.

Link to SVD (MLF week 6). If $X=U\Sigma V^T$ is the SVD of the centred $d\times n$ matrix, the principal directions are the columns of $U$ and $\lambda_j=\sigma_j^2/n$ .

Your turn

Your turn: 1. PCA on four points

Points $(1,0),\,(-1,0),\,(0,2),\,(0,-2)$ are already centred. Find $C$ , the eigenvalues, PC1 and the variance explained by PC1.

Need a hint?

Sum $x^2$ , $xy$ , $y^2$ , divide by $n=4$ .

Show the full solution

$\sum x^2=2$ , $\sum xy=0$ , $\sum y^2=8$ . $C=\operatorname{diag}(0.5,\,2)$ . Eigenvalues $2$ and $0.5$ . PC1 is the $y$ -axis $(0,1)$ . Variance explained $=\frac2{2.5}=80\%$ .

Your turn: 2. Centre first

Raw data: $(2,4),\,(4,8),\,(6,12)$ . Find the mean, the centred data and the covariance matrix. How many non-zero eigenvalues will there be?

Need a hint?

All three points lie on one line.

Show the full solution

Mean $(4,8)$ . Centred: $(-2,-4),\,(0,0),\,(2,4)$ . $\sum x^2=8$ , $\sum xy=16$ , $\sum y^2=32$ . $C=\frac13\begin{pmatrix}8&16\\16&32\end{pmatrix}$ , trace $\frac{40}3$ , determinant $0$ . Eigenvalues $\frac{40}3$ and $0$ : one non-zero eigenvalue, because the data lies exactly on a line. PC1 $=\frac1{\sqrt5}(1,2)$ , explaining $100\%$ .

Your turn: 3. Reconstruction error

$C$ has eigenvalues $8,\,4,\,2,\,1$ . We keep 2 components. Give the variance explained and the average reconstruction error.

Need a hint?

Error = sum of the discarded eigenvalues.

Show the full solution

Total $=15$ . Explained $=\frac{12}{15}=80\%$ . Reconstruction error $=2+1=\mathbf3$ .

Your turn: 4. Coordinates and reconstruction

With $\mathbf w_1=\frac1{\sqrt2}(1,1)$ as PC1, find the PC1 coordinate and reconstruction of the centred point $(4,2)$ , and the squared error.

Need a hint?

Coordinate $=\mathbf w_1^T\mathbf x$ .

Show the full solution

$z=\frac{4+2}{\sqrt2}=3\sqrt2\approx4.24$ . Reconstruction $=z\,\mathbf w_1=(3,3)$ . Error vector $(1,-1)$ , squared length $2$ .

Your turn: 5. True or false

(a) PCA needs labels. (b) PC1 and PC2 are perpendicular. (c) PCA can be done without centring and still give the right answer. (d) Reconstruction error with $k$ components is the sum of the retained eigenvalues.

Need a hint?

Go back to the recipe.

Show the full solution

(a) False, it is unsupervised. (b) True, eigenvectors of a symmetric matrix. (c) False, you must centre. (d) False: it is the sum of the discarded eigenvalues.

Exam radar

In MLT Quiz 1, the concept summaries mention PCA in 25 of 60 papers, covariance matrix in 18, PCA variance in 11, principal components in 10, variance explained in 9, reconstruction error in 9. PCA also appears in 14 End Term papers (with kernel PCA).

Typical items: compute a $2\times2$ covariance from a few points and find its eigenvalues; variance explained by $k$ components; reconstruct a point from PC1; "which statements about PCA are true"; the data is not centred, what changes?

Watch out - real exam trap

Reconstruction error = discarded eigenvalues, not the kept ones.
Eigenvectors for PCA must be unit length before you project.
Forgetting to centre is the most common blunder.
"PCA minimises the sum of vertical distances" is false: it is perpendicular distances.
Check whether the paper's $C$ uses $\frac1n$ or $\frac1{n-1}$ ; the question will say.

Quick quiz

Principal components of a data set are the eigenvectors of...

the data matrix
the covariance matrix of the centred data
the identity matrix
the label vector

PCA diagonalises the covariance matrix.

Covariance eigenvalues are 6, 3, 1. Variance explained by the first component is...

30 percent
50 percent
60 percent
90 percent

6 / 10 = 60 percent.

Keeping 1 of 3 components with eigenvalues 6, 3, 1, the average reconstruction error is...

The sum of the discarded eigenvalues: 3 + 1 = 4.

Select all TRUE statements about PCA. (select all that apply)

It is an unsupervised method.
The principal components are mutually perpendicular.
Centring the data is optional.
It can only be used for classification.

Centring is essential, and PCA is used for compression, visualisation and denoising, not only classification.

Recap

Remember this

PCA finds the directions of maximum variance: the eigenvectors of $C=\frac1nXX^T$ (after centring), ordered by eigenvalue.
Coordinates $\mathbf z=W^T\mathbf x$ ; reconstruction $WW^T\mathbf x$ .
Variance explained $=\sum_{\le k}\lambda/\sum\lambda$ ; reconstruction error $=\sum_{>k}\lambda$ .
Max variance $\equiv$ min reconstruction error (Pythagoras). PCA is linear and unsupervised.

Formulas to keep

Centre: $\mathbf x_i\leftarrow\mathbf x_i-\bar{\mathbf x}$ ; $C=\frac1nXX^T$
Variance along unit $\mathbf w$ : $\mathbf w^TC\mathbf w$ ; best $\mathbf w$ : $C\mathbf w=\lambda\mathbf w$ , top $\lambda$
Coordinates $\mathbf z=W^T\mathbf x$ ; reconstruction $\hat{\mathbf x}=WW^T\mathbf x$
Variance explained $=\frac{\lambda_1+\dots+\lambda_k}{\lambda_1+\dots+\lambda_d}$ ; error $=\lambda_{k+1}+\dots+\lambda_d$
SVD link: $\lambda_j=\sigma_j^2/n$

Connected weeks (learn them together)

MLF week 1 - What is machine learning, and which maths do we need?: MLT starts by treating every data point as a vector. Vectors, lengths and dot products are MLF week 1.
MLF week 3 - Vectors, matrices and the best-fit line: PCA's 'reconstruction' is a projection - exactly the shadow idea from MLF week 3.
MLF week 4 - The special directions of a matrix: Principal components ARE eigenvectors of the covariance matrix.
MLF week 5 - Symmetric matrices: the well-behaved ones: Covariance matrices are symmetric, so the spectral theorem promises real eigenvalues and perpendicular principal components.
MLF week 6 - SVD and PCA: squeezing data: SVD is the machinery under PCA.
MLP week 12 - Unsupervised learning in sklearn: PCA in scikit-learn.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 32 real questions on this week All Quiz 1 papers