Kernel methods and the kernel trick

Summary

A kernel computes a feature-space inner product without explicitly constructing the feature vectors. Write $k (x, x^{'}) = ⟨ ϕ (x), ϕ (x^{'})⟩$ . An algorithm expressed through these inner products can use the kernel directly, preserving the feature-space calculation. The shortcut avoids feature construction; it does not automatically avoid pairwise dataset storage or expensive training solves.

The trick

Suppose the desired feature-space algorithm reads inputs only through $⟨ ϕ (x_{i}), ϕ (x_{j})⟩$ . For two-dimensional inputs, consider

k (x, x^{'}) = (x^{⊤} x^{'} + 1)^{2} .

An exact feature map is

ϕ (x) = (x_{1}^{2}, 2 x_{1} x_{2}, x_{2}^{2}, 2 x_{1}, 2 x_{2}, 1) .

Expanding the feature inner product reproduces the squared polynomial, including its cross-term coefficients. For $x = (2, 1)$ and $x^{'} = (1, 3)$ , the six contributions are $4, 12, 9, 4, 6, 1$ , totaling $36$ . The shortcut obtains $(5 + 1)^{2} = 36$ from the original coordinates. In $d$ dimensions, explicit degree-two features number $(2 d + 2)$ ; one kernel evaluation needs $O (d)$ arithmetic.

Learning objective

The kernel reaches 36 without constructing either feature vector

Derivation

Read it this way: both routes return 36. The explicit route constructs six-coordinate features; the kernel route evaluates the polynomial directly. This skips feature construction without approximating the inner product. References: Burges's SVM tutorial and scikit-learn's SVM formulation.

Check: Which calculation gives the same 36 without materializing either six-dimensional feature vector?

Read it this way: The coordinate dot product is 4; the kernel (4+2)^2 is 36. This is an exact shortcut, not an approximation.
Does the compact route approximate the expanded feature result?

Change the Distance Scale

New task: Define similarity through distance rather than a fixed polynomial expansion.

Picture and change: Use the Gaussian RBF kernel $k (x, x^{'}) = exp (- ∥ x - x^{'} ∥^{2} / (2 σ^{2}))$ , with $σ > 0$ .

Check: The example’s squared distance is $5$ . Bandwidths $σ = 1, 2$ give $e^{- 5/2} \approx 0.0821$ and $e^{- 5/8} \approx 0.5353$ .

Use when: A distance-based smooth similarity matches the task. Over a continuous input domain, this kernel generally needs an infinite-dimensional exact feature space, not a finite polynomial map.

The Gram matrix

For $N$ points, the Gram matrix has entries $K_{ij} = k (x_{i}, x_{j})$ and shape $N \times N$ .

Kernel ridge regression: solve $(K + λ I) α = y$ , then predict $\sum_{i} α_{i} k (x_{i}, x)$ . This convention uses an unnormalized squared-error sum plus $λ$ times the squared function norm.
Kernel PCA: eigendecompose the centered $K$ .
Gaussian processes: use $K + σ^{2} I$ as the covariance.
SVM: dual formulation depends only on $K$ and labels.

New task: Train when a dense Gram matrix exceeds the memory budget.

Picture and change: Approximate $K$ with landmark columns $C$ and their Gram matrix $W$ : $K = C W^{†} C^{⊤}$ .

Check: For $K = I_{2}$ and only the first landmark, $K = diag (1, 0)$ . The second direction is lost; this is no longer the exact kernel trick.

Use when: Measured approximation error is acceptable. A float64 matrix with $100, 000$ rows requires $80$ decimal GB before factorization or solver workspace. Dense direct solves cost cubic arithmetic; practical limits depend on hardware and solver structure.

What makes a valid kernel

A real kernel must be symmetric and give a positive-semidefinite Gram matrix for every finite input collection. Feature inner products satisfy this because

a^{⊤} K a = i \sum a_{i} ϕ (x_{i})^{2} \geq 0.

The converse supplies a Hilbert-space feature representation. Mercer expansions additionally require their own domain and regularity conditions.

Common kernels:

Linear: $k (x, x^{'}) = x^{⊤} x^{'}$ . The trivial case.
Polynomial: $(x^{⊤} x^{'} + c)^{p}$ , with nonnegative integer degree $p$ and $c \geq 0$ .
RBF / Gaussian: $exp (- γ ∥ x - x^{'} ∥^{2})$ , with $γ \geq 0$ .
Laplacian: $exp (- γ ∥ x - x^{'} ∥_{1})$ , with $γ \geq 0$ .
String kernels: count shared substrings.
Graph kernels: count shared subgraphs.

Sums, pointwise products, and nonnegative scalings preserve validity; arbitrary negative scaling does not.

Kernel trick in attention

An inner product in a common feature space is a linear kernel. Attention may use different query and key maps, producing an asymmetric cross-score matrix. Row-normalized attention is not automatically a symmetric PSD Gram matrix. Feature-map attention methods require their particular approximation and normalization guarantees; they are not all RBF random-feature substitutions.

Why deep learning won

Learned representations can adapt similarity to a task; a fixed kernel imposes a chosen geometry. Neither guarantees better results across all datasets. Kernels remain useful for structured prior similarity, Gaussian processes, controlled baselines, and theoretical analysis.

Common pitfalls

Missing coefficients. Omitting the square-root-two factors changes the polynomial feature inner product.
Uncontrolled scale. Feature units change RBF distances and the effective bandwidth.
Confusing shortcuts. An exact kernel evaluation and an approximate low-rank Gram matrix make different guarantees.
Overloaded terminology. A convolution filter called a kernel need not define a PSD similarity function.

Reconstruct

Does a symmetric similarity matrix always define a valid kernel?

No. $[1221]$ is symmetric but has eigenvalue $- 1$ . For $a = (1, - 1)^{⊤}$ , its quadratic form is $- 2$ , which cannot be a squared feature norm.