Kernel trick

Also known as: kernel method

On this page 7

The kernel trick is a technique in machine learning that replaces every inner product in an algorithm with a kernel function, so the algorithm behaves as if the data had been mapped into a high-dimensional feature space without ever computing that mapping. It turns linear methods such as the support vector machine, ridge regression and principal component analysis into nonlinear learners while keeping their convex, well-understood optimization.

Algorithms that use it are often called kernel methods. The idea rests on a simple observation: many learning algorithms touch the data only through dot products between pairs of examples, and those dot products can be computed directly in the implicit feature space.

How the kernel trick replaces explicit feature maps

The kernel trick works because a valid kernel k(x, z) equals an inner product of two mapped vectors, written as the dot product of φ(x) and φ(z), where φ is the feature map. If an algorithm can be rewritten so that the training examples appear only inside such products, the map φ never has to be evaluated.

A classic illustration is the degree-2 polynomial kernel on two-dimensional inputs. Squaring the dot product of x and z produces exactly the inner product of vectors containing x1², x2² and √2·x1x2, a three-dimensional feature space reached with one multiplication and one square. For higher degrees and more input dimensions the explicit space grows combinatorially, while the kernel cost stays linear in the input dimension.

The mathematical guarantee comes from Mercer’s theorem and the theory of reproducing kernel Hilbert spaces (RKHS). A symmetric function is a valid kernel when every Gram matrix it produces on any finite set of points is positive semidefinite. The representer theorem then states that the optimal solution of a regularized loss over the RKHS can be written as a weighted sum of kernels centered on the training points, which is why kernel models store coefficients per training example.

The following table traces the steps that turn a linear algorithm into its kernelized form.

StepWhat happensResult
Dual formulationRewrite the model in terms of training examplesWeights become per-example coefficients
Inner product isolationConfirm data appears only in dot productsAlgorithm is kernelizable
Kernel substitutionReplace each dot product with k(x, z)Implicit nonlinear feature space
Gram matrix computationEvaluate k on all training pairsAn n × n matrix of similarities
PredictionSum kernel values against stored examplesNonlinear decision function
Steps in kernelizing a linear algorithm

Common kernel functions and their parameters

The choice of kernel defines the shape of the feature space and therefore the family of functions the model can represent. Each kernel encodes an assumption about which inputs should count as similar, and its hyperparameters control how flexible the resulting decision boundary becomes.

KernelFormula sketchKey parametersTypical use
Linear kernelDot product of x and zNoneHigh-dimensional sparse text
Polynomial kernel(γ·x·z + c) raised to degree dDegree d, offset c, scale γFeature interactions of fixed order
RBF (Gaussian) kernelexp(−γ·squared distance)Width γDefault for dense numeric data
Laplacian kernelexp(−γ·L1 distance)Width γData with sharp local changes
Sigmoid kerneltanh(γ·x·z + c)Scale γ, offset cHistorical neural network analogy
String and graph kernelsCounts of shared substructuresSubstring length, decaySequences, molecules, graphs
Widely used kernels in classic machine learning

The radial basis function kernel deserves special attention because its implicit feature space is infinite-dimensional, which no explicit feature map could ever reproduce. A large γ value makes each training point influence only a tiny neighborhood and invites overfitting, while a small γ smooths the boundary toward a nearly linear one. The sigmoid kernel is not positive semidefinite for all parameter values, so it can break the convexity that makes kernel methods reliable.

Kernel methods compared with explicit features and neural networks

Kernel methods sit between hand-built feature engineering and learned representations. They offer a rich nonlinear model with a convex training problem, yet their cost grows with the number of training examples rather than with the number of features.

ApproachFeature spaceTraining costMain limitation
Explicit polynomial featuresBuilt and storedGrows with feature countCombinatorial explosion
Kernel trickImplicit, possibly infiniteRoughly O(n²) to O(n³)Poor scaling to millions of rows
Random Fourier featuresApproximate, explicitLinear in nApproximation error
Tree ensemblesLearned axis-aligned splitsAbout n log n per treePiecewise constant output
Neural networksLearned by gradient descentLinear in n per epochNonconvex, data hungry
Ways to obtain a nonlinear model

Within the Topic, the kernel trick is most closely tied to the support vector machine, but it also powers kernel ridge regression, kernel PCA, spectral clustering on kernel similarity graphs and the Gaussian process, whose covariance function is itself a kernel. A Gaussian process and kernel ridge regression produce the same mean prediction under matching assumptions; the Gaussian process adds a calibrated predictive variance.

Choosing and tuning a kernel in practice

Kernel selection should follow the structure of the data, and tuning should always use cross-validation. Because distance-based kernels compare raw coordinates, feature scaling before training is mandatory; one unscaled feature measured in thousands can dominate every similarity value.

SituationRecommended choiceReason
Many sparse features, such as textLinear kernelData is often already separable
Few dense numeric featuresRBF kernel with tuned γ and CFlexible smooth boundaries
Known interaction orderPolynomial kernel of low degreeMatches the expected structure
Sequences or molecular graphsDomain-specific structured kernelCaptures shared substructures
More than about 100,000 rowsKernel approximation or linear modelGram matrix becomes too large
Decision guide for kernel selection

A sound tuning procedure searches γ and the regularization constant C on a logarithmic grid, for example powers of ten from 10⁻³ to 10³, or uses Bayesian optimization for larger budgets. The two parameters interact strongly, so tuning one while fixing the other usually misses the best region.

Limitations and common misconceptions

The central drawback is quadratic memory and roughly cubic time in the number of training examples. A Gram matrix for 100,000 points holds ten billion entries, which is why large-scale work relies on the Nyström method, random Fourier features or switching to linear models.

  • Misconception: kernels add features to the dataset. No new columns are created; only pairwise similarities are computed.
  • Misconception: any similarity function is a kernel. Without positive semidefiniteness, the optimization can lose convexity and a unique solution.
  • Interpretability suffers, because weights live in an implicit space that cannot be inspected feature by feature.
  • Prediction cost grows with the number of stored support vectors or training points.
  • The curse of dimensionality still applies, since distance-based kernels lose contrast when many irrelevant features are present.

Stripped to the essentials

Some patterns cannot be separated with a straight line. Imagine red dots in the middle of a sheet of paper and blue dots in a ring around them. No single line divides them, but if the paper is lifted into a bowl shape, a flat plane can slice between the two groups.

The kernel trick is a shortcut for that lifting. Instead of actually reshaping the data, the algorithm uses a formula that tells it how similar two points would be after the lift. The key takeaway is that a simple, reliable learning method can draw curved boundaries without paying the cost of building the larger space.

Where it is applied

A quality engineer at an electronics plant wants to flag defective solder joints from twelve measurements taken by an inspection camera, such as joint height, reflectivity and fillet angle. The dataset holds about 8,000 labeled joints, and defective joints form curved clusters that a linear classifier separates poorly, reaching roughly 84 percent accuracy.

The engineer standardizes the twelve features, trains a support vector machine with an RBF kernel, and tunes γ and C by five-fold cross-validation on a logarithmic grid. With 8,000 rows the Gram matrix fits comfortably in memory and training takes seconds. The tuned model reaches about 95 percent accuracy on held-out joints, and because the training problem is convex, retraining each month on new data gives stable, reproducible results without the run-to-run variation of a neural network.