Kernels, Gram Matrices, and Implicit Feature Spaces

Each family encodes a different prior about useful similarity.

The linear kernel, k(x,z)=xᵀz, works in the original feature space. It is fast and interpretable on sparse data, it is the baseline to beat before any nonlinear kernel is tried, and it is sensitive to scaling and offsets.

The polynomial kernel represents interactions up to a chosen degree. It captures multiplicative feature combinations, the degree controls complexity, the offset changes which lower-order terms are included, and its values can become numerically large.

The RBF kernel lets similarity decay with squared Euclidean distance. It creates a rich infinite-dimensional feature space, its bandwidth controls locality, it is the most sensitive of the three to feature scaling, and at extreme bandwidths its Gram matrix degenerates toward an identity-like or a nearly constant matrix.

The three families are not independent choices sitting side by side. At one end of its range, the third collapses into the first. Keerthi and Lin proved it in 2003: as σ²→∞ with C = C̃σ², the Gaussian-kernel SVM converges to the linear SVM with penalty C̃. A kernel family is a claim about which transformations should leave similarity alone. The claim is testable.

A kernel k(x,z) returns a scalar similarity with special mathematical structure. When k is valid in the usual sense, there exists a feature map φ such that k(x,z)=⟨φ(x),φ(z)⟩, possibly in a very large space. Algorithms that depend only on inner products can replace explicit dot products with kernel evaluations. The resulting model is linear in feature space while it may be nonlinear in the original inputs.

What that substitution buys has been scored on a public benchmark. Shankar and colleagues stated the comparison in a single sentence in 2020: “We construct a simple neural network architecture using only 3x3 convolutions, 2x2 average pooling, ReLU, and optimized with SGD and MSE loss that achieves 96% accuracy on CIFAR10, and whose corresponding compositional kernel achieves 90% accuracy.” The kernel learns no features at all. It only compares examples, and it lands within a few points of the network it corresponds to. In the small-data regime the same paper reports that “compositional kernels outperform NTKs and neural networks outperform both kernel methods”.

A different construction shows the same gap. A depth-11 convolutional neural tangent kernel with global average pooling reached 77.43% on CIFAR-10, against 82.92% for the matching finite CNN. Arora and colleagues reported both numbers in 2019, and call the kernel result “a significant new benchmark for the performance of a pure kernel-based method on CIFAR-10”. A benchmark set, and still trailing.

The kernel trick saves feature construction, not all computation. Training still depends on a Gram matrix whose size grows with the number of examples.

For training points x₁,…,xₙ, the Gram matrix K has entries Kᵢⱼ=k(xᵢ,xⱼ). If k is an inner product kernel, then cᵀKc=||Σᵢcᵢφ(xᵢ)||²≥0 for every coefficient vector c. That is the positive semidefinite property, and it is what allows K to behave like inner products among feature vectors.

The condition is old enough to carry a name. James Mercer set out the theory of functions of positive type in 1909, and practitioners still speak of Mercer kernels. The condition above is his.

An arbitrary symmetric similarity matrix may fail this test. Small negative eigenvalues can arise from floating-point error or approximations. Large negative structure indicates that the similarity is not an ordinary Hilbert-space kernel. That is not a hypothetical about badly chosen functions. Chen and colleagues assembled eight real similarity datasets in 2009 — among them 213 proteins in four classes (72/72/39/30) compared by sequence alignment, 204 Amazon books by 47 authors, 945 NIST faces of 139 people, 241 patrol-unit members, and 435 Congressional voting records. Their statement of the problem is flat: “Similarity functions may be asymmetric and fail to satisfy the other mathematical properties required for metrics or inner products”.

What practitioners do about it is a small catalogue of repairs, applied to the spectrum before any kernel algorithm sees the matrix. “Spectrum clip makes S PSD by clipping all the negative eigenvalues to zero”, and “any indefinite similarity matrix can be made PSD by shifting its spectrum by the absolute value of its minimum eigenvalue”. Flipping the sign of the negative eigenvalues is the third. Each repair changes the geometry. Each is a modeling decision rather than a numerical cleanup.

The same situation holds for structured data, and Oglic and Gärtner named the part that makes it dangerous in 2019: “Such functions are typically not positive definite and it is often well beyond the expertise of practitioners to verify this condition.” Their own work is motivated by “problems with structured representations (e.g., graphs, strings, time-series)”. The check is cheap. Skipping it is what costs.

Consider an RBF kernel k(x,z)=exp(−||x−z||²/(2σ²)). Both ends of the bandwidth range were worked out analytically by Keerthi and Lin in 2003. The scikit-learn documentation states the same two failures operationally, on its RBF SVM parameters example page: “If gamma is too large, the radius of the area of influence of the support vectors only includes the support vector itself and no amount of regularization with C will be able to prevent overfitting. When gamma is very small, the model is too constrained and cannot capture the complexity or “shape” of the data.”

Treat the kernel as a representation choice with testable invariances.

1. Define useful similarity. State which transformations should preserve or reduce similarity. This is domain work, not mathematics: sequence alignment for proteins, co-authorship for books and pairwise ratings for faces gave Chen and colleagues eight different answers across eight datasets.

2. Standardize the inputs. Align distance scales with the task before evaluating kernels. On svmguide1 that one step moved default-parameter accuracy from 66.925% to 96.15%, and the LIBSVM guide puts it ahead of parameter selection for exactly that reason.

3. Verify kernel structure. Check symmetry and positive semidefinite Gram behavior. Decide in advance which repair — clip, flip or shift — you will apply if the spectrum comes back indefinite, because each of the three changes the geometry differently.

4. Tune jointly. Select kernel parameters and regularization under leak-free validation. Keerthi and Lin's two limits are limits in σ and C together, and the empirical picture matches: the good models lie on a diagonal in (C, γ), so a search that fixes one parameter and sweeps the other can miss them entirely.

5. Inspect scalability and neighbors. Review concrete similar pairs, memory cost, and approximation error. Prefer a method whose error is bounded, such as the Nyström construction Drineas and Mahoney analyzed, over a shortcut whose only measured property is its speed.

The feature map may remain implicit throughout the computation.

1. Original input x. Examples begin in a space where the desired boundary may be nonlinear.

2. Feature map φ(x). A conceptual transformation creates coordinates where linear comparison is useful; for the RBF kernel that space is infinite-dimensional and is never written down.

3. Kernel evaluation. Compute inner products k(x,z) without necessarily constructing φ.

4. Gram matrix K. Store pairwise kernel values for the training examples. This is the step with a price tag. Shankar and colleagues built theirs over CIFAR-10 and CIFAR-100 (60,000 images of 32×32×3) and MNIST (70,000 images of 28×28), “creating a total complexity of Õ(N2D2)”. They spell out what enlarging the training set does to it: “if one wants to perform 100 augmentations per example, then the final kernel matrix will be 10,000 times larger, and solving the prediction problem may be one million times slower”. The neural tangent kernel carries a matching count: “To compute the CNTK matrix corresponding to a CNN with GAP that has L convolution layers and one fully-connected layer on n samples, the time complexity is O(n2P2Q2L)”. Sixty thousand images and roughly a thousand GPU hours pass before a single prediction is made.

5. Kernel predictor. Express predictions through weighted similarities to training examples.