SVM Kernels

Imagine you're classifying images of handwritten digits. Some digits — like 0 and 8 — have shapes that aren't separable by any straight line in pixel space. Or consider a fraud detection system where transactions are flagged as suspicious when a specific combination of features is present (high amount AND unusual location), but neither feature alone is decisive. Patterns like these wrap around the feature space in ways no linear boundary can capture.

Linear SVMs fail here. No matter how wide you set the margin, a straight line through the original features cannot separate these classes. The solution is to project the data into a higher-dimensional space where a linear separator exists — without ever computing that projection explicitly. That's the kernel trick.

Let's see this failure in action on the simplest nonlinear pattern: XOR.

import numpy as np
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler

X = np.array([
    [ 1,  1], [ 2,  2], [-1, -1], [-2, -2],   # positive class: same sign
    [ 1, -1], [ 2, -2], [-1,  1], [-2,  2],   # negative class: opposite sign
])
y = np.array([1, 1, 1, 1, -1, -1, -1, -1])

svm_linear = SVC(kernel='linear', C=1.0)
svm_linear.fit(X, y)
train_acc = svm_linear.score(X, y)
print(f"Linear SVM train accuracy on XOR: {train_acc:.2f}")

Linear SVM train accuracy on XOR: 0.50

Random guessing. The XOR pattern requires a nonlinear boundary.

What It Is

A kernel is a function $K(x_i,x_j)$ that computes the dot product between two points in a transformed feature space — without ever constructing that space. The kernel trick replaces every $x_i\cdot x_j$ in the dual SVM objective with $K(x_i,x_j)$, letting you train SVMs in spaces with millions or infinitely many dimensions at the cost of an $O(d)$ computation in the original space.

Why Linear Fails on XOR

Positive class sits in Q1 and Q3 (same-sign quadrants); negative class in Q2 and Q4. Any line that separates Q1 from Q4 fails to separate Q3 from Q2 — the pattern wraps around.

The Plan — Four Steps to Kernel SVM

We'll walk through kernels in four steps: first see why linear SVM fails and how explicit feature maps solve it, then learn the kernel trick that avoids computing the map, explore the two most important kernels (polynomial and RBF), and finally understand how to choose among them.

Step 1 — The Feature Map Solution

Instead of drawing a line in 2D, let's map to a 3D space where the classes become linearly separable. The feature map $\varphi :{\mathbb{R}}^2\to {\mathbb{R}}^3$:

$\varphi (x_1,x_2)=(x_1^2,x_2^2,x_1{x}_2)$

The third component $z_3=x_1{x}_2$ captures the sign interaction — positive when $x_1,x_2$ have the same sign, negative otherwise.

In the lifted space, all positive class points have $z_3>0$ and all negative class points have $z_3<0$. The hyperplane $z_3=0$ (i.e., $x_1{x}_2=0$) separates them perfectly.

✓ Step 1 complete. By mapping XOR data to 3D with $\varphi (x_1,x_2)=(x_1^2,x_2^2,x_1{x}_2)$, the classes become linearly separable.

Step 2 — The Kernel Trick

Computing $\varphi (x_i)$ explicitly then taking dot products is expensive — the mapped space can be millions of dimensions. The kernel trick shows that what appears in the dual objective is only the dot product $\varphi (x_i)\cdot \varphi (x_j)$, and this inner product can often be computed without ever computing $\varphi (x_i)$ explicitly.

A kernel function is:

$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$

computed directly in the original space. For the polynomial kernel of degree 2:

$K(x_i,x_j)=(x_i\cdot x_j+1{)}^2$

Expanding: $(x_i\cdot x_j+1{)}^2=(x_{i1}{x}_{j1}+x_{i2}{x}_{j2}{)}^2+2(x_{i1}{x}_{j1}+x_{i2}{x}_{j2})+1$

This equals ${\varphi }^{\prime }(x_i)\cdot {\varphi }^{\prime }(x_j)$ for the feature map ${\varphi }^{\prime }(x)=(x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2,\sqrt{2}{x}_1,\sqrt{2}{x}_2,1)$ — without ever computing the 6-dimensional vector.

✓ Step 2 complete. The kernel $K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$ computes dot products in the lifted space using only the original coordinates.

Step 3 — Polynomial Kernel Values on the Anchor

$K(x_i,x_j)=(x_i\cdot x_j+1{)}^2$

Computing for representative pairs:

Same-class pairs share high kernel values (25) when features have the same magnitude. Cross-class pairs get $K=1$ — the offset from the constant term only, no sign interaction.

✓ Step 3 complete. The polynomial kernel $(x_i\cdot x_j+1{)}^2$ implicitly computes a 6-dimensional feature map.

Step 4 — The RBF Kernel

The Radial Basis Function (Gaussian) kernel is the most commonly used:

$K(x_i,x_j)=\exp \left(-\gamma \Vert x_i-x_j{\Vert }^2\right)$

• $\gamma$ controls how quickly similarity decays with distance
• As $\gamma \to 0$: all points are equally similar (underfitting)
• As $\gamma \to \infty$: only identical points are similar (overfitting)
• RBF corresponds to an infinite-dimensional feature map — it can represent any smooth decision boundary

RBF kernel values for $\gamma =0.5$ on the anchor:

The (1,1) vs (−1,−1) pair gets $K=0.018$ — even though they're in the same class, they're far apart in distance. The kernel doesn't know class labels; it only measures similarity by proximity.

✓ Step 4 complete. The RBF kernel corresponds to an infinite-dimensional feature map, yet costs only $O(d)$ to compute.

Hyperparameter Sensitivity — $\gamma$ Effect on the Decision Boundary

Let's see what happens as we vary $\gamma$. We'll use C=1.0 and try values from 0.1 to 100. Notice we don't need StandardScaler here — XOR data is already centered and on the same scale.

import matplotlib
matplotlib.use('Agg')
import numpy as np
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler

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

gammas = [0.1, 1, 10, 100]
for gamma in gammas:
    svm = SVC(kernel='rbf', C=1.0, gamma=gamma)
    svm.fit(X, y)
    train_acc = svm.score(X, y)
    print(f"gamma={gamma:>5}: train_acc={train_acc:.2f}, n_SV={svm.support_vectors_.shape[0]}")

gamma=  0.1: train_acc=0.50, n_SV=8
gamma=    1: train_acc=1.00, n_SV=4
gamma=   10: train_acc=1.00, n_SV=8
gamma=  100: train_acc=1.00, n_SV=8

At $\gamma =0.1$: still fails — the RBF kernel is too smooth, each point's influence extends so far that the XOR structure averages out. At $\gamma =1$: optimal — four support vectors, a clean X-shaped boundary. At $\gamma =10,100$: still 100% train accuracy, but all 8 points become support vectors — the kernel is so local that each point only sees itself.

✓ Hyperparameter sensitivity complete. $\gamma$ controls the RBF kernel's locality: too small underfits (all points look equally similar), too large overfits (each point only sees itself).

Choosing a Kernel

RBF is the default for unknown structure. Linear wins when the data is already high-dimensional (text BOW, embeddings) because: (a) it's often linearly separable in high dimensions already, (b) the dual has $n$ variables but the primal has $d$ — using the primal (with LinearSVC) is faster.

Mercer's Theorem

A function $K(x,z)$ is a valid kernel (corresponds to some feature map $\varphi$) if and only if the kernel matrix $K_{ij}=K(x_i,x_j)$ is positive semi-definite for any set of points. This is Mercer's condition. The sigmoid kernel violates this for some parameter choices — SVM convergence is not guaranteed when using non-PSD kernels.

Related Concepts

Backward: The kernel trick builds entirely on the dual formulation from post 02. The dual SVM objective contains $x_i\cdot x_j$ everywhere — not $x_i$ individually. This is what makes it possible to substitute $K(x_i,x_j)$ for $\varphi (x_i)\cdot \varphi (x_j)$ without changing the optimization. If the dual weren't available, kernels would require explicitly mapping to the lifted space (which could be infinite-dimensional).

Forward: Kernel SVM opens the door to spectral methods and graph-based learning. The kernel matrix $K_{ij}=K(x_i,x_j)$ is the core of kernel PCA, kernel ridge regression, and Gaussian processes. Understanding why $K$ must be positive semi-definite (Mercer's theorem) carries over directly to these methods.

Honest Limitations

1. $\gamma$ and $C$ interact in ways you won't expect until you grid-search them together. I've spent hours tuning $C$ alone, only to find that changing $\gamma$ by an order of magnitude made the $C$ search irrelevant. These two hyperparameters form a coupled system — $\gamma$ controls the shape of the boundary and $C$ controls how tightly it fits the data. Always tune them jointly with GridSearchCV over a logarithmic grid like {'C': [0.1, 1, 10], 'gamma': [0.1, 1, 10]}.

2. Kernel SVM trades interpretability for flexibility — and you will feel this loss. With a linear kernel, I can inspect the weight vector and say "credit score contributes positively to predicting no default." With RBF, the decision function is a sum over support vectors weighted by their distance to the new point. You can't extract feature importance, you can't explain individual predictions by feature contributions, and you can't easily debug why a specific point was misclassified. If interpretability matters for your stakeholders, consider linear models or tree-based methods before reaching for RBF.

3. No single kernel works for all data. RBF assumes the decision boundary has the same complexity everywhere in the feature space. I've seen this fail on text data where word importance varies by topic — one global kernel can't capture topic-specific interactions. Polynomial kernels of degree 2 or 3 handle different interaction patterns but require understanding whether your problem has polynomial structure. Kernel selection is model selection; treat it as a hyperparameter search, not a free choice.

Test Your Understanding

1. The feature map $\varphi (x_1,x_2)=(x_1^2,x_2^2,x_1{x}_2)$ separates XOR. What hyperplane in the 3D lifted space corresponds to the decision boundary $x_1{x}_2=0$? Express it in terms of $z_1,z_2,z_3$.

2. The polynomial kernel $K(x_i,x_j)=(x_i\cdot x_j+1{)}^2$ computes a 6-dimensional dot product without explicitly computing 6-dimensional vectors. What is the computational cost of computing $K(x_i,x_j)$ in the original 2D space? What would it cost to explicitly compute $\varphi (x_i)\cdot \varphi (x_j)$ in 6D?

3. At $\gamma =0.1$, the RBF kernel fails on XOR (50% accuracy). Explain geometrically: if the RBF kernel is very smooth (large influence radius), what does the learned decision function look like?

4. At $\gamma =100$, all 8 training samples become support vectors. This achieves 100% train accuracy but is likely to generalize poorly. Given the KKT conditions from post 02, what does it mean when every point is a support vector?

5. The linear kernel SVC fails on XOR but would succeed on the lifted XOR data (with $z_3=x_1{x}_2$ as a third feature). If you add $z_3$ as a feature and use a linear kernel, would the result be identical to using an RBF kernel with $\gamma =1$ on the original data? Why or why not?