The kernel trick — AI-ML notes

WHY do we need it?

WHAT is the problem? A linear SVM finds a separating hyperplane $\mathbf{w}^\top \mathbf{x} + b = 0$ . But data like concentric circles (inner class vs outer ring) has no straight line that separates them.

WHY does lifting help? If we add a feature like $x_1^2 + x_2^2$ (distance-squared from origin), the inner points get a small value and the outer ring a large value — now a flat threshold on that new axis separates them perfectly.

HOW without exploding cost? A degree- $d$ polynomial map on $n$ features has $O(n^d)$ new features. Computing them explicitly is expensive (or infinite-dimensional!). The kernel trick sidesteps this: the SVM's math only ever uses dot products $\langle \mathbf{x}_i, \mathbf{x}_j\rangle$ , so if we can compute $\langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j)\rangle$ cheaply via a shortcut function, we never form $\phi(\mathbf{x})$ at all.

The dual form: where dot products appear

Why this matters: the training data appears only as the inner product $\langle \mathbf{x}_i,\mathbf{x}_j\rangle$ . Prediction is also purely dot products: $f(\mathbf{x}) = \operatorname{sign}\Big(\sum_i \alpha_i y_i \langle \mathbf{x}_i,\mathbf{x}\rangle + b\Big).$

So replace every $\langle \mathbf{x}_i,\mathbf{x}_j\rangle$ with $K(\mathbf{x}_i,\mathbf{x}_j) = \langle \phi(\mathbf{x}_i),\phi(\mathbf{x}_j)\rangle$ and you get a nonlinear SVM for free.

Deriving a kernel FROM SCRATCH

Let's prove the polynomial kernel is a dot product in a bigger space. Take 2D inputs $\mathbf{x}=(x_1,x_2)$ , $\mathbf{z}=(z_1,z_2)$ and the function $K(\mathbf{x},\mathbf{z}) = (\mathbf{x}^\top\mathbf{z})^2.$

Step 1 — expand. Why? We want to see if it factors as $\phi(\mathbf{x})^\top\phi(\mathbf{z})$ . $(x_1z_1 + x_2z_2)^2 = x_1^2z_1^2 + 2x_1x_2z_1z_2 + x_2^2z_2^2.$

Step 2 — regroup as a dot product. Why? Group terms so each summand is (function of $\mathbf x$ ) $\times$ (same function of $\mathbf z$ ). $= (x_1^2)(z_1^2) + (\sqrt2 x_1x_2)(\sqrt2 z_1z_2) + (x_2^2)(z_2^2).$

Step 3 — read off $\phi$ . Why? It now literally is $\phi(\mathbf x)^\top\phi(\mathbf z)$ with $\phi(\mathbf{x}) = (x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2).$

When is a function $K$ a valid kernel? By Mercer's theorem: iff $K$ is symmetric and the Gram matrix $[K(\mathbf x_i,\mathbf x_j)]$ is positive semidefinite for every dataset. PSD guarantees some feature map $\phi$ exists.

Common kernels

Why is RBF infinite-dimensional? Expand $e^{2\gamma\mathbf{x}^\top\mathbf{z}}$ as a Taylor series $\sum_k \frac{(2\gamma\mathbf{x}^\top\mathbf{z})^k}{k!}$ : it contains polynomial terms of every degree. Each degree adds features, so $\phi$ has infinitely many — impossible to compute explicitly, trivial to evaluate as a kernel. This is why the kernel trick is essential, not just convenient.

Worked examples

Common mistakes (steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine trying to separate red marbles inside a circle from blue marbles outside, all lying flat on a table. No straight stick can split them. Now lift the middle of the table up like a hill — reds rise high, blues stay low. Now a flat card can slide between them! The kernel trick is a magic ruler that tells you how far apart marbles would be after lifting, without ever building the hill. You get the answer for free.

Recall

What is the kernel trick?

Computing

\langle\phi(\mathbf x),\phi(\mathbf z)\rangle

via a cheap function

K

without ever building the high-dimensional feature map

\phi

Why can kernels be plugged into the SVM at all?

The dual SVM and its prediction use training points ONLY through dot products

\langle\mathbf x_i,\mathbf x_j\rangle

, which we replace by

K

Give the feature map for

K=(\mathbf x^\top\mathbf z)^2

in 2D.

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

State Mercer's condition.

K

is a valid kernel iff it is symmetric and its Gram matrix is positive semidefinite for every dataset.

Write the RBF kernel.

K(\mathbf x,\mathbf z)=\exp(-\gamma\|\mathbf x-\mathbf z\|^2)

Why is the RBF feature space infinite-dimensional?

Its Taylor expansion contains polynomial terms of every degree, adding infinitely many features.

Effect of large

\gamma

in RBF?

Similarity decays fast with distance → each point isolated → overfitting / wiggly boundary.

Polynomial kernel formula and its feature-space size?

K=(\mathbf x^\top\mathbf z+c)^d

; finite feature space of size

O(n^d)

Connections

Support Vector Machines — the dual form that exposes dot products
Soft-margin SVM — where $C$ and $\alpha_i$ come from
Mercer's Theorem — validity condition for kernels
RBF Kernel — infinite-dimensional lift
Gaussian Naive Bayes — contrast: probabilistic vs margin-based
Overfitting and Regularization — tuning $\gamma$ , $C$

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, kabhi-kabhi data aisa hota hai ki koi bhi seedhi line usse alag nahi kar sakti — jaise ek chhota circle andar aur bada circle bahar. Aisi situation mein hum data ko ek higher-dimensional space mein "utha" lete hain, jahan wahi data ek flat plane se easily separate ho jaata hai. Yeh uthana kaam karta hai feature map $\phi$ se — jaise $x_1^2+x_2^2$ (origin se distance-squared) add kar diya.

Ab problem yeh hai ki agar features bahut zyada ho jaayein (polynomial degree $d$ pe $O(n^d)$ , ya RBF pe toh infinite!), toh unhe explicitly compute karna mushkil ya impossible hai. Yahan aata hai kernel trick ka jaadu: SVM ki dual form mein data sirf dot products ke roop mein aata hai. Toh hum $\phi$ banate hi nahi — bas ek function $K(\mathbf x,\mathbf z)=\langle\phi(\mathbf x),\phi(\mathbf z)\rangle$ use karte hain jo seedha original space mein sasta compute ho jaata hai.

Sabse common kernels: linear, polynomial $(\mathbf x^\top\mathbf z+c)^d$ , aur RBF $\exp(-\gamma\|\mathbf x-\mathbf z\|^2)$ . RBF ek "closeness" measure hai — paas ke points ka similarity 1 ke kareeb, door ke points ka 0 ke kareeb. Ek cheez yaad rakho: har similarity function kernel nahi hota — usse Mercer condition (symmetric + PSD Gram matrix) satisfy karna padta hai. Aur $\gamma$ bada rakhoge toh model overfit karega, isliye tuning zaroori hai. Bas itna samajh lo, toh non-linear SVM tumhare liye clear ho gaya.

Test yourself — SVM, Naive Bayes & Probabilistic Models

Connections