Kernel Function

machine-learning linear-algebra statistics

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}}$

Necessary Conditions

Symmetry: For any $\mathbf{x},{\mathbf{x}}^{\prime }\in \mathcal{X}$, the kernel must satisfy $k(\mathbf{x},{\mathbf{x}}^{\prime })=k({\mathbf{x}}^{\prime },\mathbf{x})$, reflecting the commutativity of the inner product.

Positive Semi-Definiteness (PSD): For any finite set of points $\{x_1,\dots ,x_n\}$, the corresponding Gram matrix $K$ must be positive semi-definite ($c^{\top }Kc\ge 0$ for all $c\in {\mathbb{R}}^n$). This ensures that the mapping corresponds to a valid geometry in $\mathcal{H}$.

Algebraic Closure Properties

Valid kernel functions are closed under several operations, allowing for the construction of complex kernels from simpler components while maintaining positive semi-definiteness.

Summation: If $k_1$ and $k_2$ are valid kernels, then their sum $k(\mathbf{x},{\mathbf{x}}^{\prime })=k_1(\mathbf{x},{\mathbf{x}}^{\prime })+k_2(\mathbf{x},{\mathbf{x}}^{\prime })$ is also a valid kernel. This corresponds to concatenating the underlying feature maps.

Product: The pointwise product $k(\mathbf{x},{\mathbf{x}}^{\prime })=k_1(\mathbf{x},{\mathbf{x}}^{\prime })\cdot k_2(\mathbf{x},{\mathbf{x}}^{\prime })$ is a valid kernel, corresponding to the tensor product of the feature maps.

Scalar Multiplication: For any constant $c>0$, $k(\mathbf{x},{\mathbf{x}}^{\prime })=c\cdot k_1(\mathbf{x},{\mathbf{x}}^{\prime })$ is a valid kernel.