时间戳

首页 > 技术文章 > 再生核Hilbert空间（RKHS）

再生核Hilbert空间（RKHS）

zhangcn 2020-07-12 18:04 原文

在支持向量机SVM中，通常使用核函数将样本输入空间转化为再生核Hilbert空间（Reproducing kernel Hilbert space，RKHS），提高算法处理非线性分类问题的性能。相比于Hilbert空间，RKHS有着很多优秀的性质。下面从RKHS的定义、RKHS刻画、RKHS与Hilbert空间关系等三个部分展开工作。

RKHS的定义

定义1和定义3给出了再生核Hilbert空间（Reproducing kernel Hilbert space， RKHS）的定义。定理2证明了定义1与定义3的等价性。

定义1 (RKHS定义）。设\(\mathcal{H}\)是一个由定义在非空集合\(\mathcal{X}\)上函数\(f:\mathcal{X}\mapsto \mathbb{K}\)构成的Hilbert函数空间，若函数\(k:\mathcal{X}\times \mathcal{X}\mapsto \mathbb{R}\)满足：

  • \(∀x∈\mathcal{X} ,k(⋅,x)∈\mathbb{K}\)
  • \(∀x∈\mathcal{X},∀f∈\mathcal{H},\left <f,k(⋅,x) \right >_\mathcal{H}=f(x)\)，（重构属性）
  • 特别地，对于\(∀x,y∈\mathcal{X}\)，有\(k(x,y)=\left <k(⋅,x),k(⋅,y) \right >_\mathcal{H}\)。

其中\(<⋅,⋅>_\mathcal{H}\)是内积。则\(k\)称为\(\mathcal{H}\)的再生核函数，\(\mathcal{H}\)为再生核Hilbert空间（RKHS）。

定义2（求值泛函定义，Evaluation Functional）。设\(\mathcal{H}\)是一个由定义在非空集合\(\mathcal{X}\)上函数\(f:\mathcal{X}↦\mathbb{K}\)构成的Hilbert函数空间，对于一个固定的\(x∈\mathcal{X}\)，定义映射\(δ_x:\mathcal{H}↦\mathbb{K}\)满足\(δ_x f=f(x)\)，则\(δ_x\)是在\(x\)点的求值泛函。

显然，求值泛函\(δ_x\)是一个线性泛函，因为对于\(∀f,g∈\mathcal{H}\)和\(∀α,β∈\mathbb{K}\)，有

\[δ_x (αf+βg)=(αf+βg)(x)=αf(x)+βg(x)=αδ_x (f)+βδ_x (g) \]

一个重要的数学问题是\(δ_x\)是否是连续线性泛函（是否是有界线性泛函）。下面从求值泛函的有界性质来重新考察再生核Hilbert空间。

定义3（RKHS定义）。\(\mathcal{H}\)是再生核Hilbert空间当且仅当对于\(∀x∈\mathcal{X}\)，求值泛函\(δ_x\)是有界的，即存在一个与\(x\)有关的常量\(λ_x≥0\)满足对\(∀f∈\mathcal{H}\),有

\[|f(x)|=|δ_x f|≤λ_x ‖f‖_\mathcal{H} \]

定理1（Riesz表示定理）。在一个Hilbert空间\(\mathcal{H}\)中，对于任意的一个有界线性算子\(A\)均存在\(g_A∈\mathcal{H}\)，使得\(Af=\left <f,g_A \right>_H,∀f∈\mathcal{H}\)。

下面定理证明了再生核Hilbert空间的两种定义之间等价性。

定理2。\(\mathcal{H}\)是一个再生核Hilbert空间（其求值泛函\(δ_x\)是有界的）当且仅当\(\mathcal{H}\)有一个再生核。

证明：充分性：如果\(\mathcal{H}\)有一个再生核\(k(⋅,⋅)\)，下面证明\(δ_x\)是一个有界线性泛函。

\[|δ_x (f)|=|f(x)| \]

\[=|\left <f,k(⋅,x) \right >_\mathcal{H} | \]

\[≤‖k(⋅,x)‖_\mathcal{H} ‖f‖_\mathcal{H} \]

\[=\sqrt{(k(x,x))} ‖f‖_\mathcal{H} \]

其中，第二行是\(k\)的重构属性，第三行是Schwarz不等式。因此，当\(λ_x=\sqrt{(k(x,x))}\)时\(|δ_x (f)|≤λ_x ‖f‖_H\)，所以\(δ_x\)是一个有界线性泛函。

必要性：记\(\mathcal{H}'\)是\(\mathcal{H}\)的对偶空间，假设\(δ_x∈\mathcal{H}'\)且\(δ_x:\mathcal{H}↦\mathbb{K}\)是一个有界求值泛函，有\(δ_x f=f(x)\)。Riesz表示定理表明，\(δ_x\)是有界的，则存在\(g_{δ_x}∈\mathcal{H}\)使得，

\[δ_x f=\left <f,g_{δ_x} \right>_\mathcal{H}, ∀f∈\mathcal{H} \]

因为\(\mathcal{H}\)是一个Hilbert空间，所以存在一个等距共轭线性同构\(I:\mathcal{H}'↦\mathcal{H}\)使得\(δ_x\)映射成\(g_{δ_x}\)，即有\(Iδ_x=g_{δ_x}\)。定义\(\mathcal{H}\)上函数\(k\)为

\[k(x,x'):=\left <δ_x , δ_{x'} \right>_{\mathcal{H}'} \]

下面我们验证\(k\)是\(\mathcal{H}\)上的再生核。
1. 对\(∀x'∈\mathcal{X}\)，我们有\(k(⋅,x')=Iδ_{x'}∈\mathcal{H}\)。因为

\[k(x,x' )=\left <δ_x ,δ_x' \right>_{\mathcal{H}'} =^{(a)}<Iδ_x , Iδ_{x'} >_\mathcal{H} =^{(b)} δ_x (Iδ_{x' } ) =^{(c)}Iδ_{x' } (x) \]

其中，\((a)\)使用了共轭线性同构，\((b)\)使用了\(Iδ_x=g_{δ_x}\)，\((c)\)是求值泛函的定义。
2. \(k\)满足重构属性，即

\[f(x' )=δ_{x'} f=\left <f,Iδ_{x' } \right>_\mathcal{H}=<f,k(⋅,x') >_\mathcal{H} \]

因此，\(k\)是\(\mathcal{H}\)上的再生核。

再生Hilbert空间的定义比较抽象，该如何刻画一个具体的RKHS呢？

RKHS的刻画

定义4（正定核函数）。设\(\mathcal{X}\)是一个非空集。对于函数\(\mathcal{X}\times \mathcal{X}↦\mathbb{K}\)，若存在一个\(\mathbb{K}\)-Hilbert空间\(\mathcal{H}\)和一个映射\(ϕ:\mathcal{X}↦\mathcal{H}\)，满足对\(∀x,y∈\mathcal{H}\)，有

\[k(x,y)=< ϕ(x),ϕ(y)>_\mathcal{H} \]

则\(k\)为正定核函数。

引理1。正定核函数一定是正定的。

证明：对于任意的\(∀n≥1\)，\(∀(a_1,⋯,a_n )∈\mathbb{C}^n\),\(∀(x_1,⋯,x_n )∈\mathcal{X}^n\)，总有

\[\sum_{i=1}^n\sum_{j=1}^n a_i \bar a_j k(x_i,x_j)=\sum_{i=1}^n \sum_{j=1}^n \left <a_i ϕ(x_i ),a_j ϕ(x_j ) \right>=\left \|\sum_{i=1}^n a_i ϕ(x_i ) \right \|^2≥0 \]

所以正定核函数\(k\)是正定的。

引理2。再生核函数一定是正定核函数。

证明：对RKHS \(\mathcal{H}\)中再生核\(k\)，满足\(k(x,y)=<k(⋅,x),k(⋅,y) >_\mathcal{H}\)，取\(ϕ:x↦k(⋅,x)\)，即证。

正定核函数是否也是再生核函数呢？下面的Moore-Aronszajn定理回答了这个问题。

定理3（Moore-Aronszajn定理）。每一个正定核k都与唯一一个再生核Hilbert空间相对应。

该定理证明比较复杂，参考文献[1]中第4节。

虽然正定核与再生核相互确定，但对于正定核\(k\)，对象\(x\)的映射向量\(ϕ(x)\)并不是唯一的；即给定不同的正交基空间，映射向量\(ϕ(x)\)在不同基下的坐标是不一致的，但是其内积的性质在不同基下是保持一致的。当\(ϕ(x)= k(⋅,x)\)时，\(ϕ(x)\)被称作\(x\)的典型映射向量。
在实际的计算过程中， \(ϕ(x)\)的维数往往是无穷的，而且很难去计算它的具体的值。我们往往采用核技巧的方法来避免去直接处理\(ϕ(x)\)。我们直接用\(k(x_i,x_j)\)直接替代公式中的\(\left <ϕ(x_i ),ϕ(x_j)\right >\)，然后得到算法的非线性版本。这种方法简化了计算量，而且十分容易去处理。在实际计算过程中我们只需要选择合适的正定核函数。

RKHS与Hilbert空间的关系

RKHS是一个Hilbert函数空间，Hilbert空间范围更广。毫无疑问，RKHS是Hilbert空间的一部分。但是，Hilbert空间未必是RKHS。

RKHS的一个关键属性就是求值泛函的性质。在一般的Hilbert空间下，求值泛函并不是连续的（有界的）。这意味着当依范数f_n↦f时，不能推断出\(δ_x f_n↦δ_x f\)。比如，在\(L_2 (0,1)\)空间（\(L2\)也是一个Hilbert空间）中，取\(f(x)=0\)和\(f_n (x)=\sqrt{n} I(x<1/n^2)\)。有

\[\left \|f_n-f\right \|=\left (\int_0^1\left |\sqrt{n} I(x<\frac{1}{n^2} )-0 \right |^2 dx\right)^{\frac{1}{2}} =\left (∫_0^{\frac{1}{n^2}}n dx \right)^{\frac{1}{2}}=\frac{1}{\sqrt{n}}↦0,n↦∞ \]

而\(δ_0 f_n=\sqrt{n}\)显然不会收敛到\(δ_0 f=0\)，当\(n↦∞\)。

因此，直观地说，Hilbert空间中包含了很多非光滑的函数。而在RKHS中，所有函数都依点态收敛\(f_n (x)↦f(x)\)，即\(δ_x f_n↦δ_x f\)。这意味着RKHS中的函数相比于Hilbert空间中的函数都是well-behaved，对于\(∀f,f_n∈\mathcal{H}\)当依范数\(f_n↦f\)时，总有\(δ_x f_n=\left <f_n,k(⋅,x)\right >↦\left <f,k(⋅,x)\right >=f(x)=δ_x f\)成立。我们有如下定理。

定理4。如果RKHS中的两个函数依范数收敛，则它们必然在每一个点都收敛。即如果\(\lim_{n→∞}⁡\|f_n-f\|_\mathcal{H}=0\) ，则有\(\lim_{n→∞} f_n (x)=f(x),∀x∈X\)。

证明：对于\(∀x∈\mathcal{X}\)，

\[|f_n (x)-f(x)|=|δ_x f_n-δ_x f|≤‖δ_x ‖ ‖f_n-f‖_\mathcal{H} \]

其中\(‖δ_x ‖\)是求值泛函的范数，因为求值泛函是有界的，所以\(‖δ_x ‖<∞\)。

综上分析，Hilbert空间和RKHS最本质的区别是Cauchy列收敛条件。Hilbert空间是完备的，所以Hilbert空间中的所有Cauchy列依范数收敛，即假设\(\{f_n \}_{n=1}^∞\)是Hilbert空间中的Cauchy列，则对任意的\(ε>0\)，存在自然数\(N\)，使得\(∀i,j>N\)时，有\(‖f_i-f_j ‖<ε\)。而在RKHS中，条件要求更严格，要求所有的Cauchy列依点态收敛，即\(∀x∈\mathcal{X}\)，式子\(|f_i (x)-f_j (x)|<ε\)都成立。

[1] Dino Sejdinovic, Arthur Gretton. What is an RKHS?[EB/OL]. http://www.gatsby.ucl.ac.uk/~gretton/coursefiles/lecture1_whatIsRKHS.pdf,2012-02-14.

推荐阅读