再生核希尔伯特空间和核方法

前言

之前遇到过很多次再生核希尔伯特空间，但一直没有搞懂，最近读论文又遇到了，就花了些时间进行了了解，并在此基础上对核方法加深了理解。

1 再生核希尔伯特空间的理解

本节参照/p/29527729。

1.1 函数与无穷向量

本人数学基础比较差，该文章中的第一句“每一个函数f都可以看做一个无限维的向量”就让我想了一些时间，最后大概是理解了，举个例子：

定义f=exf=e^{x}f=ex，对f进行泰勒展开可得：

f(x)=1+x+12!x2+13!x3+...f(x)=1+x+\frac{1}{2!}x^{2}+\frac{1}{3!}x^{3}+...f(x)=1+x+2!1​x2+3!1​x3+...

令向量α=(1,1,12!,13!,...)T，β=(1,x,x2,x3...)T\alpha =(1,1,\frac{1}{2!},\frac{1}{3!},...)^{T}，\beta =(1,x,x^{2},x^{3}...)^{T}α=(1,1,2!1​,3!1​,...)T，β=(1,x,x2,x3...)T，那么f(x)=αTβf(x)=\alpha ^{T}\betaf(x)=αTβ，此时我们可以把f(x)看做是无穷维向量α\alphaα，每输入一个x，可以获取对应的向量β\betaβ，然后做内积，就得到了f(x)的值；这样我们就将函数和一个无穷维向量联系起来了。

但对于一个n阶多项式函数，如f(x)=anxn+an−1xn−1+...+a1x1+a0f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x^{1}+a_{0}f(x)=an​xn+an−1​xn−1+...+a1​x1+a0​，按上面的方法似乎只能对应一个n+1维向量：(a0,a1,...,an−1,an)T(a_{0},a_{1},...,a_{n-1},a_{n})^{T}(a0​,a1​,...,an−1​,an​)T。

我们换一种方法，对于一个在连续区间[a,b]的连续函数f(x)，把区间中所有数看做一个向量，即α=(a,...,b)T\alpha =(a,...,b)^{T}α=(a,...,b)T，显然α\alphaα是无穷维的向量，那么我们把这个区间的所有数在f(x)作用下的值当成一个向量β=(f(a),...,f(b))T\beta =(f(a),...,f(b))^{T}β=(f(a),...,f(b))T，那么β\betaβ也是无穷维的，我们可以把β\betaβ看做是f(x)；此时对于任意一个c∈[a,b]c\in [a,b]c∈[a,b]（为了下面方便表述，我们令a<c<b），我们按上面的思路将c表述为向量α=(0,...,1,...,0)T\alpha =(0,...,1,...,0)^{T}α=(0,...,1,...,0)T（只有在c的位置为1，其他位置都是0），那么f(c)=βTαf(c)=\beta ^{T}\alphaf(c)=βTα。下面的篇幅中，我都按这种理解建立的无穷维向量进行展开。

上面是我对“每一个函数f都可以看做一个无限维的向量”这句话的理解，感觉因该对f有一个限制，就是定义在连续区间，且在该区间内f不存在第二类间断点。如果有理解错误，还请大家指正。

1.2 核函数

1.2.1 核函数的性质

通常所说的核函数K(x,y)就是正定核函数，满足：

（1）正定性：∫∫f(x)K(x,y)f(y)dxdy≥0\int \int f(x)K(x,y)f(y)dxdy\geq 0∫∫f(x)K(x,y)f(y)dxdy≥0

（2）对称性：K(x,y)=K(y,x)K(x,y)=K(y,x)K(x,y)=K(y,x)

Mercer定理给出，如果K(x,y)是有效核函数，当且仅当对于训练样本，其对应的核函数矩阵是对称半正定的。

1.2.2 核函数的矩阵理解

如果一维函数ψ\psiψ可以看成一个无穷维向量，那么我们可以把核函数K看作是行数和列数均为无穷的矩阵，这个矩阵的每个元素可以看做由相应的x值和y值确定的核函数值，每一行（列）均可看做核函数一个变量固定而形成的单变量函数。既然K是一个矩阵，那么我们可以对其进行特征值分解，因为矩阵是对称的，且是无穷维，那么就有无数个特征向量，每个向量是无穷维的，且特征向量之间是正交的。这里的特征向量也称为K的特征函数（下面的讨论中，可以把无穷维向量和函数等价理解），我们把这组特征函数表示为(ψ0,ψ1,...)(\psi _{0},\psi _{1},...)(ψ0​,ψ1​,...)，其中每个ψi\psi _{i}ψi​是一个无穷维的列向量，对应的特征值为λi\lambda _{i}λi​。我们令Ψ=(ψ0,ψ1,...)\Psi =(\psi _{0},\psi _{1},...)Ψ=(ψ0​,ψ1​,...)，Λ\LambdaΛ为对角线为特征值的对角矩阵，那么K=ΨΛΨTK=\Psi \Lambda \Psi^{T}K=ΨΛΨT（这里结合线性代数中的对称矩阵特征值分解进行理解），K(x,y)=∑i=0∞λiψi(x)ψi(y)K(x,y)=\sum_{i=0}^{\infty }\lambda _{i}\psi _{i}(x)\psi _{i}(y)K(x,y)=∑i=0∞​λi​ψi​(x)ψi​(y)。

注意，这里要将ψ\psiψ和ψ(x)\psi (x)ψ(x)进行区分，ψ\psiψ是一个列向量，是一个函数，而ψ(x)\psi (x)ψ(x)则表明是ψ\psiψ的第x个元素，是一个值；这可能会与我们之前的印象ψ(x)\psi(x)ψ(x)是一个函数不同，我们这里按矩阵进行理解，同样的K(x,y)也是一个值，是矩阵K的第x行第y列的值。该节下面部分也是这种理解。

1.2.3 再生核希尔伯特空间

上面提到核函数K有一组正交的特征函数，我们对这组特征函数进行改造得到(λ0ψ0,λ1ψ1,...)(\sqrt{\lambda _{0}}\psi _{0},\sqrt{\lambda _{1}}\psi _{1},...)(λ0​​ψ0​,λ1​​ψ1​,...)，并把改造的特征函数当做一组正交基来构建空间HHH。

线性空间

这个空间的任意一个函数f均可以由这组正交基来表示：f=∑i=0∞fiλiψif=\sum_{i=0}^{\infty }f_{i}\sqrt{\lambda _{i}}\psi _{i}f=∑i=0∞​fi​λi​​ψi​，此时f在该空间中的表示为f=(f0,f1,...)f=(f_{0},f_{1},...)f=(f0​,f1​,...)，易得该空间关于加法和数乘运算是封闭的，所以空间HHH是线性空间。

内积空间

我们在该空间中定义内积，f=(f0,f1,...)f=(f_{0},f_{1},...)f=(f0​,f1​,...)，g=(g0,g1,...)g=(g_{0},g_{1},...)g=(g0​,g1​,...)，那么我们定义f和g在该空间的内积：f.g=<f,g>=∑i=0∞figif.g=<f,g>=\sum_{i=0}^{\infty }f_{i}g_{i}f.g=<f,g>=∑i=0∞​fi​gi​，此时空间HHH为内积空间。

希尔伯特空间

上面我们定义了内积，然后我们在内积的基础上引入范数：∣∣f∣∣=f.f||f||=\sqrt{f.f}∣∣f∣∣=f.f​，此时该空间是一个赋范向量空间。根据泛函分析理论，对于不完备的赋范向量空间，一定可以使之完备化，从而得到完备的赋范向量空间（该句来自李航老师的《统计学习方法》），我们这里假设空间HHH已经完备化了，那么内积空间+完备就是希尔伯特空间。

再生性

现在距离再生核希尔伯特空间只剩一个再生性了。

前面我们知道K(x,y)=∑i=0∞λiψi(x)ψi(y)K(x,y)=\sum_{i=0}^{\infty }\lambda _{i}\psi _{i}(x)\psi _{i}(y)K(x,y)=∑i=0∞​λi​ψi​(x)ψi​(y)，那么：

K(x,.)=∑i=0∞λiψi(x)ψiK(x,.)=\sum_{i=0}^{\infty }\lambda _{i}\psi _{i}(x)\psi _{i}K(x,.)=∑i=0∞​λi​ψi​(x)ψi​，在该空间对应的向量是：(λ0ψ0(x),λ1ψ1(x),...)(\sqrt {\lambda _{0}}\psi _{0}(x),\sqrt {\lambda _{1}}\psi _{1}(x),...)(λ0​​ψ0​(x),λ1​​ψ1​(x),...)；

K(.,y)=∑i=0∞λiψiψi(y)K(.,y)=\sum_{i=0}^{\infty }\lambda _{i}\psi _{i}\psi _{i}(y)K(.,y)=∑i=0∞​λi​ψi​ψi​(y)，在该空间对应的向量是：(λ0ψ0(y),λ1ψ1(y),...)(\sqrt {\lambda _{0}}\psi _{0}(y),\sqrt {\lambda _{1}}\psi _{1}(y),...)(λ0​​ψ0​(y),λ1​​ψ1​(y),...)。

上文提到对于任意的f=∑i=0∞fiλiψif=\sum_{i=0}^{\infty }f_{i}\sqrt{\lambda _{i}}\psi _{i}f=∑i=0∞​fi​λi​​ψi​，在该空间对应的向量是：(f0,f1,...)(f_{0},f_{1},...)(f0​,f1​,...)；

那么我们可以得到下面两个结论：

（1）取K(x,.)和f的内积：

K(x,.).f=(λ0ψ0(x),λ1ψ1(x),...)(f0,f1,...)T=∑i=0∞fiλiψi(x)=f(x)K(x,.).f=(\sqrt {\lambda _{0}}\psi _{0}(x),\sqrt {\lambda _{1}}\psi _{1}(x),...)(f_{0},f_{1},...)^{T}=\sum_{i=0}^{\infty }f_{i}\sqrt{\lambda _{i}}\psi _{i}(x)=f(x)K(x,.).f=(λ0​​ψ0​(x),λ1​​ψ1​(x),...)(f0​,f1​,...)T=∑i=0∞​fi​λi​​ψi​(x)=f(x)

（2）取K(x,.)和K(.,y)的内积：

K(x,.).K(.,y)=(λ0ψ0(x),λ1ψ1(x),...)(λ0ψ0(y),λ1ψ1(y),...)T=∑i=0∞λiψi(x)ψi(y)=K(x,y)K(x,.).K(.,y)=(\sqrt {\lambda _{0}}\psi _{0}(x),\sqrt {\lambda _{1}}\psi _{1}(x),...)(\sqrt {\lambda _{0}}\psi _{0}(y),\sqrt {\lambda _{1}}\psi _{1}(y),...)^{T}=\sum_{i=0}^{\infty }\lambda _{i}\psi _{i}(x)\psi _{i}(y)=K(x,y)K(x,.).K(.,y)=(λ0​​ψ0​(x),λ1​​ψ1​(x),...)(λ0​​ψ0​(y),λ1​​ψ1​(y),...)T=∑i=0∞​λi​ψi​(x)ψi​(y)=K(x,y)

这两条就是核函数的再生性，此时可以得出HHH是再生核希尔伯特空间。

一般来说，一个核函数确定了一个再生核希尔伯特空间。

2 核方法

很多人都知道核方法，定义函数ϕ\phiϕ，该函数将有限维的向量映射到高维，甚至是无穷维，但在高维上对ϕ(x)\phi (x)ϕ(x)和ϕ(y)\phi (y)ϕ(y)做内积，运算量较大，这时候就引入了核函数K(x,y)，核函数满足K(x,y)=<ϕ(x),ϕ(y)>K(x,y)=<\phi (x),\phi (y)>K(x,y)=<ϕ(x),ϕ(y)>，这样就避免在高维空间上求内积，甚至不用显式定义函数ϕ\phiϕ。

2.1 再生核映射

上面定义的ϕ(x)=K(x,.)\phi (x)=K(x,.)ϕ(x)=K(x,.)，我们将ϕ\phiϕ称为再生核映射，该映射将x映射到上面提到的再生核希尔伯特空间。上面提到ϕ\phiϕ将x映射到无穷维，那么我们该如何理解这个说法。

按矩阵来理解二元函数，那么ϕ(x)\phi (x)ϕ(x)对应核函数的第x行，那么ϕ(x)\phi (x)ϕ(x)在该空间中是一个无穷维向量，因此ϕ\phiϕ将x映射到无穷维。

从函数的角度来讲，K(x,y)是一个二元函数，当给定x后，K(x,.)（换个写法就是K(x0,y)）就是关于y的单变量函数，而单变量函数对应无穷维向量。

2.2 经验核映射

该部分参照/p/1bbc5cef55cb

对于输入X=(x1,x2,...,xn)X=(x_{1},x_{2},...,x_{n})X=(x1​,x2​,...,xn​)，我们应用核技巧会得到一个核矩阵K（注意和之前按矩阵理解核函数时的矩阵K作区分），该矩阵为n*n，Kij=<ϕ(xi),ϕ(xj)>K_{ij}=<\phi (x_{i}),\phi (x_{j})>Kij​=<ϕ(xi​),ϕ(xj​)>.

我们定义经验核映射ϕ\phiϕ：ϕ(xi)=K−1/2Ki\phi (x_{i})=K^{-1/2}K_{i}ϕ(xi​)=K−1/2Ki​，此时ϕ(xi)Tϕ(xj)=KiTK−1Kj\phi (x_{i})^{T}\phi (x_{j})=K_{i}^{T}K^{-1}K_{j}ϕ(xi​)Tϕ(xj​)=KiT​K−1Kj​，其中KiK_{i}Ki​为K的第i列.

结语：本文中有些符号的理解会和常用的不太一样，还有一些符号用的有点乱，例如讲再生核希尔伯特空间时的矩阵K和经验核映射的矩阵K是不一样的，阅读时注意结合具体情境。