SVM Kernels

The linear SVM finds the maximum-margin hyperplane in the original feature space. When classes aren't linearly separable — like the XOR pattern — no hyperplane works, no matter how wide a margin you allow. The kernel trick solves this without ever explicitly computing a high-dimensional transformation.

Anchor dataset: XOR classification. Four points in the positive class, four in the negative class, arranged so no line can separate them.

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 gets only 50% accuracy — equivalent to random guessing. The XOR pattern requires a nonlinear boundary.

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 Feature Map Solution

Instead of drawing a line in 2D, 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.

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.

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.

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.

$\gamma$ Effect on the Decision Boundary

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]}")

At $\gamma =0.1$: still fails — the RBF kernel is too smooth (each point's influence extends very far, averaging out the XOR structure). At $\gamma =1$: perfectly separates — four support vectors, tight 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.

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.

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?