Author: Eiko

Time: 2025-02-17 10:58:26 - 2025-02-17 10:58:26 (UTC)

In this course, we talk about how to use RKHS, reporducing kernel Hilbert space, to do machine learning.

Write down a positive definite kernel, and these kernels will be served as building blocks.

Positive definite Kernels

Definition(Positive Definite Kernels). Let $X\ne \varnothing$ be any set, $k:X\times X\to \mathbb{R}$ is called a positive definite kernel if

• $k$ is symmetric $k(x,y)=k(y,x)$

• $k$ is positive semi-definite, which means, for any $n\in \mathbb{N}$, $x_1,\dots ,x_n\in X$, ${\alpha }_i\in \mathbb{R}$, we have

  $$\sum _{i,j}{\alpha }_i{\alpha }_{j}k(x_i,x_j)\ge 0$$

  This is equivalent to say the matrix $(k(x_i,x_j){)}_{i,j}$ is positive semi-definite.

You can also think we have defined a symmetric positive definite bilinear form, an inner product on the vector space ${\mathbb{R}}^X$ with distinguished basis $X$.

Main Example: Square-Exponential

$$k(x,y)=\exp (-\frac{\parallel x-y{\parallel }^2}{2{\sigma }^2})$$

is a positive definite kernel.

Remarks

• Intuition: Solutions $k(x,y)$ encode the similarity between $x$ and $y$.

• $$\int \int k(x,y)f(x)f(y)dxdy\ge 0.$$

• $k(x,y)\ge 0$ does not mean $k$ is positive definite.

Further Examples Of Positive Definite Kernels

$$k(x,y)=\exp \left(\frac{|x-y{|}^p}{{\sigma }^p}\right)$$

It is positive definite for $p\in [1,2]$.

Polynomial kernels:

$$k(x,y)=(x^{T}y+c{)}^m,x,y\in {\mathbb{R}}^d,c>0,m\in \mathbb{N}.$$

Sums And Products

Given two positive definite kernels $k_1,k_2:X\times X\to \mathbb{R}$, then also

$$\begin{array}{rl}(k_1+k_2)(x,y)& :=k_1(x,y)+k_2(x,y)\\ k_1{k}_2(x,y)& :=k_1(x,y)\cdot k_2(x,y)\end{array}$$

Scaling: $f:X\to \mathbb{R}$ and $k:X\times X\to \mathbb{R}$ positive definite, then

$$k_f(x,y):=f(x)f(y)k(x,y)$$

will also be positive definite.

Reproducing Kernel Hilbert Spaces (RKHS)

$${\mathcal{H}}_K=\{\text{limit of linear combinations of functions of the form }k(\cdot ,x)\}$$

Construction

Step 1. Fix a positive definite kernel $k:X\times X\to \mathbb{R}$.

$$\begin{array}{rl}{\mathcal{H}}_K^{\circ }& =\mathbb{R}\{k(x,\cdot ):x\in X\}\\ & =\underset{x\in X}{⨁}\mathbb{R}k(x,\cdot )\\ & =\{f=\sum _{i=1}^n{c}_{i}k(x_i,\cdot ):n\in \mathbb{N},c_i\in \mathbb{R},x_i\in X\}\end{array}$$

Step 2. Construct an inner product $⟨\cdot ,\cdot {⟩}_K$ on ${\mathcal{H}}_K$, demand that

$$f(x)=⟨f,k(x,\cdot ){⟩}_K,f\in {\mathcal{H}}_K^{\circ }.$$

This is called the reproducing property. The point of this property is that it makes computing an inner product on an infinite dimensional space very easy, just a number.

Reproducing property determines inner product on ${\mathcal{H}}_K^{\circ }$.

$$f=\sum a_{i}k(x_i,\cdot ),g=\sum b_{j}k(y_j,\cdot )$$

$$⟨f,g{⟩}_{{\mathcal{H}}_K}=\sum _{i,j}{a}_i{b}_{j}k(x_i,y_j)$$

Define the RKHS norm as $\parallel f{\parallel }_{{\mathcal{H}}_K}=\sqrt{⟨f,f{⟩}_{{\mathcal{H}}_K}}$.

Lemma. The pairing $⟨\cdot ,\cdot {⟩}_{{\mathcal{H}}_K}$ is indeed an inner product on ${\mathcal{H}}_K^{\circ }$.

$$\sum a_i{a}_{j}k(x_i,x_j)\ge 0,\mathrm{\forall }{a}_i\in \mathbb{R},x_i\in X.$$

$$⟨f,f{⟩}_{{\mathcal{H}}_K}=0\Rightarrow f=0.$$

Proof. For $x\in X$,

$$\begin{array}{rl}|f(x){|}^2& =|⟨f,k(x,\cdot )⟩{|}^2\\ & \le \parallel f{\parallel }_{{\mathcal{H}}_K}^2\parallel k(x,\cdot ){\parallel }_{{\mathcal{H}}_K}^2\end{array}$$

This means if $\parallel f{\parallel }_{{\mathcal{H}}_K}=0$, then $f(x)=0$ for all $x\in X$, RKHS norm controls function values.

Step 3. Taking Completion

Take ${\mathcal{H}}_K=\overline{{\mathcal{H}}_K^{\circ }}$, the completion of ${\mathcal{H}}_K^{\circ }$ with respect to the norm $\parallel \cdot {\parallel }_{{\mathcal{H}}_K}$.

Remark. The function space inherent properties from the kernels.

• $k$ is bounded $\iff \mathrm{\forall }f\in {\mathcal{H}}_K$, $\parallel f{\parallel }_{{\mathcal{H}}_K}<\mathrm{\infty }$.

• $k$ is bounded continuous $\iff$ $\parallel \cdot {\parallel }_{{\mathcal{H}}_K}$ is bounded continuous.

Gaussian RKHS For Different Widths

Let ${\sigma }_2>{\sigma }_1>0$, consider the two spaces ${\mathcal{H}}_{K_{{\sigma }_2}}\subset {\mathcal{H}}_{K_{{\sigma }_1}}$.

Remark.

• Computing RKHS norm for any given function is difficult because you need to write them as linear combinations of $k(x,\cdot )$.

• This integral is not the RKHS norm, in general

  $$\int \int f(x)k(x,y)f(y)\mathrm{d}x\mathrm{d}y\ne \parallel f{\parallel }_{{\mathcal{H}}_K}^2.$$

Function Evaluations, Interpretation Of RKHS Norm

If $f,g$ are close in ${\mathcal{H}}_K$, then they are close point-wise.

$$|f(x)-g(x)|\le C_x\parallel f-g{\parallel }_{{\mathcal{H}}_K}.$$

In other words, ${\delta }_x:{\mathcal{H}}_K\to \mathbb{R},f\mapsto f(x)$ is bounded continuous.

Let’s Look At A Counter Example

• $\parallel f{\parallel }_{L^2(0,1)}^2={\int }_0^{1}f(x{)}^2\mathrm{d}x$, this norm does not have the above property! Because you can move the function value at a local region without changing much of the norm. A practical example is to take $q_n=x^n$.

• In any RKHS, function evaluations are continuous. Any Hilbert space with continuous function evaluations is an RKHS. For example Sobolev spaces where the derivatives are controlled by norm

  $$\parallel f{\parallel }_{W^1}=\int {|f(x)|}^2+{|f^{\prime }(x)|}^2\mathrm{d}x$$

  are RKHS.