Home / MLT / Week 2

Week 2 · Kernel PCA: curved views of data

Official syllabus line: Unsupervised Learning - Representation learning - Kernel PCA

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

Before you start: MLT week 1 (PCA). MLF week 5 (positive semi-definite matrices).

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 a tiny dot drawn on paper, surrounded by a big ring. Can you draw a straight line to separate the dot from the ring? No matter where you draw, the line will always cut through the ring, right? That’s because simple lines can’t do curvy jobs.
Now, gently push the paper's middle down, forming a bowl shape. See? The ring goes high, and the dot settles at the bottom. A simple, flat cut at the right height can now easily separate them. We just added a new dimension, 'height', allowing a straight line to work. This is the main idea of kernel PCA!
Let's try this with numbers. Imagine points on a line: minus one, zero, one in the middle; and minus three, three on the outside. No single point can split them. But if we lift each point using its 'x squared' value, the middle points become low, and the outside points become high. A simple flat cut now separates them.
For your exam, remember to always 'centre the Gram matrix' before finding its components. Also, the number of components is at most the number of data points, no matter how many 'lifted' dimensions there are. So, kernel PCA helps straight lines do curvy jobs by secretly adding new dimensions.

The one-minute story

Think of it like this

Draw a small dot on a sheet of paper and a big ring around it. No straight line can separate "the dot" from "the ring": whichever way you cut, you slice the ring in two. PCA only knows straight lines, so it is stuck.

Now take the paper and push the middle down into a bowl. The ring is now high up, the dot is at the bottom, and one flat cut at the right height separates them perfectly. We did not change the data. We gave it a new dimension (height) where a straight line is enough.

That is kernel PCA. We secretly map each point into a bigger, richer space where PCA's straight lines can do curvy jobs. And here is the miracle, called the kernel trick: we never have to go to that bigger space. A simple formula, the kernel, tells us what the dot products would be there, and dot products are all PCA needs.

By the end of this week you can:

explain why linear PCA fails on curved data and how a feature map helps;
define a kernel and compute one from a feature map;
decide whether a function is a valid kernel (Mercer's condition and closure rules);
run kernel PCA on a small example, including centring the kernel matrix.

Words you need

Feature map $\phi$ - a rule that sends each point $\mathbf x$ to a longer list of numbers $\phi(\mathbf x)$ .
Kernel $k(\mathbf x,\mathbf y)=\phi(\mathbf x)^T\phi(\mathbf y)$ - the dot product of two points after mapping.
Gram (kernel) matrix $K$ - the table with $K_{ij}=k(\mathbf x_i,\mathbf x_j)$ .
Positive semi-definite (PSD) - symmetric with all eigenvalues $\ge0$ . Gram matrices must be PSD.
Kernel trick - using $k$ in place of $\phi(\mathbf x)^T\phi(\mathbf y)$ so we never compute $\phi$ .
RBF / Gaussian kernel - $k(\mathbf x,\mathbf y)=\exp\!\big(-\|\mathbf x-\mathbf y\|^2/2\sigma^2\big)$ , a similarity score that drops to 0 as points move apart.

Idea 1: Lifting data to where lines work

Adding the feature "distance from the centre squared" separates the ring from the middle.

A tiny 1-D version: the points $-3$ and $3$ (class A) and $-1,\,0,\,1$ (class B) sit on a line, and class B is sandwiched inside class A, so no single threshold separates them. Map $x\mapsto(x,\;x^2)$ . Now class B has heights $1,\,0,\,1$ and class A has height $9,\,9$ : a flat cut at height $5$ separates them.

The cost of lifting: the new space can have hundreds or even infinitely many coordinates. Computing $\phi(\mathbf x)$ directly would be slow or impossible. Enter the kernel.

Idea 2: Kernels

A kernel returns the dot product of the lifted points, computed from the original points only:

k(\mathbf x,\mathbf y)=\phi(\mathbf x)^T\phi(\mathbf y)

Solved example: 1. A kernel and the feature map it hides

Question. For $\mathbf x,\mathbf y\in\mathbb R^2$ take $k(\mathbf x,\mathbf y)=(\mathbf x^T\mathbf y)^2$ . Find a feature map $\phi$ , and check it on $\mathbf x=(1,2)$ , $\mathbf y=(3,1)$ .

Solution. Expand: $(x_1y_1+x_2y_2)^2=x_1^2y_1^2+2x_1x_2y_1y_2+x_2^2y_2^2$ . This is the dot product of

\phi(\mathbf x)=\big(x_1^2,\;\sqrt2\,x_1x_2,\;x_2^2\big)

with $\phi(\mathbf y)$ . Check: $\mathbf x^T\mathbf y=3+2=5$ , so $k=25$ . Via the map: $\phi(\mathbf x)=(1,\,2\sqrt2,\,4)$ and $\phi(\mathbf y)=(9,\,3\sqrt2,\,1)$ , dot product $9+2\sqrt2\cdot3\sqrt2+4=9+12+4=25$ . ✓

So computing the 2-number dot product and squaring gives the same answer as building two 3-number vectors, and for degree 5 in 100 dimensions the saving is astronomical.

Popular kernels

Kernel	Formula	Notes
Linear	$\mathbf x^T\mathbf y$	no lifting at all
Polynomial	$(\mathbf x^T\mathbf y+c)^d$ , $c\ge0$	features are all products up to degree $d$
Gaussian / RBF	$\exp(-\\|\mathbf x-\mathbf y\\|^2/2\sigma^2)$	infinitely many features; $k(\mathbf x,\mathbf x)=1$ ; small $\sigma$ means "only very close points are similar"
Laplacian	$\exp(-\\|\mathbf x-\mathbf y\\|/\sigma)$	valid; sharper peak than the Gaussian

Which functions are legal kernels? (Mercer's condition)

A function $k$ is a valid kernel exactly when, for every finite set of points, the Gram matrix $K$ is symmetric and positive semi-definite. That is equivalent to $k$ being a dot product in some feature space.

The idea

Closure rules. If $k_1,k_2$ are valid kernels, so are:

$c\,k_1$ for $c>0$
$k_1+k_2$
$k_1\cdot k_2$
$f(\mathbf x)\,k_1(\mathbf x,\mathbf y)\,f(\mathbf y)$ for any function $f$
$\exp(k_1)$ and any polynomial of $k_1$ with non-negative coefficients

Not valid in general: $k_1-k_2$ , and $c\,k_1$ with $c<0$ .

Quick disproof recipes: (i) $k$ not symmetric, like $k(x,y)=x-y$ ; (ii) a Gram matrix with a negative eigenvalue or negative determinant; (iii) a negative number on the diagonal ( $k(\mathbf x,\mathbf x)=\|\phi(\mathbf x)\|^2\ge0$ always).

Solved example: 2. Valid or invalid?

Question. Decide for 1-D points: (a) $k(x,y)=xy-1$ ; (b) $k(x,y)=(1+xy)^3$ ; (c) $k(x,y)=xy+e^{xy}$ .

Solution.

(a) For the points $0$ and $1$ : $K=\begin{pmatrix}k(0,0)&k(0,1)\\k(1,0)&k(1,1)\end{pmatrix}=\begin{pmatrix}-1&-1\\-1&0\end{pmatrix}$ . The diagonal entry $-1$ is negative (impossible for a dot product), and $\det=0-1=-1<0$ . Invalid.

(b) $xy$ is valid (linear), $1$ is valid (constant), their sum is valid, and a power is a product of valid kernels. Valid.

Idea 3: Kernel PCA

Ordinary PCA needs the eigenvectors of $C=\frac1n\sum\mathbf x_i\mathbf x_i^T$ . In the lifted space the same idea gives $C=\frac1n\sum\phi(\mathbf x_i)\phi(\mathbf x_i)^T$ , which may be gigantic or infinite. The trick:

Every eigenvector of $C$ with non-zero eigenvalue is a combination of the lifted data points: $\mathbf w=\sum_i\alpha_i\phi(\mathbf x_i)$ .
Substituting, the eigenproblem turns into one about the Gram matrix $K$ , which is only $n\times n$ :

K\boldsymbol\alpha=n\lambda\,\boldsymbol\alpha

Dot products $\phi(\mathbf x_i)^T\phi(\mathbf x_j)$ are exactly the kernel values. We never touch $\phi$ .

Important: centre in the lifted space too. PCA needs centred data, but we cannot subtract a mean we cannot compute. The fix is to centre the kernel matrix:

\tilde K=K-\mathbf 1_nK-K\mathbf 1_n+\mathbf 1_nK\mathbf 1_n,\qquad\mathbf 1_n=\tfrac1n\mathbf 1\mathbf 1^T

(Each entry becomes $K_{ij}$ minus its row mean, minus its column mean, plus the grand mean.)

The idea

Kernel PCA algorithm

Compute $K_{ij}=k(\mathbf x_i,\mathbf x_j)$ ( $n\times n$ ).
Centre it to get $\tilde K$ .
Find the eigenvalues $\mu_1\ge\mu_2\ge\dots$ and unit eigenvectors $\mathbf v_1,\mathbf v_2,\dots$ of $\tilde K$ .
The coordinate of training point $i$ on component $j$ is $\sqrt{\mu_j}\;v_{j,i}$ . (The variance of the data along component $j$ is $\mu_j/n$ .)

Facts: there are at most $n$ components (not $d$ or the huge feature dimension); with the linear kernel you get ordinary PCA back; and the eigenvalues of $\tilde K$ are $n$ times the eigenvalues of the lifted covariance.

Solved example: 3. Kernel PCA with a

2\times2

Gram matrix

Question. Two points have Gram matrix $K=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ . Centre it, find its eigenvalues, and give the coordinates of the two points on the first component.

Solution.

Row means: $1.5,\;1.5$ . Column means: $1.5,\;1.5$ . Grand mean: $1.5$ .
$\tilde K_{ij}=K_{ij}-1.5-1.5+1.5=K_{ij}-1.5$ , so $\tilde K=\begin{pmatrix}0.5&-0.5\\-0.5&0.5\end{pmatrix}$ .
Eigenvalues: trace $1$ , determinant $0$ : $\mu_1=1$ , $\mu_2=0$ . Eigenvector for $1$ : $\mathbf v_1=\frac1{\sqrt2}(1,-1)$ .
Coordinates: $\sqrt{\mu_1}\,\mathbf v_1=\big(0.707,\;-0.707\big)$ .

Only one non-zero component, as expected: two points have only one direction between them once centred. (And $\tilde K$ is PSD; the uncentred $K$ has eigenvalues $3$ and $1$ .)

Your turn

Your turn: 1. Feature map check

For $k(x,y)=(1+xy)^2$ on 1-D points, find $\phi$ and check with $x=2$ , $y=3$ .

Need a hint?

Expand $(1+xy)^2=1+2xy+x^2y^2$ .

Show the full solution

$\phi(x)=(1,\;\sqrt2\,x,\;x^2)$ . For $x=2$ : $(1,\,2\sqrt2,\,4)$ ; $y=3$ : $(1,\,3\sqrt2,\,9)$ . Dot: $1+12+36=49=(1+6)^2$ ✓.

Your turn: 2. Closure rules

$k_1$ and $k_2$ are valid. Which of these must be valid? (a) $3k_1+2k_2$ (b) $k_1-k_2$ (c) $k_1k_2$ (d) $e^{k_1}$ (e) $-k_1$ .

Need a hint?

Look at the list of rules.

Show the full solution

(a) valid, (b) not guaranteed (the difference may have a negative eigenvalue), (c) valid, (d) valid, (e) not valid (a negative multiple; its diagonal $-k_1(\mathbf x,\mathbf x)\le0$ ).

Your turn: 3. Centre a Gram matrix

$K=\begin{pmatrix}4&2\\2&4\end{pmatrix}$ . Compute $\tilde K$ .

Need a hint?

Row, column and grand means are all $3$ .

Show the full solution

$\tilde K_{ij}=K_{ij}-3-3+3=K_{ij}-3$ , so $\tilde K=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ (eigenvalues $2$ and $0$ ).

Your turn: 4. RBF facts

For the RBF kernel with $\sigma=1$ : (a) What is $k(\mathbf x,\mathbf x)$ ? (b) What happens to $k(\mathbf x,\mathbf y)$ as $\|\mathbf x-\mathbf y\|\to\infty$ ? (c) Compute $k$ for $\|\mathbf x-\mathbf y\|^2=2$ .

Need a hint?

$\exp(-d^2/2\sigma^2)$ .

Show the full solution

(a) $e^0=1$ . (b) it tends to $0$ . (c) $e^{-1}\approx0.368$ .

Your turn: 5. How many components?

You run kernel PCA on 50 data points with the RBF kernel (an infinite-dimensional feature space). At most how many components can have non-zero variance?

Need a hint?

The Gram matrix is $50\times50$ .

Show the full solution

At most $50$ (and, because of centring, in fact at most $49$ non-zero eigenvalues).

Exam radar

MLT Quiz 1 summaries mention kernels in 15 papers, Gaussian kernel in 15, polynomial kernel in 13, kernel functions in 12, Mercer's condition in 8, valid kernels in 8, invalid kernel in 7, kernel trick in 7, and the transformation mapping $\phi$ in 10. Kernel PCA appears in 14 End Term papers.

The most common MSQ is "which of the following are valid kernels?" built from the closure rules (sums and products valid, differences and negative multiples not). Next: "write the feature map for this kernel" and "centre this Gram matrix".

Watch out - real exam trap

$k_1-k_2$ is not a valid kernel in general.
Always centre $K$ before the eigen-analysis. Using the raw $K$ is a different (and wrong) problem.
The number of kernel PCA components is limited by $n$ , the number of points, not the feature dimension.
A kernel needs $k(\mathbf x,\mathbf x)\ge0$ and symmetry. A single violation rules it out.
Small $\sigma$ in an RBF kernel $\Rightarrow$ very local, can overfit; large $\sigma\Rightarrow$ nearly constant, can underfit.

Quick quiz

A valid kernel must produce a Gram matrix that is...

diagonal
symmetric and positive semi-definite
invertible
all positive entries

Mercer's condition: symmetric PSD for every finite set of points.

k1 and k2 are valid kernels. Which is NOT guaranteed to be valid?

k1 + k2
k1 times k2
k1 minus k2
5 times k1

A difference can have negative eigenvalues. Sums, products and positive multiples are safe.

The linear kernel in kernel PCA gives...

nothing
ordinary PCA
k-means
a random projection

With phi(x) = x the kernel is x dot y and kernel PCA reduces to ordinary PCA.

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

The kernel matrix must be centred.
The number of components is at most the number of data points.
It needs the feature map phi to be computed explicitly.
It is a supervised method.

The kernel trick avoids computing phi, and kernel PCA is unsupervised.

Recap

Remember this

Linear PCA fails on curved data. Lift points with $\phi$ , then run PCA there.
Kernel $k(\mathbf x,\mathbf y)=\phi(\mathbf x)^T\phi(\mathbf y)$ gives lifted dot products without computing $\phi$ .
Valid $\iff$ Gram matrix symmetric PSD. Closure: $+$ , $\times$ , positive multiples, $\exp$ OK; $-$ not.
Kernel PCA: build $K$ , centre to $\tilde K$ , eigen-analyse; coordinate $=\sqrt{\mu_j}\,v_{j,i}$ ; at most $n$ components.

Formulas to keep

$k(\mathbf x,\mathbf y)=\phi(\mathbf x)^T\phi(\mathbf y)$ ; $(\mathbf x^T\mathbf y)^2\leftrightarrow\phi=(x_1^2,\sqrt2x_1x_2,x_2^2)$
RBF: $\exp(-\|\mathbf x-\mathbf y\|^2/2\sigma^2)$ ; polynomial $(\mathbf x^T\mathbf y+c)^d$
Valid $\iff$ $K=K^T$ , $K\succeq0$
Centring: $\tilde K=K-\mathbf 1_nK-K\mathbf 1_n+\mathbf 1_nK\mathbf 1_n$
Coordinates on component $j$ : $\sqrt{\mu_j}\,v_{j,i}$ ; variance along it $\mu_j/n$

Connected weeks (learn them together)

MLF week 4 - The special directions of a matrix: Kernel PCA is eigen-analysis of a kernel matrix.
MLF week 5 - Symmetric matrices: the well-behaved ones: A function is a valid kernel exactly when its matrix is positive semi-definite.

Practise with real exam questions

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