A linear classifier cannot separate points inside a circle from points outside it. But map each point $(x_1, x_2)$ to $(x_1, x_2, x_1^2 + x_2^2)$ and the classes become separable by a plane. Mapping to a higher-dimensional feature space can make non-linear problems linear. The problem: good feature spaces may have millions or infinitely many dimensions. The kernel trick lets us work in such spaces without ever computing the features.
Feature maps#
Let $\boldsymbol{\phi}: \mathcal{X} \to \mathcal{F}$ map inputs into a feature space. A linear model there, $f(\mathbf{x}) = \mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x}) + b$, is non-linear in $\mathbf{x}$. For degree-2 polynomial features in $d$ dimensions, $\boldsymbol{\phi}$ has $O(d^2)$ components; for degree $p$, $O(d^p)$ — computing them explicitly quickly becomes infeasible.
The trick#
Many algorithms — the SVM dual, ridge regression, PCA, k-means, Gaussian processes — access data only through inner products $\mathbf{x}_i^\top\mathbf{x}_j$. Replace every inner product with a kernel function
that computes the feature-space inner product directly.
The kernelised SVM decision function becomes
— a weighted sum of similarities to the support vectors.
Which functions are valid kernels?#
Mercer's theorem: a symmetric function $k$ corresponds to an inner product in some feature space if and only if, for every finite set of points, the Gram matrix $\mathbf{K}_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$ is positive semi-definite. Valid kernels can be combined: sums, products, positive scalings and $k(f(\mathbf{x}), f(\mathbf{x}'))$ are all kernels. This lets you design kernels for strings, graphs, trees and molecules.
Common kernels#
| Kernel | Formula | Notes |
|---|---|---|
| Linear | $\mathbf{x}^\top\mathbf{x}'$ | No mapping; fast |
| Polynomial | $(\gamma\,\mathbf{x}^\top\mathbf{x}' + r)^p$ | Interactions up to degree $p$ |
| RBF / Gaussian | $\exp(-\gamma\|\mathbf{x} - \mathbf{x}'\|^2)$ | Infinite-dimensional feature space; the default |
| Laplacian | $\exp(-\gamma\|\mathbf{x} - \mathbf{x}'\|_1)$ | Less smooth |
| Sigmoid | $\tanh(\gamma\,\mathbf{x}^\top\mathbf{x}' + r)$ | Not always PSD |
| String / graph kernels | Count shared substructures | Text, proteins, molecules |
Understanding the RBF kernel#
The RBF kernel measures similarity that decays with squared distance. Its feature space is infinite-dimensional (its Taylor expansion contains polynomials of every degree). The parameter $\gamma$ sets the reach of each training example:
- Large $\gamma$: narrow bumps — each point influences only its immediate neighbourhood → wiggly boundary, overfitting risk (in the limit, like 1-NN).
- Small $\gamma$: wide bumps → smooth, nearly linear boundary, underfitting risk.
$C$ and $\gamma$ interact strongly; tune them jointly on a logarithmic grid.
import numpy as np
from sklearn.datasets import make_circles
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
X, y = make_circles(n_samples=600, factor=0.4, noise=0.12, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)
print("linear kernel acc:", SVC(kernel="linear").fit(X_tr, y_tr).score(X_te, y_te).round(3))
grid = GridSearchCV(make_pipeline(StandardScaler(), SVC(kernel="rbf")),
{"svc__C": np.logspace(-2, 3, 6), "svc__gamma": np.logspace(-3, 2, 6)},
cv=5).fit(X_tr, y_tr)
print("best RBF params:", grid.best_params_, " test acc:", round(grid.score(X_te, y_te), 3))The linear SVM performs near chance on concentric circles; the RBF SVM separates them almost perfectly.
Other kernel methods#
- Kernel ridge regression: $\hat{f}(\mathbf{x}) = \mathbf{k}(\mathbf{x})^\top(\mathbf{K} + \lambda\mathbf{I})^{-1}\mathbf{y}$ — closed form.
- Gaussian processes: a Bayesian view where the kernel is the covariance function; they give predictions with uncertainty and are the engine of Bayesian optimisation.
- Kernel PCA: non-linear dimensionality reduction.
- Support vector regression (SVR): uses an $\epsilon$-insensitive loss.
The representer theorem explains why these all work: for a broad class of regularised problems, the optimal function is a linear combination of kernel evaluations at the training points, $f(\cdot) = \sum_i\alpha_ik(\mathbf{x}_i, \cdot)$.
Limitations and remedies#
- Scalability: the Gram matrix is $n \times n$ — memory $O(n^2)$, training up to $O(n^3)$. Beyond roughly 50,000–100,000 examples, exact kernel methods become impractical.
- Remedies: Random Fourier features (Rahimi & Recht) approximate shift-invariant kernels with an explicit random feature map of modest dimension, so a linear model can be used; the Nyström method approximates the Gram matrix with a subset of points.
- Kernel choice encodes prior knowledge but must be made by hand, whereas neural networks learn their features. Interestingly, theory shows that infinitely wide neural networks behave like kernel methods (the Neural Tangent Kernel), a bridge between the two worlds.
from sklearn.kernel_approximation import RBFSampler
from sklearn.linear_model import SGDClassifier
approx = make_pipeline(StandardScaler(), RBFSampler(gamma=1.0, n_components=500, random_state=0),
SGDClassifier(loss="hinge", alpha=1e-4, random_state=0))
print("random Fourier features acc:", approx.fit(X_tr, y_tr).score(X_te, y_te).round(3))