上一章讨论了RKHS相关的定义，我们知道了只要找到一个正定的核函数(positive define kernel)，那么一定有这样一个希尔伯特空间，里面的所有元素可以用$f(x)=\langle f(\cdot),k(\cdot,x)\rangle , \forall f\in \mathcal{H}$“再生”出来，利用这个性质可以让我们用核函数代替内积。

现在我们准备深入RKHS看看。首先，我们有两条路可以证明核函数可以构成一个RKHS。

Mercer’s Theorem
Moore-Aronszajn’s Theorem

这一章来证明第一个命题:Mecer’s Theorem。我们上一篇博客给出了核函数的概念，Mecer’s Theorem比核函数的现代定义出现得要早，因此Mercer理论中的核函数定义稍有不同，显得更为严格一些。Moore-Aronszajn’s Theorem是后来发展的，现代用的比较多，它的核函数定义更为宽松，更为一般。

Mercer’s Theorem:

设 $k$ 是$[a,b]\times[a,b]$上的连续、对称的实变函数，假设对所有的$f\in L_2([a,b])$，都有：

$\int_a^b\int_a^bk(t,s)f(s)f(t)ds\ dt \ge 0. \tag{1}$

设 $K$ 是以核函数 $k$ 为基础的积分算子，即:

$(Kf)(t)=\int_a^bk(t,s)f(s)ds \tag{2}$

设$\{\phi_n\},\{\lambda_n\}$是算子$K$的特征向量和特征函数，那么对$[a,b]$上所有的 $t$ 和 $s$ ，都有：

$k(t,s)=\sum_j\lambda_j\phi_j(t)\phi_j(s). \tag{3}$

这个级数在$[a,b]\times[a,b]$上绝对收敛并且一致收敛。

Mercer’s Theorem的证明

在Mecer的原论文[3]中，这个证明十分复杂。感兴趣的读者可以去看看这篇1908年的数学论文。我没有耐心看完，当时找了很多资料，包括文献[4]，他们的证明大概分为两个步骤:

1.证明$\sum_j\lambda_j\phi^2_j(s)$一致收敛至$k(s,s)$

2.证明$\sum_j\lambda_j\phi_j(t)\phi_j(s)$一致收敛至$k(s,t)$

第一个步骤所有资料包括原文都比较简明易懂，复杂的地方主要在第二步，原文花了很长的篇幅、构造了一些中间算子，才证明了它一致收敛，这个过程我看得很吃力，没有完全看懂。而文献[4]只是提了一下用Schwarz不等式就可以证明2，但没有详细说明。

这个坑困扰了我一两周时间，我能查到的所有博客和StackExchange均没有给出令人信服的证明，比如这个Uniform convergence in Mercer Theorem for bounded kernels；它们几乎都是证明到第一步就停了，第二步和我尝试利用Schwarz不等式得到的结论一样：

$\sum_j|\lambda_j\phi_j(t)\phi_j(s)|\le k(s,s)^{1/2}k(t,t)^{1/2} \tag{4}$

这个不等式只能说明左边的级数是收敛的，无法进一步说明它收敛到$k(t,s)$。

直到我发现了Basic Class of Linear Operator[1]这本书，里面用Schwarz不等式详细证明了第二步，我觉得证明的很巧妙，有必要在这分享一下：

设

$\tilde{k}(t,s)=\sum_j\lambda_j\phi_j(t)\phi_j(s) \tag{5}$

显然，当固定t时，$\tilde{k}(t,s)$是关于s的连续函数，并且有：

$\int_a^b[k(t,s)-\tilde{k}(t,s)]f(s) \ ds=(Kf)(t) -\sum_j\lambda_j\langle f,\phi_j \rangle\phi_j(t) \tag{6}$

注：$\int_a^b\tilde{k}(t,s)f(s)ds=\int_a^b\sum_j\lambda_j\phi_j(t)\phi_j(s)f(s)ds=\sum_j\lambda_j\phi_j(t)\int_a^b\phi_j(s)f(s)ds$

对于公式(6)，做如下讨论：

1.假设$f\in \mathbf{Ker}\ K=\mathbf{Im}\ K^{\perp}$ ，那么$Kf=0$；显然$\phi_j\in \mathbf{Im}\ K$，由正交补的定义可知，$\langle f,\phi_j \rangle=0$；那么公式(6)右边等于0

2.假设$f\in \mathbf{Ker} \ K^{\perp}=\mathbf{Im}\ K$，那么根据紧自伴算子谱理论有$f=\sum_i\alpha_i\phi_i$，带入公式(6)右边：

$\begin{aligned} (Kf)(t) -\sum_j\lambda_j\langle f,\phi_j \rangle\phi_j(t) =\\ \sum_i\alpha_i\lambda_i\phi_i(t) - \sum_j\lambda_j\langle \sum_i\alpha_i\phi_i,\phi_j \rangle\phi_j(t) =\\ \sum_i\alpha_i\lambda_i\phi_i(t) - \sum_j\lambda_j\sum_i\langle\alpha_i\phi_i,\phi_j \rangle\phi_j(t) =\\ \sum_i\alpha_i\lambda_i\phi_i(t) - \sum_j\lambda_j\alpha_j\phi_j(t) =0\\ \end{aligned}$

可见公式(6)右边仍然为0。
综合上述1、2两点可知，对于所有的$f\in \mathcal{H}=(\mathbf{Ker} \ K^{\perp}\oplus\mathbf{Ker} \ K)$，公式(6)右边等于0恒成立。再进行一些补充讨论（利用Dini’S Theorem）就能得出公式(3)是一致收敛的。

其实Mercer理论和它的证明都涉及到一个很重要的理论：算子的谱理论，尤其是紧自伴算子的谱理论。这个理论在之前讨论Laplacian的时候也起到了很重要的作用，这部分内容可以参考的资料很多，不再详述。

由Mercer理论看RKHS

从Mercer理论出发，我们可以推导出RKHS。

算子$K$是$\mathcal{H}$上的紧自伴算子，由谱理论可知，它的特征函数系$\{\phi_n\}$构成了一个标准正交系(Orthonormal System)，特别注意的是，正交系非正交基(Orhonormal basis)。正交基可以表示空间$\mathcal{H}$上的所有元素，但是正交系还不行。除非算子$K$同时是单射的，$\{\phi_n\}$才是$\mathcal{H}$的一个标准正交基[5]。Mercer理论中的积分算子$K$显然没有要求是单射的。

设

$\mathcal{H'} := \text{span}\{\sum_i\alpha_i\phi_i : \alpha_i \in \mathcal{l^2}\} \tag{7}$

仅通过上述条件，推不出$\mathcal{H’}$是希尔伯特空间，并且有$\mathcal{H’} \subseteq\mathcal{H}$。当且仅当$K$是紧自伴、单射算子时，$\mathcal{H’}=\mathcal{H}$。因此剩下的重要工作是，使用完备性定义证明$\mathcal{H’}$是完备的内积空间，即希尔伯特空间。这一段证明属于细活，这里不再详述。

在此基础之上，设

$f=\sum\alpha_j\phi_j \ \in \mathcal{H'} ,\ \ g=\sum\beta_j\phi_j \ \in \mathcal{H'} \tag{8}$

我们在$\mathcal{H’}$上定义内积:

$\langle f,g \rangle_{\mathcal{H'}}=\sum\frac{ \alpha_j\beta_j}{\lambda_j} \tag{9}$

由Mercer定理公式(3)，我们固定$s$:

$k(\cdot,s)=\sum_j\lambda_j\phi_j(s)\phi_j(\cdot) \tag{10}$

显然一元函数$k(\cdot,s)\in\mathcal{H’}$。那么根据我们定义的内积可得:

$\langle k(\cdot,t),k(\cdot,s)\rangle_{\mathcal{H'}}=\sum\frac{\lambda_j\phi(t)\cdot\lambda_j\phi(s)}{\lambda_j}=\sum\lambda_j\phi(t)\phi(s)=k(t,s)$

并且对于$\forall f(\cdot)=\sum\alpha_j\phi_j(\cdot)\in\mathcal{H’}$，都有（固定$s$）:

$\langle f(\cdot),k(\cdot,s)\rangle_{\mathcal{H'}}=\sum\frac{\alpha_j\lambda_j\phi(s)}{\lambda_j}=\sum\alpha_j\phi(s)=f(s)$

因此$\mathcal{H’}$是RKHS。然后核函数$k(t,s)$的确表示$\mathcal{H’}$上的内积。

应用到SVM上

回到SVM上，设$\{x_n\}$是样本点，我们希望能找到一个$\Phi(\cdot)$将$x_i$映射到希尔伯特空间（特征空间），并且在这个特征空间上，映射后的内积可以表示为:

$\langle \Phi(x_i),\Phi(x_j)\rangle_{\mathcal{H'}}=k(x_i,x_j)$

很明显，如果给定一个核函数$k(t,s)$，那么$\Phi(x)=k(\cdot,x)$就是我们要找的映射。有了这些认识，我们再来回答上一章中提出的问题。

特征映射$\Phi$将样本$x_i$映射到了特征空间$\mathcal{H’}$，根据公式(8)可知里面的元素均为函数，并且这些函数可以表示为一组函数的线性组合。因此，$\Phi(x_i)$将$x_i$映射为某一函数，特征空间$\mathcal{H’}$为函数空间,该空间的一组标准正交基是积分算子$K$的特征函数。特别的，如果$K$的特征函数系$\{\phi_n\}$是无穷的，那么特征空间$\mathcal{H’}$也就是无穷维特征空间。

另外，实际操作中，我们一般将$\Phi(x)=\{…,\lambda_j\phi_j(x),…,\lambda_n\phi_n(x)\}$，略去基函数，写成等价的坐标形式。

那么你应该对SVM的核技巧有具象化的了解了吧，非线性特征映射将样本映射到了一个函数空间，样本变成了一个个函数，这些函数可以写成关于基函数的坐标形式，他们的内积就是核函数。

遗憾的是，$\mathcal{H’}$里面的函数实际代表的含义很难解释，尤其是当$\mathcal{H’}$是无穷维的时候。也许和神经网络模型一样，很多时候不用过分追求可解释性，毕竟调参兴邦、理论误国，只要效果有了，你怎么解释都是对的。