Kernel Method

machine-learning

Definition

Kernel Method

A kernel method is a general strategy used in machine learning to take learning algorithms that only work linearly (like the perceptron or the standard SVM) and upgrade them to solve non-linear problems efficiently.

If you can’t separate the data in its current space (the input space), map it into a higher-dimensional universe (the feature space), which is done via a feature map function $\varphi$:

$$x\stackrel{\text{map}}{⟶}\varphi (x)$$

The Curse of Dimensionality

If higher dimensional data leads to higher separability, why not map data to a billion dimensions, or even more?

The Curse of Dimensionality: Calculating the explicit transformation $x\mapsto \varphi (x)$ for every data point can be incredibly slow and memory-intensive. Sometimes the target space is even infinite-dimensional, making direct calculation impossible.

Definition

Curse of Dimensionality

The curse of dimensionality refers to various phenomena that arise when analysing and organising data in high-dimensional spaces that do not occur in low-dimensional settings. Formally, as the dimensionality $d$ increases, the volume of the space grows exponentially, causing the available data points to become sparse.

Link to original

Kernel Trick

Many linear learning algorithms don’t actually need to see the data points themselves. They only ever need to know the angles and distances between pairs of data points. This means that the algorithm only depends on the inner product between points.

Existence of a Feature Map

There exists a feature map $\varphi :\mathcal{X}\to \mathcal{H}$ from the instance space into a Hilbert space $\mathcal{H}$ such that:

$$\forall x,x^{\prime }\in \mathcal{X}:k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime }{)}_{\mathcal{H}}⟩$$

If we were to map the data to high dimensions, the algorithm would need the inner product in that new space:

$$⟨\varphi (x_i),\varphi (x_j)⟩$$

Definition

Kernel Function

A kernel function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ is a symmetric, positive semi-definite function that computes the inner product of two data points in a high-dimensional Hilbert space $\mathcal{H}$ without requiring the explicit computation of the feature mapping $\varphi :\mathcal{X}\to \mathcal{H}$. Formally:

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

Link to original