Kernel Function

Definition

Kernel Function

Let $\mathcal{X}$ be an input space. A kernel function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ is a function that computes the inner product of two data points after they have been mapped into a higher-dimensional Hilbert Space (feature space) $\mathcal{H}$ via a map $\varphi$.

This allows for computing similarities in high dimensions directly from low-dimensional inputs, avoiding the explicit computation of $\varphi (x)$ (the kernel trick).

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

Properties

For a function $k(\cdot ,\cdot )$ to be a valid kernel, it must satisfy the following properties.

Symmetry

The kernel function must be symmetric:

$$\forall x,x^{\prime }\in \mathcal{X}:k(x,x^{\prime })=k(x^{\prime },x)$$

Note that this reflects the symmetry of the inner product: $⟨a,b⟩=⟨b,a⟩$.

Positive Semi-Definiteness

This is the crucial condition that guarantees the geometry of the feature space $\mathcal{H}$ is valid (i.e., no negative lengths).

For any finite set of data points $\{x_1,\dots ,x_n\}\subset \mathcal{X}$, the corresponding $n\times n$ Kernel matrix must be a positive semi-definite.