Theory of Reproducing Kernels

Authors: Nachman Aronszajn
Published: 1950
Journal: Transactions of the American Mathematical Society
Link: PDF

Summary

This foundational paper introduces the theory of Reproducing Kernel Hilbert Spaces (RKHS), establishing the mathematical framework that underlies modern kernel methods in machine learning.

Key Contributions

1. Definition of RKHS

Aronszajn defines a Reproducing Kernel Hilbert Space as a Hilbert space $\mathcal{H}$ of functions on a set $X$ such that for every $x \in X$, the evaluation functional $\delta_x: f \mapsto f(x)$ is continuous.

2. The Moore-Aronszajn Theorem

The paper proves that:

• Every positive definite kernel $K: X \times X \to \mathbb{R}$ uniquely determines an RKHS
• Every RKHS has a unique reproducing kernel
• The reproducing property: $f(x) = \langle f, K(\cdot, x) \rangle_{\mathcal{H}}$

3. Construction of RKHS

Given a positive definite kernel $K$, the RKHS can be constructed as the completion of: $\mathcal{H}_0 = \left\{ \sum_{i=1}^n \alpha_i K(\cdot, x_i) : n \in \mathbb{N}, \alpha_i \in \mathbb{R}, x_i \in X \right\}$

with inner product: $\left\langle \sum_i \alpha_i K(\cdot, x_i), \sum_j \beta_j K(\cdot, y_j) \right\rangle = \sum_{i,j} \alpha_i \beta_j K(x_i, y_j)$

Mathematical Framework

Positive Definite Kernels

A kernel $K: X \times X \to \mathbb{R}$ is positive definite if for any $n \in \mathbb{N}$, any $x_1, \ldots, x_n \in X$, and any $\alpha_1, \ldots, \alpha_n \in \mathbb{R}$: $\sum_{i,j=1}^n \alpha_i \alpha_j K(x_i, x_j) \geq 0$

Feature Map Interpretation

Every positive definite kernel admits a feature map $\phi: X \to \mathcal{H}$ such that: $K(x, y) = \langle \phi(x), \phi(y) \rangle_{\mathcal{H}}$

where $\phi(x) = K(\cdot, x)$.

Impact on Machine Learning

This paper provides the theoretical foundation for:

1. Support Vector Machines - The kernel trick relies on RKHS theory
2. Gaussian Processes - GP regression uses RKHS function spaces
3. Kernel PCA - Nonlinear dimensionality reduction
4. Regularization Theory - RKHS norms provide natural regularization

Key Theorems

Theorem (Moore-Aronszajn)

For every positive definite kernel $K$ on $X \times X$, there exists a unique Hilbert space $\mathcal{H}$ of functions on $X$ for which $K$ is a reproducing kernel.

Theorem (Representer Theorem - implied)

Solutions to regularized problems in RKHS lie in the finite-dimensional subspace spanned by kernel evaluations at the training points.

Citation

@article{aronszajn1950theory,
  title={Theory of reproducing kernels},
  author={Aronszajn, Nachman},
  journal={Transactions of the American Mathematical Society},
  volume={68},
  number={3},
  pages={337--404},
  year={1950}
}

Further Reading

• Berlinet, A., & Thomas-Agnan, C. (2004). Reproducing Kernel Hilbert Spaces in Probability and Statistics
• Steinwart, I., & Christmann, A. (2008). Support Vector Machines