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

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

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

SVM中的Kernel Trick

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

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

原SVM的超平面：

$$f(\mathrm{x})=\mathrm{w}^\top\mathrm{x}+b$$

映射到高维的超平面：

$$f(\mathrm{x})=\mathrm{w}^\top\Phi(\mathrm{x})+b$$

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

$$\begin{aligned} &f(\mathrm{x})=\sum_i^N \alpha_i y_i \mathrm{x}_i^\top \mathrm{x}+b \\ \rightarrow &f(\mathrm{x})=\sum_i^N \alpha_i y_i \Phi(\mathrm{x}_i)^\top \Phi(\mathrm{x})+b \end{aligned}$$

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

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

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

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

定义

线性空间

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

$$\begin{aligned} &1. \ \ \ \ x+y=y+x \\ &2. \ \ \ \ (\alpha+\beta)x=\alpha x+\beta x \\ &3. \ \ \ \ \alpha(x+y)=\alpha x+\alpha y \end{aligned}$$

并且对于任意一数$\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}$，并且满足：

$$f(x)=\langle f(\cdot),k(\cdot,x)\rangle , \forall f\in \mathcal{H}$$

且

$$\mathcal{H}=\overline{ \mathrm{span}\{k(\cdot,x):x\in\mathcal{X}\}}$$

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

$$k(x,y)=\langle k(\cdot,y),k(\cdot,x)\rangle$$

这里函数$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