理论误国,调参兴邦!

0%

再生核希尔伯特空间(RKHS)漫谈(一):定义

这次系列文章主要进行RKHS相关的理论推导,以便对机器学习中的核方法和核技巧有更深的理解。

我们熟悉的SVM的推导中包含了一些数学技巧,包括最优化理论中的对偶问题,以及初学者很难理解的Reproducing Kernel Hilbert Space (RKHS)。其实RKHS是泛函分析中的一个研究对象,它的难点主要在一些泛函分析的前置知识,只要理解了泛函的一些基本概念和定理,再来看RKHS就会容易很多。

SVM中的Kernel Trick

SVM中的核技巧,就是在样本线性不可分的情况下,将样本映射到一个更高维的空间,也许在更高维空间,样本是线性可分的。

在更高维空间中,可以理解成我们给其添加了更多特征,做了更多特征交叉和非线性组合,期望这些新增加的特征可以帮助我们进行分类。在《统计学习理论》中,第10章有说过,尽管特征空间维度很高,如果样本数量足够多,我们可以以一个小的误差期望来构造分类超平面,这个超平面的泛化能力是不错的。

原SVM的超平面:

映射到高维的超平面:

$\Phi$将样本映射到高维空间。得到的分类器为:

看似我们需要指定一个具体的$\Phi$,其实不然,我们不需要知道它的具体形式,在求解参数和分类器的过程中,它不用单独计算,并且总是以内积的形式出现。

如果$\Phi$很复杂、并且映射后的维度很高,此内积的计算复杂度会很大。假设有一个函数$k(x_i,x)=\Phi(\mathrm{x}_i)^\top \Phi(\mathrm{x})$,我们就可以直接计算映射后高维空间下的内积。

那么,这个函数要满足什么条件,才能有这样的性质呢?恰好,RKHS理论提供了这样一个途径。

我第一次读到SVM的核技巧时,最大的疑问是,$\Phi$究竟将样本点映射到什么了空间中?映射成了高维空间的什么元素?映射后的元素究竟表示什么含义?或者还有确切的含义吗?亦或者,我们需要理解高维空间的意义吗?

定义

线性空间

元素满足以下几个条件的集合$L$,叫做线性空间或者向量空间:

并且对于任意一数$\alpha$和任意一元素$x\in L$,可确定$\alpha x\in L$。
后面我们讨论的希尔伯特空间是线性空间

Inner Product

内积(inner product),即满足以下几个条件的映射$\langle x,y\rangle$ :

  1. 对称性(Symmetry): $\langle x,y \rangle=\langle y,x\rangle$
  2. 双线性(Bilinearity):$\langle \alpha x+ \beta w,y\rangle=\alpha \langle x,y\rangle+\beta \langle w,y\rangle$
  3. 正定性(Positive definiteness):$\langle x,x\rangle \geqslant 0$ 并且仅当$x=0$时取到0

内积的形式是可以大胆定义的,只需要你定义的映射可以满足内积的三个条件即可。

Hilbert Space

希尔伯特空间是具有内积定义的完备空间。空间的完备性是指,空间内的所有柯西列均收敛在该空间内。比如有理数不是完备的,{1,1.2,1.21…},这个柯西列极限是$\sqrt{2}$,不在有理数空间内。而实数域R是完备的。

如果想证明一个空间是Hilbert space,需要在空间定义内积,并且证明它的完备性。
有限维的完备内积空间叫做欧几里得空间,也就是我们常见的$\mathbb{R}^n$

Kernel

k:$\mathcal{X\times X \rightarrow}\mathbb{R}$,如果满足以下条件,k是kernel:

  1. k是对称的,$k(x,y)=k(y,x)$
  2. k是正定的,是指对任意的$x_i \in \mathcal{X}, i=1,2,…,m$ , $k(x,y)$对应的Gram矩阵:$K_{ij}=k(x_i,x_j)$是半正定的。

Reproducing Kernel Hilbert Space

设有一集合$\mathcal{X}$,以及一希尔伯特空间$\mathcal{H}$,它的元素是$\mathcal{X}$上的函数$f:\mathcal{X}\rightarrow\mathbb{R}$,我们称$\mathcal{H}$为再生核希尔伯特空间(Reproducing Kernel Hilbert Space):如果存在一个函数$k:\mathcal{X}\rightarrow\mathbb{R}$,并且满足:

因此,我们可以很容易推出:

这里函数$k(\cdot,x)$和$f(\cdot)$里面的点记号,表示一个变量。只不过有时候$x$表示固定的一个数,$\cdot$通常表示变量。换一种写法意义一样:$k(x,y)$,固定某一$x$,而$y$取任意值,表示这是一个关于$y$的一元函数。为了方便起见,我们就用$k(\cdot,x)$表示固定某一$x$的一元函数。

这样来看,如果我们找到了一个核函数,就能生成一个希尔伯特空间,并且该核函数就等于在该空间内两个元素(函数)做内积。是的,在这个高维空间里面,元素是函数,你能想象你把一个用户画像的特征点映射成了一个函数么,太抽象了。后面经过推导,我相信可以呈现出一个稍微具象化的东西。

参考文献

[1] 函数论与泛函分析初步

[2] Function Space Methods in System Theory