The kernel is where you inject knowledge about your data’s structure. Choosing and tuning it is the single most consequential decision in applying an SVM. This chapter surveys the standard kernels, explains the crucial \(\gamma\) parameter of the RBF kernel, shows how kernels extend SVMs to strings, graphs, and other non-vector data, and addresses how to scale kernels to large datasets.

The standard kernels

Kernel Formula \(k(\vx,\vx')\) Use / notes
Linear \(\vx^\top\vx'\) high-dim sparse data (text); fast
Polynomial \((\gamma\,\vx^\top\vx' + r)^d\) explicit feature interactions up to degree \(d\)
RBF / Gaussian \(\exp(-\gamma\|\vx-\vx'\|^2)\) default nonlinear kernel; local, smooth
Sigmoid \(\tanh(\gamma\,\vx^\top\vx' + r)\) neural-net-like; not always PSD

The RBF (Gaussian) kernel is the default first choice for nonlinear problems. It measures similarity as a bump that decays with distance: nearby points are similar (\(k\to1\)), far points dissimilar (\(k\to0\)). It can approximate almost any decision boundary, has only one shape parameter \(\gamma\), and corresponds to an infinite-dimensional feature space. Start with RBF unless you have a reason (linear for text/very-high-dim; polynomial for known interaction structure; custom for structured objects).

The bandwidth \(\gamma\)

For the RBF kernel, \(\gamma\) controls the reach of each support vector — it is an inverse bandwidth:

  • Small \(\gamma\) (wide bumps): each point influences a large region \(\Rightarrow\) smooth, simple boundary, can underfit.

  • Large \(\gamma\) (narrow bumps): each point influences only its immediate vicinity \(\Rightarrow\) wiggly boundary that can overfit, in the limit memorizing the training set.

\(\gamma\) and \(C\) interact strongly and must be tuned together (a 2-D grid/Bayesian search), since both control the bias–variance balance.

Kernels for structured data

Because a kernel only needs to measure similarity, SVMs apply to objects that are not naturally vectors:

  • String kernels count shared substrings/\(k\)-mers — powerful for text and protein/DNA sequences.

  • Graph kernels compare graphs by shared walks, paths, or subtrees — molecules, social networks.

  • Histogram/\(\chi^2\) kernels compare distributions — the bag-of-visual-words era of computer vision.

This is a genuine strength: design a valid (PSD) similarity for your domain, and the entire SVM machinery applies unchanged. You can also combine kernels (sums and products of kernels are kernels) to fuse multiple data sources.

Scaling kernels to large data

Kernel SVMs need the \(n\times n\) Gram matrix, which is \(O(n^2)\) memory and roughly \(O(n^2\text{--}n^3)\) time — impractical beyond \(\sim10^5\) points. The standard escape is to approximate the feature map explicitly and then run a fast linear SVM:

  • Random Fourier Features approximate the RBF kernel with a random low-dimensional map \(\tilde\Phimap(\vx)\) such that \(\tilde\Phimap(\vx)^\top\tilde\Phimap(\vx')\approx k(\vx,\vx')\).

  • Nyström approximation builds a low-rank Gram approximation from a sampled subset of points.

Both turn a kernel SVM into a scalable linear one with almost the same accuracy.

Kernel-selection mistakes are the most common SVM failures. (1) RBF without scaling: distances are dominated by large-range features — always standardize. (2) Default \(\gamma\) blindly: scikit-learn’s gamma="scale" is a sane start but rarely optimal; tune it. (3) High-degree polynomials: numerically unstable and prone to overfitting — prefer RBF. (4) Kernel on millions of rows: use linear SVM or random features instead. (5) Invalid kernels: a hand-rolled similarity that is not PSD can silently break the optimization.

Random Fourier features — approximating a kernel by a random nonlinear map — is a conceptual bridge to deep learning: a single wide random layer followed by a linear classifier is an approximate kernel machine, foreshadowing the Neural Tangent Kernel view that wide networks behave like kernel methods (Chapter [ch:svmmlai]). Structured kernels (string, graph) were the dominant approach to sequences and molecules before RNNs and graph neural networks, and graph kernels remain competitive baselines. The lesson — “encode domain structure into a similarity” — directly informs how modern architectures bake in inductive biases.

from sklearn.svm import SVC
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import GridSearchCV
from sklearn.datasets import load_breast_cancer
X, y = load_breast_cancer(return_X_y=True)
pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
grid = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [1e-3, 1e-2, 1e-1, 1]}
gs = GridSearchCV(pipe, grid, cv=5).fit(X, y)     # tune C and gamma jointly
print("best params:", gs.best_params_, " cv acc:", round(gs.best_score_, 3))

Chapter summary

  • Standard kernels: linear (text/high-dim), polynomial (interactions), RBF (default nonlinear), sigmoid (risky).

  • For RBF, \(\gamma\) is inverse bandwidth: small \(\gamma\) underfits (smooth), large \(\gamma\) overfits (wiggly); tune with \(C\).

  • Kernels extend SVMs to strings, graphs, histograms — any domain with a valid PSD similarity; kernels can be combined.

  • Kernel SVMs are \(O(n^2)\); scale via random Fourier features or Nyström + linear SVM.

  • Always standardize, and tune the RBF \(\gamma\) jointly with \(C\); random-feature maps prefigure the kernel view of wide networks.