Principle:Scikit learn Scikit learn Kernel Methods

Knowledge Sources	Scikit_learn Scikit-learn Docs
Domains	Supervised Learning, Non-Parametric Methods
Last Updated	2026-02-08 15:00 GMT

Overview

Kernel methods map data into high-dimensional feature spaces via kernel functions and perform linear algorithms in those spaces, enabling non-linear models with strong theoretical foundations.

Description

Kernel methods extend linear algorithms to handle non-linear relationships by implicitly operating in a high-dimensional (or even infinite-dimensional) feature space defined by a kernel function. The kernel trick avoids explicit computation of the high-dimensional feature vectors, instead computing inner products directly via the kernel function. This enables linear methods like ridge regression, PCA, and SVMs to learn non-linear patterns while retaining their theoretical properties. Kernel approximation and random projection methods provide scalable alternatives that explicitly construct approximate low-dimensional feature maps, enabling kernel-like performance with linear algorithms at reduced computational cost.

Usage

Use Kernel Ridge Regression when you want a non-linear regression model that combines the kernel trick with ridge regularization, particularly when exact kernel evaluation is feasible (small to moderate datasets). Use kernel approximation methods (Nystroem, Random Fourier Features) when the dataset is too large for exact kernel methods but you want to approximate kernel-based learning using explicit feature maps with linear models. Use random projection methods (Gaussian random projection, sparse random projection) when you need fast, data-independent dimensionality reduction that approximately preserves pairwise distances, as guaranteed by the Johnson-Lindenstrauss lemma.

Theoretical Basis

Kernel Trick: A kernel function $k(x,x^{\prime })$ computes the inner product in a feature space without explicit transformation:

$k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime }){⟩}_{{\mathscr{H}}}$

where $\varphi :{𝒳}\to {\mathscr{H}}$ maps inputs to a (potentially infinite-dimensional) Hilbert space. Mercer's theorem ensures that any positive semi-definite kernel corresponds to such a mapping.

Kernel Ridge Regression: Combines the kernel trick with ridge regression:

$\hat{f}(x)=k(x,X)(K+\alpha I{)}^{-1}y$

where $K_{ij}=k(x_i,x_j)$ is the kernel matrix and $\alpha$ is the regularization parameter. The dual formulation has complexity $O(n^3)$ for $n$ samples, independent of the (possibly infinite) feature space dimensionality.

Kernel Approximation: Explicit feature maps $\hat{\varphi }$ approximate the kernel:

$k(x,x^{\prime })\approx \hat{\varphi }(x{)}^T\hat{\varphi }(x^{\prime })$

Random Fourier Features (RBF Sampler): For shift-invariant kernels, Bochner's theorem guarantees:

$k(x-x^{\prime })=\int e^{i{\omega }^T(x-x^{\prime })}p(\omega )d\omega \approx \frac{1}{D}\sum _{j=1}^D\cos ({\omega }_j^{T}x+b_j)\cos ({\omega }_j^T{x}^{\prime }+b_j)$

where ${\omega }_j\sim p(\omega )$ and $b_j\sim \text{Uniform}(0,2\pi )$. For the RBF kernel, $p(\omega )={𝒩}(0,2\gamma I)$.

Nystroem Approximation: Approximates the kernel matrix using a subset of $m$ landmark points:

$K\approx C{W}^{-1}{C}^T$

where $C$ is the $n\times m$ kernel matrix between all points and the landmarks, and $W$ is the $m\times m$ kernel matrix among landmarks.

Random Projection: Projects data from ${\mathbb{ℝ}}^d$ to ${\mathbb{ℝ}}^k$ using a random matrix $R$:

$x^{\prime }=\frac{1}{\sqrt{k}}Rx$

The Johnson-Lindenstrauss Lemma guarantees that for $k=O({\epsilon }^{-2}\log n)$, pairwise distances are preserved within a factor of $(1\pm \epsilon )$ with high probability:

$(1-\epsilon )\Vert x_i-x_j{\Vert }^2\le \Vert {x_i}^{\prime }-{x_j}^{\prime }{\Vert }^2\le (1+\epsilon )\Vert x_i-x_j{\Vert }^2$

Gaussian random projection uses $R_{ij}\sim {𝒩}(0,1)$. Sparse random projection uses a sparse matrix with entries $\{-1,0,+1\}$ with appropriate probabilities, providing computational savings while maintaining the JL guarantee.

Related Pages

• Implementation:Scikit_learn_Scikit_learn_KernelRidge
• Implementation:Scikit_learn_Scikit_learn_KernelApproximation
• Implementation:Scikit_learn_Scikit_learn_RandomProjection