Mercer's Theorem
Kernel methods feel a bit like a magic trick: you act as if your data has been lifted into a huge feature space where a linear model works, without ever building those features explicitly. Mercer’s Theorem is one of the key results that tells you when that “trick” is mathematically legitimate.
What Mercer’s Theorem guarantees
In supervised learning, a kernel is a function k(x, x') that behaves like an inner product in some (possibly infinite-dimensional) feature space: k(x, x') = ⟨φ(x), φ(x')⟩. Mercer’s Theorem gives conditions under which such a feature map φ exists. In practical terms: if a kernel is symmetric and positive semidefinite (PSD) in the right sense, then it corresponds to a valid inner product, and algorithms like SVMs can safely use it.
The PSD “kernel matrix” test
Given training points, you build the Gram matrix K where K_ij = k(x_i, x_j). Mercer’s condition shows up as:
- K must be positive semidefinite: for any vector c, cᵀ K c ≥ 0.
- Equivalently, K has no negative eigenvalues (up to numerical noise).
This matters because SVM training is a convex optimization problem only when the kernel is PSD; violate it and you can get unstable training or solutions that aren’t well-defined.
Why you care in real models
When you pick an RBF kernel for spam detection or a polynomial kernel for credit scoring, Mercer’s Theorem is the reason those choices “work” as kernels at all. In libraries like scikit-learn’s SVC, standard kernels are Mercer-valid by construction; trouble usually appears with custom similarity functions that feel reasonable but aren’t PSD.
Mercer’s Theorem gives the condition under which a symmetric function kernel corresponds to an inner product in some (possibly infinite-dimensional) feature space: its associated Gram matrix is positive semidefinite for any finite set of inputs. This matters because it justifies the kernel trick in SVMs and other supervised learners—only Mercer kernels guarantee convex optimization and valid similarity computations (e.g., RBF and polynomial kernels).
Think of a kernel like a “similarity score” between two things, such as two emails or two photos. If the similarity score behaves sensibly, an SVM can use it to draw a reliable boundary between categories, even when the boundary is curved and complicated.
Mercer’s Theorem is the rulebook that tells you whether a proposed kernel is “safe” to use. It checks that your similarity score could really come from comparing items in some (possibly very large) feature space—like measuring distances after secretly expanding each item into a longer description. When the kernel passes Mercer’s conditions, the SVM’s learning problem stays well-behaved and trustworthy.