Part IX — Dimensionality Reduction

Chapter 30 · Kernel PCA

Part IX closes with the chapter PCA's linearity had coming. When data lives on a curve — two concentric rings of points, say — no straight axis can order it, and PCA's best projection entangles the rings into a coin flip. Kernel PCA rotates Chapter 14's kernel trick into dimensionality reduction: run PCA in a hidden high-dimensional feature space, paid for entirely in kernel values — the RBF kernel matrix is computed by hand here on three points, the polynomial kernel's secret 144-in-one-line identity is verified exactly, and the gamma dial is turned until the rings snap apart on a single axis. Then the real Wine pipeline, the kernel menu, and the honest bill: what nonlinearity costs.

📖 Chapter 30 of 33 ⏱ ~90 min read Mostly Core Stable Volatile 📝 Quiz · 30 MCQs

🎯 Learning Objectives

Show precisely where PCA fails: nonlinear structure, live on real concentric rings (0.510 vs 1.000 — real numbers)
Compute an RBF kernel matrix by hand on three points, and verify the polynomial kernel's (x·z + 1)² = φ(x)·φ(z) identity exactly
Explain Kernel PCA's trick: PCA in feature space, executed only through kernel values — no φ ever computed
Turn the gamma dial and read its three regimes: too flat (≈ PCA), the sweet spot, too sharp (memorisation)
Run the real Wine pipeline: kernel menu, gamma sweep, and how KPCA-2's perfect score sits beside PCA's and LDA's
State Kernel PCA's costs honestly: n² kernel matrix, no explained-variance percentages, no easy inverse, one more hyperparameter

1. The Wall PCA Cannot Climb

Chapter 28's parting confession was this: PCA finds straight axes. If the data lies on a curved manifold, the leading principal components cut across it. Time to watch that failure happen, then fix it.

The classic exhibit: two concentric rings — 300 points, an outer ring of radius 1, an inner ring of radius 0.3, a whisper of noise, two classes. Every line drawn through this data has the rings mirrored on both sides; no straight axis can score ring-membership. The real run (logistic regression in PCA's own 2-component space — which here is the raw plane, since two components reproduce it exactly):

PCA-space logistic accuracy = 0.510 — a coin flip. No line separates the rings.

This is not a tuning problem. The information (which ring a point belongs to) is the distance from the centre — a radius — and no linear combination of (x, y) can express a radius. PCA is structurally blind to it.

Figure 30.1 — The real rings (300 points). Every direction PCA could pick slices both rings in half: the class information is a radius, and radii are nonlinear.

The fix was already invented in Chapter 14, for exactly this shape of problem: the kernel trick. Lift the data into a high-dimensional feature space where a linear separator exists, and pay only in dot products — never compute the lift itself. Kernel SVM used the trick to bend a classifier's boundary. Kernel PCA uses the same trick to bend the axes of a projection. Same tool, new job.

2. The Kernel, by Hand

Chapter 14 introduced the kernel as a similarity function that secretly computes a dot product in a hidden feature space. Two hand examples make that concrete — every number exact and verified.

2.1 The RBF kernel matrix on three points

The Gaussian (RBF) kernel with γ = 1: K(x, x′) = exp(−γ‖x − x′‖²). Take three 1-D points {0, 1, 3}. First the squared distances, then exponentials of their negatives — each a hand lookup (e⁻¹ = 0.3679, e⁻² = 0.1353, e⁻³ = 0.0498, e⁻⁴ = 0.0183, e⁻⁹ ≈ 0.0001):

‖x − x′‖²	0	1	3
0	0 → 1.0000	1 → e⁻¹ = 0.3679	9 → e⁻⁹ = 0.0001
1	1 → 0.3679	0 → 1.0000	4 → e⁻⁴ = 0.0183
3	9 → 0.0001	4 → 0.0183	0 → 1.0000

Three properties to read off, because the whole method stands on them: the diagonal is 1 (every point is maximally similar to itself); the matrix is symmetric (similarity has no direction); and similarity decays with distance — 0 and 1 are acquaintances (0.368), 0 and 3 are strangers (0.0001). The RBF kernel is a neighbourhood function: near in input space means near in feature space.

2.2 The polynomial kernel's secret identity

Chapter 14 claimed the polynomial kernel (x·z + 1)² equals a dot product in a 6-dimensional feature space without ever building it. Verify, with x = (1, 2) and z = (3, 4). The kernel side is one line:

(x·z + 1)² = (1·3 + 2·4 + 1)² = (11 + 1)² = 144

The feature space it hides: φ(v) = (√2v₁, √2v₂, v₁², √2v₁v₂, v₂², 1) — all monomials up to degree 2. So φ(x) = (1.414, 2.828, 1, 2.828, 4, 1) and φ(z) = (4.243, 5.657, 9, 16.97, 16, 1). Their dot product: 6.0 + 16.0 + 9 + 48 + 64 + 1 = 144. One line of kernel arithmetic, thirty-six multiplications saved — the trick's entire economy. (Verified numerically: φ(x)·φ(z) = 144.0.)

And the RBF kernel? Its hidden feature space is infinite-dimensional (Chapter 14's cliff-hanger, now load-bearing): every distance gets its own coordinate, infinitely fine-grained similarity — which is why KPCA axes can bend as sharply as any data demands.

💡

Pro Tip: a valid kernel must be symmetric with a 1-diagonal after normalisation and correspond to some feature space's dot products (positive semi-definite). RBF, polynomial, sigmoid, cosine all qualify — which is exactly the menu KernelPCA(kernel=...) offers.

3. Kernel PCA: The Algorithm

Here is the beautiful part: Kernel PCA is ordinary PCA, executed in the feature space, with the kernel paying all the bills.

Imagine mapping every point xᵢ through φ into the feature space (for RBF: infinitely many coordinates — never written down).
Centre the φ-images — possible using only kernel values (subtract row/column means of K and add back the grand mean: the double-centring K̃ = K − 1ₙK − K1ₙ + 1ₙK1ₙ).
Eigendecompose the centred kernel matrix K̃ (n × n — one entry per pair of points, computed by the hand method of Section 2). Its eigenvalues rank directions of maximum variance in feature space; its eigenvectors encode the principal axes through the point-wise kernel.
Score each point: component k of point i is the i-th entry of the k-th eigenvector, scaled by its eigenvalue. The scores are the new coordinates — curves in input space, straight lines in feature space.
Project new points (the test set) by kernelising them against the training points — the Nyström approximation, one kernel evaluation per training point per component.

Notice what changed from Chapter 28: the matrix decomposed is n × n (142 × 142 for the Wine training set), not p × p (13 × 13). The geometry lives between points now, not between features — which is both the power (any number of feature dimensions, including infinite) and the bill (Section 8).

📝

Note — no percentages: the eigenvalues of K̃ are variances in the feature space, whose total scale has no interpretation in original units. KPCA has no "56.2% of variance" sentence to offer — component count must be chosen by downstream performance (Section 6), not by a scree threshold. A real trade-off for the loss of Chapter 28's tidy variance ledger.

4. The Gamma Dial

γ controls how fast similarity decays with distance — the single knob that decides what KPCA sees. Hold the hand matrix's entries in mind and turn the dial on a fixed distance-1 pair:

γ	K(distance 1)	K(distance 3)	Regime
0.01	0.990	0.914	Nearly flat — everything is similar to everything; the kernel matrix approaches all-ones, KPCA degenerates toward nothing-at-all (and RBF ≈ linear-ish behaviour)
0.5	0.607	0.011	Regional — neighbours similar, far points distinct; structure at medium scale
1	0.368	0.0001	Local — the hand matrix's regime
5	0.007	0.0000	Hyper-local — only near-twins relate; each point its own island
50	0.0000	0.0000	Identity matrix — every point only similar to itself; the "components" are re-labelled points, pure memorisation

It is Chapter 14's γ story again, now in projections: too small and the kernel cannot see curvature (behaves like linear PCA); too large and it sees only individuals (memorises, generalises nothing). The sweet spot relates γ to the data's own scale — and sklearn's default, γ = 1/n_features, is a reasonable anchor on standardised features, never a guarantee. Section 6 shows both failure modes on real data, with numbers.

⚠

Warning — γ interacts with scaling: distances depend on units, so the same γ means different neighbourhoods on raw and standardised data. Standardise first (the source does), then tune γ on that scale — mixing the two is a silent bug.

📋 Stable content — Reviewed: October 2026

5. Implementation in Python

import numpy as np
import pandas as pd

dataset = pd.read_csv('Wine.csv')
X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, -1].values

from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=0)

sc = StandardScaler()
X_train = sc.fit_transform(X_train)
X_test = sc.transform(X_test)

from sklearn.decomposition import KernelPCA
kpca = KernelPCA(n_components=2, kernel='rbf')   # gamma defaults to 1/n_features
X_train = kpca.fit_transform(X_train)            # unsupervised — no labels, like PCA
X_test = kpca.transform(X_test)

from sklearn.linear_model import LogisticRegression
classifier = LogisticRegression(random_state=0)
classifier.fit(X_train, y_train)

from sklearn.metrics import confusion_matrix, accuracy_score
y_pred = classifier.predict(X_test)
print(confusion_matrix(y_test, y_pred))          # [[14  0  0]
                                                 #  [ 0 16  0]
                                                 #  [ 0  0  6]]
print(accuracy_score(y_test, y_pred))            # 1.0

Listing 30.1 — The complete kernel pipeline (source: kernel_pca.py). One word differs from Chapter 28: KernelPCA(kernel='rbf').

# The circles rescue, reproducible
from sklearn.datasets import make_circles
Xc, yc = make_circles(n_samples=300, factor=0.3, noise=0.05,
                      random_state=0)

# raw plane (= PCA space for 2 features): no line separates the rings
LogisticRegression(random_state=0).fit(Xc, yc).score(Xc, yc)   # 0.510

T = KernelPCA(n_components=2, kernel='rbf', gamma=5).fit_transform(Xc)
LogisticRegression(random_state=0).fit(T, yc).score(T, yc)     # 1.000

# the idiom cupboard
KernelPCA(n_components=2, kernel='rbf', gamma=5)   # explicit gamma
KernelPCA(n_components=2, kernel='poly', degree=3) # Chapter 14's other trick
kpca.eigenvalues_                                  # kernel-matrix eigenvalues
                                                   # (feature-space scale — no %)

Listing 30.2 — The motivating demo and the API surface worth knowing.

💡

Pro Tip: like PCA (and unlike LDA), KernelPCA's fit sees no labels — the leakage rule is the same: fit on train, transform test. But the n² memory means you also cannot casually refit it per fold inside a grid search on large data; budget accordingly (Section 8).

6. The Real Run — Wine, Bent Axes

Back to the 178 wines (split 142/36, seed 0, standardised). The source's default configuration — RBF, γ = 1/13 ≈ 0.077, two components, then logistic regression:

Model (same split, same scaling)	Confusion matrix	Accuracy
KPCA-2 (RBF, γ=1/13) + logistic	[[14, 0, 0], [0, 16, 0], [0, 0, 6]]	1.000 — perfect
LDA-2 + logistic (Ch 29)	[[14, 0, 0], [0, 16, 0], [0, 0, 6]]	1.000
PCA-2 + logistic (Ch 28)	[[14, 0, 0], [1, 15, 0], [0, 0, 6]]	0.972
All 13 features + logistic	[[14, 0, 0], [0, 16, 0], [0, 0, 6]]	1.000

The kernel's two leading eigenvalues on this data: 19.13 and 12.62 (feature-space units — resist calling them percentages). The class means in KPCA coordinates — (−0.44, −0.19), (0.02, 0.32), (0.44, −0.22) — sit much closer together than LDA's (Chapter 29's were spread ±4), yet the logistic boundary still slices them perfectly: on this dataset the wine chemistry is nearly linear anyway, so KPCA's advantage is modest — it matches LDA's ceiling.

6.1 The kernel menu

Chapter 14 offered a kernel menu for SVM; the same menu, on the same idea, for projection (2 components each, real accuracies):

Kernel	Wine accuracy	Character
linear	0.972	≡ PCA — the sanity check that KernelPCA(linear) is Chapter 28
rbf	1.000	infinite-dimensional similarity; the default reach
poly	1.000	polynomial feature interactions
sigmoid	0.972	neural-tanh similarity; no gain here
cosine	1.000	angle-only similarity (magnitude-blind)

6.2 The gamma sweep — both failure modes, live

γ	0.001	0.01	0.077 (default)	0.5	2.0
Accuracy	0.944	0.972	1.000	0.833	0.444
Top eigenvalues	1.32, 0.70	10.36, 5.60	19.12, 12.61	2.87, 2.28	1.07, 1.06

Read the two ends. At γ = 0.001 the kernel is flat — every wine similar to every other — the eigenvalues collapse toward the near-linear regime and accuracy sinks to 0.944 (worse than plain PCA: a flat kernel distorts even the linear structure). At γ = 2.0 the kernel is so sharp that each wine relates only to itself; the eigenvalues shrink to ~1 (near-identity matrix), the components degenerate into re-labelled individual points, and the classifier collapses to majority guessing — 16/36 = 0.444, exactly the majority-class share of the test set. Section 4's dial, at both broken extremes, on real data.

6.3 And the rings? Snapped apart

The chapter's opening wound, healed with the same tool. KPCA (γ = 5 — found by sweep, Section 8's hands-on does it honestly) on the 300 rings, then the same logistic classifier that managed 0.510:

Figure 30.2 — The same 300 points after Kernel PCA (real coordinates). The rings, inseparable in any linear projection, land on opposite ends of the first kernel component: inner −0.39…−0.34, outer 0.17…0.54 — disjoint, with empty space between. Logistic accuracy: 0.510 → 1.000.

What did the first kernel component learn? Distance from the centre — the radius no linear axis could express. KPCA discovered the ring's defining nonlinearity from nothing but pairwise similarities. That is the entire promise of this chapter, delivered.

🌎

Real World: kernel-reduced coordinates feed exactly the pipelines Parts II–III built: denoise image or sensor data with KPCA, then regress or classify on the components. Where curved manifolds hide inside high dimensions — spectral data, motion captures, fraud patterns — the trick earns its keep; on gently linear business tables, plain PCA wins on cost.

7. The Part IX Family Table

Three chapters, three reducers, one dataset family. The complete ledger:

	PCA (Ch 28)	LDA (Ch 29)	Kernel PCA (Ch 30)
Uses labels?	no	yes	no
Axes	straight, variance-ranked	straight, separation-ranked	curved (linear in feature space)
Matrix decomposed	feature covariance (p × p)	SḦ⁻¹Sఖ (p × p)	centred kernel matrix (n × n)
Max components	min(n−1, p)	C − 1	n
Hyperparameters	k	k (≤ C−1), shrinkage	k + kernel + γ
Variance ledger	clean % of total	% of between-class	feature-space units, uninterpretable
Wine, 2 axes	0.972	1.000	1.000
Circles, 2 axes	0.510	0.510 (also linear!)	1.000
Inverse transform	exact	n/a	approximate only (pre-image problem)

Note the circles row: LDA fails too — its boundaries are as straight as PCA's axes. Only the kernel bends. And note the choice rule that falls out of the whole part: linear structure, no labels → PCA; labels, few classes, near-Gaussian → LDA; curved structure → Kernel PCA — with the cost column (next section) as the tiebreaker at scale.

Figure 30.3 — All 142 training wines at their real KPCA coordinates (γ = 1/13). Tighter, curlier clusters than Chapter 28's — the kernel compresses near-neighbourhoods — and a perfect 36/36 downstream.

⚠ Volatile content — Reviewed: October 2026 · Next review: January 2027

8. Costs & the Road Ahead

Nonlinearity is bought, not given. The honest bill — and where the research went (the volatile part):

Quadratic memory, cubic time: the kernel matrix is n × n and its eigendecomposition ~n³. At n = 142, trivial; at n = 100,000, 10¹&sup0; entries — a non-starter. Large-scale kernel methods (Nyström sampling, random kitchen-sink features) approximate the kernel with landmark points, trading exactness for feasibility.
One more hyperparameter: γ (and the kernel choice) must be tuned — Section 6's sweep showed accuracy swinging 1.000 → 0.444 on one dial. Chapter 31's grid search exists partly for exactly this.
No variance ledger, no easy inverse: component counts can't be justified by "% variance", and mapping scores back to input space (the pre-image problem) is only approximate and iterative — a real limitation for compression and denoising workflows PCA serves natively.
The deep alternative: autoencoders (Chapter 26's machinery, trained to reconstruct through a bottleneck) learn nonlinear reductions that scale to millions of examples and do reconstruct — at the cost of data hunger, tuning, and no convexity guarantee. Kernel methods and neural methods remain the two poles of nonlinear reduction; t-SNE/UMAP (Chapter 28's volatile section) rule visualisation but not downstream pipelines.

Part IX is complete: PCA for linear variance, LDA for label-aligned linear separation, Kernel PCA for the curved remainder. Part X turns from building models to choosing them honestly — k-fold cross-validation to measure what you actually have, grid search to tune what Chapter 14 and this chapter kept turning by hand, and XGBoost, the gradient-boosted trees that still dominate tabular machine learning. The course's final ascent begins.

🛠 Hands-On: Rescue the RingsIntermediate

You are handed the concentric-rings dataset and a reputation to defend: "your predecessor tried PCA and quit." Verify the hand arithmetic, reproduce the failure, then find the γ that rescues it — and prove you know why it works.

Steps

Hand-verify the 3×3 RBF kernel matrix of Section 2.1 (all nine entries, from e⁻ᵖ lookups) and the polynomial identity (x·z+1)² = 144 = φ(x)·φ(z).
Generate the rings (Listing 30.2); confirm the raw-plane logistic accuracy ≈ 0.510 and explain, in one sentence each, why PCA and LDA both fail here.
Run KPCA on the rings with γ ∈ {0.1, 0.5, 1, 2, 5, 10, 20}; for each, report the logistic accuracy and the PC1 ranges of both rings. Identify every regime from Section 4's dial.
Plot or tabulate your sweep and defend one operating γ — including what breaks on either side of it.
Run the Wine pipeline (Listing 30.1); verify the perfect confusion matrix, the kernel menu, and the gamma sweep's two failure modes (0.944 at γ=0.001, 0.444 at γ=2).
Bonus: fit PCA and KPCA(linear) on the same scaled Wine training data and confirm their projections are proportional — the sanity check of Section 6.1's "linear ≡ PCA" claim.

View Solution / Walkthrough

import numpy as np
from sklearn.datasets import make_circles
from sklearn.decomposition import KernelPCA
from sklearn.linear_model import LogisticRegression

# ---- step 1: hand checks
pts = np.array([[0.],[1.],[3.]])
K = np.exp(-((pts - pts.T)**2))
print(K.round(4))          # [[1, .3679, .0001], [.3679, 1, .0183], [.0001, .0183, 1]]
x, z = np.array([1.,2.]), np.array([3.,4.])
phi = lambda v: np.array([np.sqrt(2)*v[0], np.sqrt(2)*v[1],
                          v[0]**2, np.sqrt(2)*v[0]*v[1], v[1]**2, 1.])
print((x@z+1)**2, phi(x)@phi(z))    # 144.0 144.0

# ---- steps 2-4: the rings and the dial
Xc, yc = make_circles(n_samples=300, factor=0.3, noise=0.05,
                      random_state=0)
print('raw acc %.3f' % LogisticRegression(random_state=0)
      .fit(Xc, yc).score(Xc, yc))               # 0.510
for g in [0.1, 0.5, 1, 2, 5, 10, 20]:
    T = KernelPCA(n_components=2, kernel='rbf', gamma=g).fit_transform(Xc)
    acc = LogisticRegression(random_state=0).fit(T, yc).score(T, yc)
    inn = T[yc==0][:,0]; out = T[yc==1][:,0]
    print('g=%5.1f acc %.3f | PC1 inner %.2f..%.2f outer %.2f..%.2f'
          % (g, acc, inn.min(), inn.max(), out.min(), out.max()))

# ---- step 5: Wine
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import confusion_matrix, accuracy_score
ds = pd.read_csv('Wine.csv')
X, y = ds.iloc[:, :-1].values, ds.iloc[:, -1].values
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=.2, random_state=0)
sc = StandardScaler(); Xs = sc.fit_transform(Xtr); Xt = sc.transform(Xte)
kp = KernelPCA(n_components=2, kernel='rbf').fit(Xs)
yp = LogisticRegression(random_state=0).fit(kp.transform(Xs), ytr) \
        .predict(kp.transform(Xt))
print(confusion_matrix(yte, yp), accuracy_score(yte, yp))

# ---- step 6: linear == PCA
from sklearn.decomposition import PCA
A = PCA(2).fit_transform(Xs); B = KernelPCA(2, kernel='linear').fit_transform(Xs)
c = np.corrcoef(A[:,0], B[:,0])[0,1]
print('PC1 correlation PCA vs KPCA-linear: %.4f' % c)   # ±1

Expected results (real): kernel matrix and 144-identity exact. Rings: raw 0.510; γ=0.1 flat (acc ~0.5, ranges entangled); γ=1 already 1.000 with overlapping-ish but sufficient ranges; γ=2–5 clean disjoint bands (γ=5: inner −0.39…−0.34 vs outer 0.17…0.54, empty gap between); γ=20 degrades (0.740) — the memorisation regime. Wine: perfect cm [[14,0,0],[0,16,0],[0,0,6]], menu linear/sigmoid 0.972 vs rbf/poly/cosine 1.000; sweep 0.944 / 0.972 / 1.000 / 0.833 / 0.444. PCA's PC1 and KPCA(linear)'s first component correlate at |r| = 1 (sign may flip) — same axis, two spellings.

🎯 Key Takeaways

PCA's axes are straight; curved structure — rings, moons, manifolds — is invisible to them. Real rings: 0.510 in PCA space, a coin flip.

The kernel trick, hand-verified: RBF on {0,1,3} gives the exact matrix with 1-diagonal, symmetry, decaying similarity; (x·z+1)² = 144 = φ(x)·φ(z) in one line.

Kernel PCA is PCA in feature space, paid in kernel values: centre K, eigendecompose the n × n matrix, score from eigenvectors. No φ ever computed.

γ is the whole game: flat (γ→0) collapses to near-linear; sharp (γ→∞) becomes identity-matrix memorisation. Wine swung 1.000 → 0.444 on one dial.

The rings snapped apart: KPCA's first component learned the radius no line could express — inner −0.39…−0.34 vs outer 0.17…0.54, accuracy 0.510 → 1.000.

Part IX's rule: no labels + linear → PCA; labels + near-Gaussian → LDA; curved → Kernel PCA — at n² memory and n³ time, with no variance ledger and no exact inverse.