Is every similarity function a valid kernel?

No. Standard positive-semidefinite kernel methods require more than intuitive similarity or symmetry.

Must the feature map be computed explicitly?

No. Algorithms using inner products can often work directly with kernel evaluations.

Does one positive-semidefinite Gram matrix prove global validity?

No. Kernel validity concerns every finite collection from the stated domain; one counterexample can disprove it.

AI Glossary / Mathematics and optimization / Advanced

Mercer's theorem

Definition

Mercer's theorem is a result explaining how suitable continuous, symmetric, positive-semidefinite kernels can be represented by nonnegative eigenvalues and associated eigenfunctions. In a classical compact-domain setting, it gives a convergent expansion of the kernel into products of those functions. This connects kernel similarities with inner products in a feature space.

What it means

A kernel K(x,y) assigns a number to a pair of inputs. For kernel methods, the important question is not merely whether the number seems like a plausible similarity, but whether the function has the required positive-semidefinite structure.

Machine-learning introductions often use “Mercer's theorem” broadly when discussing valid kernels and feature maps. The classical spectral theorem has additional domain, continuity, and measure assumptions. The more general fact that a positive-semidefinite kernel admits a Hilbert-space feature representation should not be conflated with every detail of a Mercer eigenfunction expansion. This entry keeps that distinction explicit.

How it works

For a real symmetric kernel, positive semidefiniteness means that every finite Gram matrix G, with G_ij=K(x_i,x_j), satisfies cᵀGc≥0 for every real coefficient vector c. This is a global condition over all finite input collections, not just one training sample.

In a standard classical setting, take a continuous symmetric positive-semidefinite kernel on a compact interval with the usual integration measure. Its integral operator has nonnegative eigenvalues, and the kernel can be expanded using associated orthonormal eigenfunctions. Writing the expansion schematically as K(x,y)=sum_j lambda_j e_j(x)e_j(y), the coordinates sqrt(lambda_j)e_j(x) supply a feature representation.

An algorithm that uses only feature inner products can then evaluate K(x,y) without constructing every coordinate explicitly. This is the kernel trick. The theorem justifies a representation under its assumptions; it does not automatically establish that a chosen kernel models the data well or that a resulting predictor generalizes.

Three practical examples

1. Support-vector methods: understand why a valid kernel can replace an explicit feature inner product in the model's optimization and predictions.

2. Kernel approximation: motivate spectral representations and investigate how truncating an expansion changes the represented similarity.

3. Custom similarity review: test whether a proposed function has a positive-semidefinite justification before treating it as a standard kernel in an algorithm that requires one.

Think of it this way

Think of a similarity table that can be explained by hidden coordinates: each entry equals the inner product of the coordinates assigned to its two objects. Mercer theory provides a structured version of this connection under specified conditions.

The analogy does not mean that a visually appealing similarity table necessarily has such a representation, or that its hidden coordinates have an obvious human meaning. It also distinguishes a finite table from a kernel defined over an entire domain.

Worked example

Consider K(x,y)=1+xy on the compact interval [−1,1]. A direct feature map is phi(x)=(1,x), because phi(x)·phi(y)=1+xy. This already proves positive semidefiniteness: any quadratic form built from a finite Gram matrix equals the squared length of a weighted sum of feature vectors.

Using ordinary Lebesgue integration on [−1,1], take e_1(x)=1/√2 and e_2(x)=√(3/2)x. They are orthonormal: their squared integrals are one and their cross integral is zero. The associated nonzero eigenvalues are 2 and 2/3. The expansion gives 2×(1/√2)×(1/√2)+(2/3)×√(3/2)x×√(3/2)y=1+xy, exactly recovering K.

For contrast, a proposed two-point Gram matrix with rows (1,2) and (2,1) is not positive semidefinite. With c=(1,−1), cᵀGc=−2. Its positive entries and symmetry do not rescue it. This finite counterexample is enough to disprove kernel validity for a function producing that matrix, although passing one finite check would not prove validity everywhere.

Illustrative case study

Fictional case: an analytics team designs a custom similarity score for documents and wants to use it in a standard kernel classifier. The score looks sensible in examples, but one sampled Gram matrix has a materially negative quadratic form.

The team checks its implementation and mathematical construction before proceeding. It considers a similarity built from an explicit feature map, which supplies a clear positive-semidefinite argument. It separately tests predictive performance. The review distinguishes mathematical compatibility with a method from whether the similarity captures useful document relationships.

Common misconceptions and mistakes

Positive-semidefinite does not mean every kernel value is positive, nor does symmetry alone suffice. It refers to all the relevant finite quadratic forms being nonnegative.

A positive-semidefinite matrix on one dataset does not prove that a candidate kernel is valid on every input set. A finite matrix eigendecomposition is related to, but not identical with, an integral-operator eigenfunction expansion. Finally, assumptions for uniform convergence or particular spectral approximations must be stated rather than inferred from the phrase kernel trick.

Business use

For a business team using kernel-based models, the theorem explains part of the mathematical justification behind an otherwise abstract similarity calculation. Its practical relevance is strongest when choosing or modifying a kernel, or assessing an approximation designed to reduce computation.

Ask both whether the construction meets the method's requirements and whether it performs well on representative held-out data. Mathematical validity does not guarantee interpretability, efficient scaling, or predictive advantage. Those are additional design and evaluation questions.

Check your understanding

A symmetric similarity matrix has only positive entries. Is that enough to conclude it is positive semidefinite?

Answer: No. The matrix with diagonal entries 1 and off-diagonal entries 2 gives a negative quadratic form for (1,−1).

Related terms

Kernel function
Gram matrix
Hilbert space
Kernel trick
Support vector machine
positive semidefinite
eigenfunction
spectral approximation

Learn next

derive positive semidefiniteness from an explicit feature map. Then compare finite Gram-matrix eigenvectors with integral-operator eigenfunctions and study how assumptions affect a truncated kernel expansion.

Sources

Yee Whye Teh, Oxford kernel-method lecture slides: https://www.stats.ox.ac.uk/~teh/teaching/smldmHT2014/W5slides.pdf . Rustem Takhanov, primary abstract summarizing classical Mercer expansion: https://arxiv.org/abs/2205.00487 . Relevant passages were read. Classical spectral assumptions and broader feature-map usage are distinguished. The interval expansion and counterexample are original calculations.

Previous: Mentions Next: Merge-scan