Kernel Functions

A kernel tells you how alike two points are by returning their dot product in some big feature space, computed directly from the original coordinates without ever building that space.

Two inputs lift into a large feature space while the kernel shortcut returns 0.607 directly from the raw coordinates

Why Does This Exist?

Linear methods are fast but blind to curves: no straight line separates a ring from its center. Lifting points into a richer feature space fixes the blindness, yet the lifted coordinates can be infinite-dimensional, so building them is impossible. Kernels break the deadlock, because algorithms like SVMs only ever need dot products between lifted points, and the kernel computes those from raw inputs.

This page defines what makes a function a valid kernel and checks one on numbers. The algorithm spending those dot products is the kernel trick. The matrix facts underneath are in positive definite matrices.

The one idea you need first

A positive definite matrix has all eigenvalues above zero, so every quadratic form through it stays nonnegative. Kernel validity demands exactly this of every Gram matrix you can build. No collection of points may force the similarities into a geometrically impossible shape.

Think of It Like This

A spice blend rated without tasting each spice

A chef rates how well two dishes pair from one sniff of each finished plate, without listing every molecule. The score behaves like a dot product of full ingredient lists that nobody wrote down.

A kernel is that sniff. Two raw inputs go in, one similarity number comes out, and the number equals the inner product in a feature kitchen you never enter.

Where it stops: not every similarity qualifies. Only positive definite ones correspond to a real feature space, while the rest silently produce nonsense geometry.

How It Actually Works

A function $k(x, z)$ is a kernel when it is symmetric and positive definite: for every finite set $x_1, \ldots, x_n$ , the Gram matrix $K_{ij} = k(x_i, x_j)$ is positive semidefinite, meaning $c^\top K c \geq 0$ for all $c$ . In plain words, $k$ returns a similarity that can always be realized as dot products somewhere.

Three kernels carry nearly all of practice. Linear: $k(x, z) = x^\top z$ . Polynomial: $k(x, z) = (x^\top z + c)^d$ . Gaussian RBF: $k(x, z) = \exp(-\|x - z\|^2 / 2 \sigma^2)$ with width $\sigma$ . Mercer theorem says each valid kernel genuinely equals $\langle \phi(x), \phi(z) \rangle$ in some Hilbert space, and the RBF space is infinite-dimensional.

Worked example

Take the RBF kernel with $\sigma = 1$ on points $x = 0$ and $z = 1$ . Then $\|x - z\|^2 = 1$ , so $k(0, 1) = \exp(-1/2) \approx 0.607$ . Diagonal entries are $k(0, 0) = k(1, 1) = 1$ , giving:

K = \begin{bmatrix} 1 & 0.607 \\ 0.607 & 1 \end{bmatrix}

Eigenvalues are $1 + 0.607 = 1.607$ and $1 - 0.607 = 0.393$ . Both are positive, so $K$ is positive definite and this kernel behaves like a genuine dot product here. Small widths push $0.607$ toward $0$ for near-orthogonality, while large widths push it toward $1$ for near-identity.

Code

Build the Gram matrix and check its eigenvalues stay positive, the validity test for any kernel.

1import numpy as np2
3
4def rbf_gram(xs: np.ndarray, sigma: float = 1.0) -> np.ndarray:5    d2 = (xs[:, None] - xs[None, :]) ** 2  # pairwise squared distances6    return np.exp(-d2 / (2 * sigma**2))  # RBF similarity7
8
9xs = np.array([0.0, 1.0])10print(rbf_gram(xs))  # -> [[1. 0.607] [0.607 1.]]11print(np.linalg.eigvalsh(rbf_gram(xs)))  # -> [0.393 1.607]

Ones on the diagonal, $0.607$ off it, eigenvalues $0.39$ and $1.61$ : positive, exactly as computed by hand.

Watch Out For

Inventing a similarity that is not positive definite

A custom kernel can train fine on small data, then yield indefinite Gram matrices with negative eigenvalues like $-0.3$ while the optimizer oscillates.

Eigencheck every new kernel on a few hundred points first. Build custom kernels only from sums, products, and scalings of known-valid ones.

Setting the RBF width by gut feeling

Tiny $\sigma$ drives every off-diagonal Gram entry toward $0$ for memorization, while huge $\sigma$ drives them toward $1$ for underfit.

Grid-search $\sigma$ against validation error, or start from the median pairwise distance heuristic and tune from there.

The Quick Version

A kernel returns the dot product in a feature space you never construct.
Validity means every Gram matrix is positive semidefinite, checked through eigenvalues.
Linear, polynomial, and RBF kernels cover nearly all practice, and the RBF feature space is infinite-dimensional.
Points 0 and 1 with unit width score 0.607, with Gram eigenvalues 1.61 and 0.39.
Width controls similarity scale, since small widths orthogonalize while large widths merge.