The Kernel TrickOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

The Kernel Trick

Linear SVMs can only draw straight decision boundaries. But what if the true boundary is a circle, a spiral, or something complex? The kernel trick solves this by implicitly mapping data to a higher-dimensional space where it becomes linearly separable — without ever computing that mapping. It's a hypothesis-space change: same margin objective, same optimizer, but a vastly richer family of boundaries the model can now express.

Real-world examples: Gene expression analysis, image recognition, anomaly detection in network traffic.

The problem with linear boundaries

Consider data arranged in concentric circles — inner ring is class A, outer ring is class B. No straight line can separate them. But if we map to 3D using z=x2+y2z = x^2 + y^2, the classes become separable by a plane.

Intuition

Imagine looking at a chessboard from above — the black and white squares are interleaved and not linearly separable. Now tilt the board: suddenly you can draw a plane that separates them. The kernel trick does this "tilting" implicitly.

What is a kernel?

A kernel function computes the dot product in a higher-dimensional space without actually going there:

K(xi,xj)=ϕ(xi)Tϕ(xj)K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)

where ϕ\phi is the mapping to the higher-dimensional space. The key insight: the SVM optimization only needs dot products, so we can replace them with kernel evaluations.

Common kernels

Polynomial kernel

K(xi,xj)=(γ xiTxj+r)dK(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \, \mathbf{x}_i^T \mathbf{x}_j + r)^d

Maps to a space of all monomials up to degree dd. For d=2d=2, γ=1\gamma=1, r=1r=1 and 2D input (x1,x2)(x_1, x_2):

ϕ(x1,x2)=(x12,  x22,  2 x1x2,  2 x1,  2 x2,  1)\phi(x_1, x_2) = (x_1^2,\; x_2^2,\; \sqrt{2}\, x_1 x_2,\; \sqrt{2}\, x_1,\; \sqrt{2}\, x_2,\; 1)

Why this ϕ\phi works: expand the kernel. Take two points x=(x1,x2)\mathbf x=(x_1,x_2), z=(z1,z2)\mathbf z=(z_1,z_2) and expand the kernel directly:

(x⊤z+1)2=(x1z1+x2z2+1)2(\mathbf{x}^\top\mathbf{z}+1)^2 = (x_1 z_1 + x_2 z_2 + 1)^2 =x12z12+x22z22+2x1x2z1z2+2x1z1+2x2z2+1.= x_1^2 z_1^2 + x_2^2 z_2^2 + 2x_1 x_2 z_1 z_2 + 2x_1 z_1 + 2 x_2 z_2 + 1.

Now group the cross terms using 2ab=(2a)(2b)2ab=(\sqrt2 a)(\sqrt2 b). This is exactly ϕ(x)⊤ϕ(z)\phi(\mathbf x)^\top\phi(\mathbf z):

=x12z12⏟+x22z22⏟+(2x1x2)(2z1z2)⏟+(2x1)(2z1)⏟+(2x2)(2z2)⏟+1⋅1⏟.= \underbrace{x_1^2 z_1^2}_{} + \underbrace{x_2^2 z_2^2}_{} + \underbrace{(\sqrt2 x_1x_2)(\sqrt2 z_1z_2)}_{} + \underbrace{(\sqrt2 x_1)(\sqrt2 z_1)}_{} + \underbrace{(\sqrt2 x_2)(\sqrt2 z_2)}_{} + \underbrace{1\cdot1}_{}.

So the 2\sqrt2 factors in ϕ\phi are exactly what's needed to make the explicit dot product equal the cheap kernel evaluation. We get a 6-D feature space for the cost of one dot product and a square — that's the trick.

RBF (Gaussian) kernel

K(xi,xj)=exp⁡(−γ∥xi−xj∥2)K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2\right)

Maps to an infinite-dimensional space. The most popular kernel. It can learn any decision boundary given enough support vectors.

  • γ\gamma small: smooth boundary, more regularization
  • γ\gamma large: complex boundary, risk of overfitting

RBF kernel intuition

Think of γ\gamma as controlling the "reach" of each training example. Small γ\gamma: each example influences a wide region (smooth boundary). Large γ\gamma: each example only influences its immediate neighborhood (jagged boundary).

Sigmoid kernel

K(xi,xj)=tanh⁡(γ xiTxj+r)K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \, \mathbf{x}_i^T \mathbf{x}_j + r)

Similar to a neural network with one hidden layer. Less commonly used.

The visualization below shows both the original 2D space (left) and the implicit feature mapping (right) — switch between kernels and adjust γ to see how the decision boundary changes.

Kernel Trick: Original Space vs Feature Space

Original 2D Space

x₁x₂

RBF Similarity to Inner Class

cHigh similarity (blue) = inner class region
kernelRBF
γ0.5
inner pts12
outer pts18

Left: original 2D data with kernel decision boundary. Right: implicit feature mapping. Switch kernels to see how RBF and Polynomial can separate concentric rings that no linear boundary can split.

Worked example

Numeric check of the trick. Let x=(1,2)\mathbf x=(1,2), z=(3,−1)\mathbf z=(3,-1).

  • Cheap kernel: x⊤z=1⋅3+2⋅(−1)=1\mathbf x^\top\mathbf z = 1{\cdot}3 + 2{\cdot}(-1) = 1, so (x⊤z+1)2=22=4(\mathbf x^\top\mathbf z+1)^2 = 2^2 = 4.
  • Explicit map: ϕ(x)=(1,4,22,2,22,1)\phi(\mathbf x)=(1,4,2\sqrt2,\sqrt2,2\sqrt2,1), ϕ(z)=(9,1,−32,32,−2,1)\phi(\mathbf z)=(9,1,-3\sqrt2,3\sqrt2,-\sqrt2,1). Their dot product is 9+4−12+6−4+1=49+4-12+6-4+1 = 4. ✓

Same answer, but the kernel never built the 6-D vectors. For an RBF kernel the equivalent ϕ\phi is infinite-dimensional: expanding via the Taylor series eu=∑n=0∞un/n!e^u = \sum_{n=0}^\infty u^n/n! with u=2γ x⊤zu = 2\gamma\,\mathbf{x}^\top\mathbf{z} shows that every monomial of every degree appears in the feature map, yet KK is still one cheap exponential.

What makes a function a valid kernel?

Not every KK corresponds to some ϕ\phi. Mercer's condition: KK is a valid kernel iff for every finite set of points the Gram matrix Kij=K(xi,xj)K_{ij}=K(\mathbf x_i,\mathbf x_j) is symmetric positive semi-definite — roughly, the pairwise similarity scores must respect the geometry of a real inner product space (no "impossible" similarity configurations). Linear, polynomial, and RBF all satisfy this; the sigmoid kernel does not in general, which is why it can misbehave.

Now a non-separable dataset where only a kernel can succeed:

Python
import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_circles

# Non-linearly separable data
X, y = make_circles(n_samples=200, noise=0.1, factor=0.3, random_state=42)

# Linear SVM fails
linear_svm = SVC(kernel='linear', C=1)
linear_svm.fit(X, y)
print(f"Linear accuracy: {linear_svm.score(X, y):.3f}")  # ~0.5-0.6

# RBF kernel succeeds
rbf_svm = SVC(kernel='rbf', C=1, gamma='scale')
rbf_svm.fit(X, y)
print(f"RBF accuracy: {rbf_svm.score(X, y):.3f}")  # ~1.0

print(f"Support vectors: {len(rbf_svm.support_vectors_)}")

The kernel trick in the SVM objective

The dual form of the SVM optimization uses only dot products:

max⁡α∑iαi−12∑i,jαiαjyiyj xiTxj\max_\alpha \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \, \mathbf{x}_i^T \mathbf{x}_j

With the kernel trick, replace xiTxj\mathbf{x}_i^T \mathbf{x}_j with K(xi,xj)K(\mathbf{x}_i, \mathbf{x}_j):

max⁡α∑iαi−12∑i,jαiαjyiyj K(xi,xj)\max_\alpha \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \, K(\mathbf{x}_i, \mathbf{x}_j)

Prediction becomes:

f(x)=sign(∑i∈SVαiyi K(xi,x)+b)f(\mathbf{x}) = \text{sign}\left(\sum_{i \in SV} \alpha_i y_i \, K(\mathbf{x}_i, \mathbf{x}) + b\right)

Only support vectors (where αi>0\alpha_i > 0) contribute to the prediction.

Choosing the right kernel

KernelWhen to useParameters
LinearHigh-dimensional, many features (text)None
RBFDefault choice, non-linear, unknown structureγ\gamma, CC
PolynomialKnown polynomial relationshipdegree dd, rr

Hyperparameter tuning

Python
# The idiom (for your own X_train / y_train / X_test / y_test):
from sklearn.model_selection import GridSearchCV

param_grid = {
    'C': [0.1, 1, 10, 100],
    'gamma': [0.01, 0.1, 1, 10],
    'kernel': ['rbf']
}

grid = GridSearchCV(SVC(), param_grid, cv=5, scoring='accuracy')
grid.fit(X_train, y_train)

print(f"Best params: {grid.best_params_}")
print(f"Best CV accuracy: {grid.best_score_:.3f}")
print(f"Test accuracy: {grid.score(X_test, y_test):.3f}")

Kernel SVM scaling

Kernel SVMs don't scale well — training is O(n2)O(n^2) to O(n3)O(n^3) in the number of samples. For datasets larger than ~50K samples, consider:

  • Linear SVM (LinearSVC or SGDClassifier)
  • Random feature approximations (Nyström, RFF)
  • Gradient-boosted trees (XGBoost, LightGBM)

Exercise

What is the RBF kernel value K(x₁, x₂) when the two points are identical?

Need a hint?

K(x, x) = exp(-||x-x||² / 2σ²).

Exercise

When should you use a linear kernel instead of RBF?

Need a hint?

Think about high-dimensional data with many features.

Exercise

In an RBF kernel, what does increasing gamma do?

Need a hint?

Gamma controls the 'reach' of each training example.

Exercise

Set the RBF kernel γ for an SVM to capture non-linear structure without memorizing every training point.

0.0015.0010
Need a hint?

High γ = tight kernels → complex/jagged boundary. Low γ = wide kernels → smooth boundary.

Common mistakes

  1. Using RBF on high-dimensional data: In high dimensions, all points are equidistant. Use linear kernel when d>nd > n (more features than samples).
  2. Not scaling features: Kernels compute distances. Unscaled features dominate the distance metric.
  3. Default γ\gamma on small datasets: Use gamma='scale' or 'auto', or tune via grid search. ('scale' sets γ=1/(nfeatures⋅var(X))\gamma = 1 / (n_{\text{features}} \cdot \text{var}(X)) — features, not samples.)

Key takeaways

  • Kernels let a linear SVM learn non-linear boundaries via implicit feature maps.
  • RBF is the go-to general kernel; polynomial and linear are alternatives.
  • C controls margin softness; gamma controls RBF reach — tune them together.
  • Large gamma/C overfits; always scale features before kernel SVMs.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelated
The Kernel TrickLinear & Logistic Regress…Linear Algebra for MLMaximum Margin Classifica…Constrained Optimization …Principal Component Analy…Soft Margins & Tuning CGaussian Processes