The Kernel Trick

The kernel trick lets you train an SVM in a space with millions — or infinitely many — dimensions without ever computing a single coordinate in that space. The mechanism is a one-line substitution in the dual objective. Every formula in the dual where $x_i\cdot x_j$ appears gets replaced by $K(x_i,x_j)$. The reason this works at all is that the dual depends on dot products between samples, never on the weight vector $\mathbf{w}$ directly.

Anchor dataset: XOR classification — four points, no linear boundary possible.

import numpy as np
from sklearn.svm import SVC

X = np.array([[1, 1], [-1, -1], [1, -1], [-1, 1]])
y = np.array([1, 1, -1, -1])
# Positive class (y=+1): same-sign quadrants (Q1, Q3)
# Negative class (y=-1): opposite-sign quadrants (Q2, Q4)

Phase 1 — Why the Dual Is the Gateway

The primal SVM solves:

${\min }_{\mathbf{w},b}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\text{subject to }{y}_i(\mathbf{w}\cdot x_i+b)\ge 1$

The weight vector $\mathbf{w}$ lives in the same space as the input features. To use a nonlinear feature map $\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^D$, you would need to store and optimize a $D$-dimensional $\mathbf{w}$ — impossible when $D=\infty$ (as with the RBF kernel).

The dual objective is:

${\max }_{\mathbf{\alpha }}{\sum }_i{\alpha }_i-\frac{1}{2}{\sum }_i{\sum }_j{\alpha }_i{\alpha }_j{y}_i{y}_j\underset{\text{only dot products}}{\underbrace{x_i\cdot x_j}}$

subject to ${\sum }_i{\alpha }_i{y}_i=0$, ${\alpha }_i\ge 0$.

The weight vector drops out entirely. The dual depends only on pairwise inner products between training points. Substitute the feature map $\varphi$:

${\max }_{\mathbf{\alpha }}{\sum }_i{\alpha }_i-\frac{1}{2}{\sum }_i{\sum }_j{\alpha }_i{\alpha }_j{y}_i{y}_j\underset{=K(x_i,x_j)}{\underbrace{\varphi (x_i)\cdot \varphi (x_j)}}$

A kernel function $K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$ computes this inner product in the lifted space directly from the original inputs — no explicit $\varphi$ computation needed. The prediction for a new point also collapses to kernel evaluations:

$f(x)={\mathbf{w}}^{\ast }\cdot \varphi (x)+b={\sum }_{i\in \text{SV}}{\alpha }_i^{\ast }{y}_i\underset{K(x_i,x)}{\underbrace{\varphi (x_i)\cdot \varphi (x)}}+b$

The primal needs $\mathbf{w}\in {\mathbb{R}}^D$. The dual needs only the $n\times n$ kernel matrix. When $D\gg n$ — or when $D=\infty$ — the dual is the only tractable option.

Phase 2 — The Gram Matrix

The full set of pairwise kernel values between all training points is the Gram matrix $K\in {\mathbb{R}}^{n\times n}$, where $K_{ij}=K(x_i,x_j)$. This is the only structure the SVM optimizer ever sees — not the raw features, not $\varphi$.

The degree-2 homogeneous polynomial kernel $K(x_i,x_j)=(x_i\cdot x_j{)}^2$ corresponds to the feature map $\varphi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$. The $\sqrt{2}{x}_1{x}_2$ component captures the sign interaction that separates XOR.

Verifying the feature map works: for $x=(1,1)$ and $x^{\prime }=(-1,-1)$ (both positive class):

$\varphi (1,1)=(1,\sqrt{2},1),\varphi (-1,-1)=(1,\sqrt{2},1)$

They map to the same point. For $x^{\prime \prime }=(1,-1)$ (negative class): $\varphi (1,-1)=(1,-\sqrt{2},1)$. The $\sqrt{2}{x}_1{x}_2$ component flips sign — exactly what separates the classes.

Now computing the full 4×4 Gram matrix. Every entry $K_{ij}=(x_i\cdot x_j{)}^2$:

The full matrix (using $x_1=(1,1),x_2=(-1,-1),x_3=(1,-1),x_4=(-1,1)$):

$K=\left(\begin{array}{cccc}4& 4& 0& 0\\ 4& 4& 0& 0\\ 0& 0& 4& 4\\ 0& 0& 4& 4\end{array}\right)$

Same-class pairs (rows 1–2 and rows 3–4) have $K_{ij}=4$. Cross-class pairs have $K_{ij}=0$. The block structure in the kernel matrix is exactly the class structure.

The SVM optimizer solves the dual using only this matrix. The 3D feature space $(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$ is never instantiated.

Phase 3 — Prediction via Kernel Evaluations

The dual solution for this symmetric XOR problem: by symmetry all four ${\alpha }_i$ are equal. Setting ${\alpha }_i=\alpha$ and the constraint ${\sum }_i{\alpha }_i{y}_i=0$: $\alpha +\alpha -\alpha -\alpha =0$ ✓.

The dual objective becomes:

$4\alpha -\frac{1}{2}\cdot 32{\alpha }^2=4\alpha -16{\alpha }^2$

Setting the derivative to zero: $4-32\alpha =0\Rightarrow {\alpha }^{\ast }=\frac{1}{8}$ for all four points.

The bias $b$: substituting $x_1$ (a support vector) into $y_{1}f(x_1)=1$:

$f(x_1)=\frac{1}{8}(1)(4)+\frac{1}{8}(1)(4)+\frac{1}{8}(-1)(0)+\frac{1}{8}(-1)(0)+b=1+b$

Since $y_{1}f(x_1)=1$: $b=0$.

Now predict $x_{\text{test}}=(0.5,0.5)$ (falls in Q1, should be class +1). Compute $K(x_i,x_{\text{test}})=(x_i\cdot x_{\text{test}}{)}^2$ for each support vector:

$f(x_{\text{test}})=0.125+0.125+0+0+0=+0.25$

Positive — correctly classified as +1. The votes from $x_3$ and $x_4$ are exactly zero because their sign interaction ($x_1{x}_2<0$) is orthogonal to $x_{\text{test}}$'s orientation.

Phase 4 — Why RBF Is Infinite-Dimensional

For the polynomial kernel, the lifted space is finite: degree-2 maps ${\mathbb{R}}^2\to {\mathbb{R}}^3$. The RBF kernel $K(x,z)=\exp (-\gamma \Vert x-z{\Vert }^2)$ corresponds to an infinite-dimensional space.

For scalar inputs, expand via $e^{ab}={\sum }_{n=0}^{\infty }\frac{(ab{)}^n}{n!}$:

$K(x,z)=e^{-\gamma (x-z{)}^2}=e^{-\gamma x^2}\cdot e^{-\gamma z^2}\cdot \underset{\sum _{n=0}^{\infty }\frac{(2\gamma {)}^n}{n!}{x}^n{z}^n}{\underbrace{e^{2\gamma xz}}}$

$={\sum }_{n=0}^{\infty }\frac{(2\gamma {)}^n}{n!}\left(e^{-\gamma x^2}{x}^n\right)\left(e^{-\gamma z^2}{z}^n\right)$

This is a dot product $\varphi (x)\cdot \varphi (z)$ where:

$\varphi (x)=e^{-\gamma x^2}\left(1,\sqrt{\frac{2\gamma }{1!}}x,\sqrt{\frac{(2\gamma {)}^2}{2!}}{x}^2,\sqrt{\frac{(2\gamma {)}^3}{3!}}{x}^3,\dots \right)$

One component for every polynomial degree from 0 to $\infty$. The feature map is infinite-dimensional. Yet computing $K(x,z)=\exp (-\gamma \Vert x-z{\Vert }^2)$ costs $O(d)$ — the same as an ordinary dot product.

RBF kernel values ($\gamma =0.5$) on representative anchor pairs:

The same-class pair $(x_1,x_2)$ is further apart than the cross-class pairs $(x_1,x_3)$. XOR puts same-class points in opposite quadrants. RBF solves it not by finding same-class proximity but by fitting a complex boundary around the Q1/Q3 region.

γ Sensitivity

γ controls how quickly the RBF kernel decays with distance. Small γ: smooth kernel — each point's influence extends far. Large γ: sharp kernel — each point only sees itself.

from sklearn.svm import SVC
import numpy as np

X = np.array([[1, 1], [-1, -1], [1, -1], [-1, 1]])
y = np.array([1, 1, -1, -1])

for gamma in [0.05, 0.5, 2, 20]:
    svm = SVC(kernel='rbf', C=10, gamma=gamma)
    svm.fit(X, y)
    print(f"gamma={gamma:>5}: acc={svm.score(X,y):.2f}, n_SV={len(svm.support_vectors_)}")

gamma= 0.05: acc=0.50, n_SV=4
gamma=  0.5: acc=1.00, n_SV=4
gamma=    2: acc=1.00, n_SV=4
gamma=   20: acc=1.00, n_SV=4

At $\gamma =0.05$: the kernel is so smooth that $K(x_i,x_j)\approx 1$ for all pairs — the optimizer sees every point as equally similar to every other point and cannot find a separating boundary. At $\gamma =0.5$: the decay is fast enough to distinguish the XOR structure. At $\gamma =20$: each point's kernel value drops to near zero within a tiny radius — the SVM draws tight circles around each training point (all 4 become support vectors) and will fail on any test point not close to a training point.

Computational Cost

The kernel wins when $D\gg d$. The trap: kernel SVMs compute the full $n\times n$ Gram matrix during training. At $n=100,000$, that is $10^{10}$ float64 values — roughly 80 GB. This is why kernel SVMs are replaced by approximations at scale (Nyström method, random Fourier features) once $n$ exceeds roughly 50,000.

from sklearn.svm import SVC
from sklearn.kernel_approximation import RBFSampler
from sklearn.linear_model import SGDClassifier
from sklearn.pipeline import make_pipeline
import numpy as np

X = np.array([[1, 1], [-1, -1], [1, -1], [-1, 1]])
y = np.array([1, 1, -1, -1])

exact = SVC(kernel='rbf', C=10, gamma=0.5)
approx = make_pipeline(
    RBFSampler(gamma=0.5, n_components=100, random_state=42),
    SGDClassifier(max_iter=1000, random_state=42)
)
exact.fit(X, y)
approx.fit(X, y)
print(f"Exact kernel SVM:   {exact.score(X, y):.2f}")
print(f"Approx (RFF, n=100): {approx.score(X, y):.2f}")

Exact kernel SVM:    1.00
Approx (RFF, n=100): 1.00

RBFSampler approximates the RBF kernel via random Fourier features — maps inputs to a fixed $D$-dimensional space (here $D=100$) and then trains a linear model. Same accuracy on this tiny dataset, but the approach scales to millions of samples.

Related Concepts and Honest Limitations

This post depends entirely on the dual SVM formulation from post 02 — specifically that the dual objective collapses $\mathbf{w}$ out and retains only pairwise inner products $x_i\cdot x_j$. Without the dual, there is no substitution point. From here, the Gram matrix structure generalizes directly: kernel PCA replaces the covariance matrix with $K$, kernel ridge regression solves $(K+\lambda I{)}^{-1}y$ instead of $(X^{\top }X+\lambda I{)}^{-1}{X}^{\top }y$, and Gaussian processes use $K$ as the prior covariance. Mercer's condition (positive semi-definiteness of $K$) — covered in post 03 — is the formal requirement that makes the substitution valid.

The kernel trick is structurally tied to models whose training objective collapses to dot products — SVMs, kernel ridge regression, kernel PCA. Decision trees, random forests, and gradient boosting have no dual formulation of this form and cannot be kernelized. Logistic regression can be kernelized (via the dual of the regularized problem) but rarely is in practice. At $n>50,000$ the $O(n^2)$ Gram matrix becomes the bottleneck: 80 GB at $n=100,000$ in float64, before even running an optimizer. The correct response is the Nyström approximation (subsample $m\ll n$ points, approximate $K\approx K_{nm}{K}_{mm}^{-1}{K}_{mn}$) or random Fourier features, both of which trade approximation error for tractable memory. Finally, choosing the wrong kernel is equivalent to choosing the wrong model family: a polynomial kernel of degree 3 on data with a degree-2 structure will overfit; a linear kernel on XOR will fail entirely. Kernel selection is a hyperparameter search problem, not a free choice.

Test Your Understanding

1. The dual objective contains ${\sum }_i{\sum }_j{\alpha }_i{\alpha }_j{y}_i{y}_j{K}_{ij}$. In the primal, the analogous term is $\Vert \mathbf{w}{\Vert }^2$. Show algebraically that these are equal when ${\mathbf{w}}^{\ast }={\sum }_i{\alpha }_i^{\ast }{y}_i\varphi (x_i)$ — this is why the dual value equals the primal value at optimum.

2. The Gram matrix for the XOR anchor with kernel $K(x,z)=(x\cdot z{)}^2$ has a perfect $2\times 2$ block structure. If you added a fifth point $x_5=(0.1,0.1)$ (positive class), compute its row in the Gram matrix. Does the block structure hold?

3. At $\gamma =0.05$ the RBF kernel fails on XOR (50% accuracy). Using the Taylor expansion, explain why small $\gamma$ causes the kernel to assign nearly equal similarity to all pairs — what does this do to the Gram matrix?

4. The Nyström approximation builds a rank-$m$ approximation of the $n\times n$ Gram matrix by selecting $m$ "landmark" points. If $m=10$ and $n=100,000$, what are the storage requirements for the Nyström approximation vs the full Gram matrix?

5. The polynomial kernel $(x\cdot z{)}^2$ separates XOR perfectly, but the kernel $(x\cdot z+1{)}^2$ does not (all off-diagonal entries equal 1, giving no class separation). Expand $(x\cdot z+1{)}^2$ and identify which terms in the feature map are the same for all XOR points — this reveals why the intercept destroys the structure.