Kernel Method

The kernel method lets linear algorithms (like SVM) operate in very high (even infinite-dimensional) feature spaces without ever explicitly computing the feature map. Many linear algorithms depend on the data only through dot products, and a kernel $k(x,x^{\prime })$ can compute $⟨\varphi (x),\varphi (x^{\prime })⟩$ in time independent of the feature space dimension.

What's the kernel trick buying us?

Nonlinear decision boundaries at linear-algorithm prices: skip the explicit high-dimensional lift and still get its expressive power.

Motivation: Nonlinear Decision Boundaries

Linear methods fail when the true boundary is curved (e.g., a circle, or XOR). Lift the data into a higher-dimensional space where it becomes linearly separable.

XOR

The map $\varphi (x)=(x_1,x_2,x_1{x}_2)$ makes XOR separable: the product coordinate captures the interaction.

Feature Maps

A feature map sends $x\in {\mathbf{R}}^d$ to $\varphi (x)\in {\mathbf{R}}^D$ where $D\gg d$ (possibly $D=\infty$).

Quadratic feature map (example): for $x=(x_1,x_2)$, take $\varphi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$ Now a linear classifier in $\varphi$-space captures quadratic boundaries.

The issue: computing $\varphi (x)$ explicitly for high-order polynomial or Gaussian feature maps is expensive or infeasible.

The Kernel Trick

A function $k(x,x^{\prime })$ is a kernel if there exists some feature map $\varphi$ such that $k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$

Crucially, $\varphi$ may be expensive (or infinite-dimensional) but $k$ may be cheap to evaluate.

Quadratic kernel example: $k(x,x^{\prime })=⟨x,x^{\prime }{⟩}^2$. $⟨x,x^{\prime }{⟩}^2={\left({\sum }_i{x}_i{x}_i^{\prime }\right)}^2={\sum }_{i,j}{x}_i{x}_j{x}_i^{\prime }{x}_j^{\prime }=⟨\varphi (x),\varphi (x^{\prime })⟩$

where:

• $\varphi (x{)}_{ij}=x_i{x}_j$ is the quadratic feature map

Computing the kernel takes $O(d)$ time instead of $O(d^2)$ for the explicit map.

Intuition

You never materialize the high-dimensional feature vector. The kernel evaluates the inner product in the implicit space directly, so you get a decision boundary curved in the original space without paying the cost of explicit features. For the RBF kernel, $\varphi$ is literally infinite-dimensional, and yet $k(x,x^{\prime })$ is a one-line exponential. Any algorithm that touches data only through dot products gets this upgrade for free.

Common Kernels

• Linear: $k(x,x^{\prime })=⟨x,x^{\prime }⟩$ (no lifting)
• Polynomial (degree $p$): $k(x,x^{\prime })=(⟨x,x^{\prime }⟩+c{)}^p$
• Gaussian / Radial Basis Function (RBF): $k(x,x^{\prime })=\exp (-\Vert x-x^{\prime }{\Vert }_2^2/(2{\sigma }^2))$, corresponds to an infinite-dimensional feature map

The RBF kernel reads as a similarity score: 1 when $x=x^{\prime }$, decaying smoothly to 0 as they move apart. $\sigma$ is the bandwidth, how quickly similarity drops. Small $\sigma$ means every point is “an island” (overfits), large $\sigma$ smooths everything toward linear.

Valid Kernels: Mercer’s Condition

A function $k$ is a valid kernel iff, for any finite dataset $\{x_1,\dots ,x_n\}$, the Gram matrix $K\in {\mathbf{R}}^{n\times n}$ with $K_{ij}=k(x_i,x_j)$ is

1. Symmetric: $K_{ij}=K_{ji}$
2. Positive semidefinite (PSD): $v^{\top }Kv\ge 0$ for all $v\in {\mathbf{R}}^n$

PSD-ness follows from writing $K=\Phi {\Phi }^{\top }$ where $\Phi$ has rows $\varphi (x_i)$.

Kernelized SVM

Recall the SVM dual depends only on $⟨x_i,x_j⟩$: ${\min }_{0\le \alpha \le C}\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j⟨x_i,x_j⟩-{\sum }_i{\alpha }_i$

Replace $⟨x_i,x_j⟩$ with $k(x_i,x_j)$: ${\min }_{0\le \alpha \le C}\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}k(x_i,x_j)-{\sum }_i{\alpha }_i$

Predicting a new point $x$: we don’t need $\varphi (x)$ explicitly: $\hat{y}(x)=\text{sign}\left({\sum }_i{\alpha }_i{y}_{i}k(x_i,x)+b\right)$

Complexity

• Linear-kernel SVM: $O(nd)$ training, $O(d)$ test time
• General-kernel SVM: $O(n^{2}d)$ to build the Gram matrix at training, $O(nd)$ test time (loop over support vectors)

So kernels aren’t free: there’s a dataset-size penalty. Worth it when $d$ is small or moderate and the true boundary is nonlinear.

From CS480 lec6.

Related

• Support Vector Machine (canonical kernel application)
• Kernel Density Estimation
• CS480