kernel_methods

Kernel Methods and SVMs

Definition

Kernel methods use a kernel function to implicitly map inputs into a high-dimensional (possibly infinite) feature space, allowing linear algorithms to learn non-linear decision boundaries. Support Vector Machines (SVMs) are the most prominent kernel method.

Intuition

In the original feature space, the data may not be linearly separable. Mapping to a higher-dimensional space can make it separable. The kernel trick avoids explicitly computing this mapping — it computes inner products in the high-dimensional space directly from the original inputs. SVMs then find the maximum-margin hyperplane in that space.

Formal Description

Hard-Margin SVM (Linearly Separable)

Find the hyperplane ${\mathbf{w}}^{\top }\mathbf{x}+b=0$ with maximum margin $2/\Vert \mathbf{w}\Vert$:

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\text{s.t.}{y}_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)\ge 1\forall i$$

Dual problem (via Lagrangian):

$$\underset{\mathbf{\alpha }}{\max }\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{\top }{\mathbf{x}}_j$$ $$\text{s.t.}\sum _i{\alpha }_i{y}_i=0,{\alpha }_i\ge 0$$

Support vectors: training points with ${\alpha }_i>0$ (on the margin boundaries). All other ${\alpha }_i=0$.

Prediction: $\hat{y}=\mathrm{sign}\left({\sum }_i{\alpha }_i{y}_i{\mathbf{x}}_i^{\top }\mathbf{x}+b\right)$

Soft-Margin SVM (C-SVM)

Introduces slack variables ${\xi }_i\ge 0$ to allow margin violations:

$$\underset{\mathbf{w},b,\mathbf{\xi }}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _i{\xi }_i\text{s.t.}{y}_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

$C>0$ controls the trade-off: large $C$ → low tolerance for misclassifications → narrower margin; small $C$ → wide margin, more misclassifications.

Dual with box constraints: $0\le {\alpha }_i\le C$.

The Kernel Trick

Replace ${\mathbf{x}}_i^{\top }{\mathbf{x}}_j$ with a kernel function $k({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$:

$$\hat{y}=\mathrm{sign}\left(\sum _i{\alpha }_i{y}_{i}k({\mathbf{x}}_i,\mathbf{x})+b\right)$$

Common kernels:

Kernel	Formula	Properties
Linear	${\mathbf{x}}_i^{\top }{\mathbf{x}}_j$	No mapping; fast
Polynomial	$(\gamma {\mathbf{x}}_i^{\top }{\mathbf{x}}_j+r{)}^d$	Degree-$d$ interactions
RBF (Gaussian)	$\exp (-\gamma \Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2)$	Infinite-dimensional; most popular
Sigmoid	$\tanh (\gamma {\mathbf{x}}_i^{\top }{\mathbf{x}}_j+r)$	Similar to single-layer NN

Mercer’s condition: a symmetric function $k$ is a valid kernel iff its Gram matrix $K_{ij}=k({\mathbf{x}}_i,{\mathbf{x}}_j)$ is positive semidefinite for any finite sample.

RBF kernel: the bandwidth $\gamma =1/(2{\sigma }^2)$ controls the smoothness of the decision boundary. Large $\gamma$ → narrow Gaussians → complex boundary; small $\gamma$ → smooth boundary.

SVR (Support Vector Regression)

$\epsilon$-insensitive loss: ignore residuals $<\epsilon$; penalise larger residuals linearly. Dual formulation analogous to SVM.

Kernel Ridge Regression

Closed-form kernel regression: $\hat{f}(\mathbf{x})={\mathbf{k}}^{\top }(K+\lambda I{)}^{-1}\mathbf{y}$, where $K_{ij}=k({\mathbf{x}}_i,{\mathbf{x}}_j)$ and ${\mathbf{k}}_i=k({\mathbf{x}}_i,\mathbf{x})$. Equivalent to ridge regression in the RKHS.

Applications

• SVMs were dominant in text classification, image recognition, and bioinformatics before deep learning.
• Kernel methods remain useful for small datasets or specialised kernels (e.g., string kernels for sequences, graph kernels).
• SVM classifiers are a good baseline when the dataset fits in memory and has < ~10k samples.

Trade-offs

Aspect	SVM	Neural Network
Small data	✅ Works well	❌ May overfit
Large data	❌ $O(n^2)$ kernel matrix	✅ Scalable with SGD
Interpretability	Moderate (support vectors)	Low
Kernel choice	Requires domain knowledge	Learned end-to-end

Links

• Lagrangian and Constrained Optimization (SVM dual)
• Convex Optimization (QP)
• Linear Models (linear kernel = linear SVM)
• Regularization (C parameter)