What does Mercer's condition require, and why isn't every similarity function a valid kernel?
answer
- symmetry plus something about eigenvalues
- the matrix of pairwise values matters
- no negative eigenvalues allowed
- positive semi-definite Gram matrix
- PSD guarantees a feature space exists
basics
~20 sA kernel must be symmetric and produce a positive semi-definite matrix of pairwise values on every finite set of points. Only then does it correspond to a genuine inner product in some feature space, which is what the whole method assumes.
solid answer
~50 sFor a function `k` to be usable as a kernel it has to be symmetric — `k(x, z) = k(z, x)` — and for any finite set of points the matrix `K` with `K_ij = k(x_i, x_j)` must be positive semi-definite, meaning it has no negative eigenvalues. That is Mercer's condition, and it is exactly the guarantee that some feature map `phi` exists with `k(x, z) = <phi(x), phi(z)>`. Hand-built similarity scores routinely fail it: you can invent something intuitive, symmetric and bounded that still yields a matrix with negative eigenvalues, because there is no feature space it could be an inner product in. Feed one to a margin solver and the optimisation stops being convex — no guaranteed unique optimum, and the geometry the method reasons about no longer exists. The cheap safeguard is to build new kernels from known ones: sums, positive multiples and products of valid kernels are valid.
go deeper
Recall that a kernel is not just any similarity score — it has to satisfy a mathematical condition, and the standard linear, polynomial and RBF choices already do. Inventing your own similarity measure is not automatically safe.
State the condition precisely: symmetric, and the matrix of pairwise values must be positive semi-definite for any finite set of points. Explain that this is what guarantees a feature map exists, which is the assumption the whole method rests on.
Show you would actually check, and know what a failure costs: a non-convex training problem, unstable solutions and a margin with no geometry behind it. Know the repairs — eigenvalue clipping, spectrum shifting — and that both change the similarities you were given.
Frame kernel design as an engineering discipline: prefer composing from known-valid pieces via sums and products over hand-built matrices, and decide when a custom domain kernel is worth the validation burden versus using features a simpler model can consume.
## The condition A function `k(x, z)` of two points qualifies as a kernel when two things hold: 1. **Symmetry**: `k(x, z) = k(z, x)` for all inputs. 2. **Positive semi-definiteness**: for *any* finite collection of points `x_1, ..., x_n`, the n-by-n Gram matrix `K` with entries `K_ij = k(x_i, x_j)` is positive semi-definite — equivalently, all of its eigenvalues are greater than or equal to zero, or `c^T K c >= 0` for every real vector `c`. This is Mercer's condition. Its payoff is an existence theorem: if it holds, there is a feature map `phi` into some inner-product space with `k(x, z) = <phi(x), phi(z)>`. You never have to construct `phi`; you just need to know it exists, because every step of a kernel method is reasoning about geometry in that space. ## Why intuition is not enough The tempting move is to write down whatever similarity score your domain suggests — an edit-distance-derived score, a hand-tuned overlap measure, an expert-elicited table of "how alike are these two cases" — and drop it in where the kernel goes. It is symmetric, it is bounded, similar things score high. Surely that is a kernel? Often it is not. Consider being handed a hand-built similarity matrix over a few hundred cases, assembled by domain experts. Symmetric, diagonal all ones, everything in [0, 1]. Compute its eigenvalues and several come out negative. Those negative eigenvalues are a proof that no feature space exists in which these numbers are inner products: an inner-product Gram matrix cannot have one, because `c^T K c` is the squared norm of a vector in that space and squared norms are not negative. The similarity scores are internally inconsistent as a geometry — for instance they can imply that A is very close to B and to C while B and C are far apart by more than the triangle inequality permits. ## What goes wrong if you use one anyway A margin classifier's training problem is a quadratic optimisation whose curvature comes from the kernel matrix. With a positive semi-definite `K` that problem is convex: one global optimum, a solver that converges to it, and a solution independent of where it started. With negative eigenvalues in `K` the problem becomes non-convex. In practice you see solvers failing to converge, results that shift when you reorder or re-seed the data, objective values that drift below where a convex problem could go, and an optimum whose margin interpretation is meaningless because the space it claims to maximise a margin in does not exist. The model may still emit predictions; you simply cannot say what it optimised. ## Doing it safely The practical route is composition. If `k1` and `k2` are valid kernels then so are `k1 + k2`, `a*k1` for any `a > 0`, the product `k1*k2`, and `f(x)*k1(x, z)*f(z)` for any real-valued function `f`. Build your domain kernel out of parts you already trust and the result inherits the guarantee — no eigenvalue check required. This is how multi-source kernels are assembled: a kernel on numeric features plus a kernel on structured features is itself a kernel. If you already have a matrix and need to know, check it directly: compute the eigenvalues of the Gram matrix on a decent sample of points and look for negative ones. Note that the check is over every finite subset in principle, so passing on one sample is evidence rather than proof — but a failure on one sample is proof of failure. When a matrix does fail there are standard repairs: clip the negative eigenvalues to zero and rebuild the matrix, or shift the whole spectrum by adding a small multiple of the identity, which lifts every eigenvalue by the same amount and touches only the diagonal. Both alter the similarities you were handed, which is the honest cost: you are no longer using the experts' numbers, you are using the nearest consistent geometry to them. ## A caution about well-known formulas Not everything that circulates under the name "kernel" satisfies the condition unconditionally. The hyperbolic-tangent similarity `tanh(a*(x . z) + r)` is the standard example: for many choices of `a` and `r` its Gram matrix is not positive semi-definite, so it is not a kernel at those settings even though it is widely quoted as one. The linear, polynomial and RBF kernels are safe; anything else deserves a check before it goes near a solver.
- Domain experts hand you a symmetric similarity matrix whose eigenvalues include negative ones. What do you do?First say what it means: no feature space exists in which those numbers are inner products, so a margin solver would face a non-convex problem with no meaningful geometry. Then either rebuild the similarity from valid kernel pieces composed with sums and products, or project the matrix to the nearest valid one by clipping the negative eigenvalues to zero or shifting the spectrum. Both repairs change the experts' numbers, and you should say so.
- How can you combine a kernel on numeric features with one on structured features and stay valid?Add them, or multiply them, or take a positive-weighted sum. Sums, positive scalar multiples and products of valid kernels are themselves valid kernels, so the composite inherits the guarantee with no eigenvalue check needed. The weights in the sum then become hyperparameters controlling how much each source contributes.
- You checked the Gram matrix on a 500-point sample and it was positive semi-definite. Is the function a valid kernel?Not proven. The condition quantifies over every finite set of points, so one clean sample is encouraging evidence rather than a proof — a different or larger sample could still produce a negative eigenvalue. A failure on any single sample, by contrast, is conclusive proof that the function is not a kernel.
saying these in an interview costs you the question
- Says any symmetric similarity function can serve as a kernel
- Confuses positive semi-definite with all entries being positive
- Thinks a diagonal of ones is enough to make a matrix valid
- Cannot say what breaks when the condition fails
- Believes negative eigenvalues just slow the solver down