再生核方法-第一章 基本概念

再生核方法-第一章基本概念

闲居

2020年11月于西财宏远楼

再生核概述

在过去的二十年里，核方法相对其他方法（比如神经网络）快速流行起来，因为它具有可靠的理论支持。传统的机器学习和统计理论及算法集中在线性模型，现实世界中复杂的问题往往需要非线性模型才能建立数据中的相依性，和实现感兴趣对象的成功预测。再生核（没有特别说明，后面都简称为核）能帮助我们更好地捕获现实世界，它对应着一个特征空间（往往是高维空间）的内积。在特征空间中，我们的估计方法是线性的，而对原始空间而言却是非线性的估计方法。利用核追踪，我们从不需要在高维特征空间中计算任何东西。核方法具有算法实现简单和理论可靠的优点。

再生核

给定一组经验数据\(\{(x_i, y_i),i=1,\cdots,n\} \subset \mathcal{X} \times \mathcal{Y}\)，其中\(x_i\)为预测变量或协变量，\(y_i\)为响应变量或目标变量。我们这里对定义域\(\mathcal{X}\)无任何要求，只需它是一个非空集合。我们需要一个函数， \[k: \mathcal{X} \times \mathcal{X}\rightarrow R, (x,x')\rightarrow k(x,x')\] 满足对任意\(x,x' \in \mathcal{X}\)，都存在一个映射\(\Phi: \mathcal{X} \rightarrow \mathcal{H}\)，使得 \[K(x,x') = \langle \Phi(x), \Phi(x')\rangle_{\mathcal{H}}\tag{2.1}\] 成立，其中\(\mathcal{H}\)为一个内积空间,通常被称为特征空间，\(\Phi\)称为特征映射，相似性度量\(k\)被称为核。

问题1. $\Phi(x)$所在的空间$\mathcal{H}$与$k$生成的Hilbert空间是同一个空间吗？
答：它们可以是同一个空间，其中$H$称为自然特征空间。
注.线性空间是指定义了加法和数乘运算的非空集合；
内积空间是定义了内积的线性空间；
希尔伯特空间是指完备化的内积空间。

当\(\mathcal{H}\)为自然特征空间时，\(\Phi(x)=k(x,\cdot)\)。

正定核

\((2.1)\)式中所定义的核其实就是我们下面所要定义的正定核。

定义1（核矩阵）. 由 \[\begin{equation} \label{eq:Kmat} K = (k(x_i,x_j)) \end{equation}\] 生成的矩阵被称为Gram矩阵或核矩阵。

定义2（正定矩阵）.若\(\sum_{i,j}c_ic_jK_{ij}\geq 0\)对所有\(c_i\)都成立，则称\(K\)为正定的。若等式只在\(c_1=\cdots=c_n = 0\)时成立，则称\(K\)是严格正定的。 

注.这里的正定矩阵概念和矩阵分析中有点差异。
这里的“正定”对应矩阵分析中“半正定”的概念；
这里的“严格正定”对应于矩阵分析中“正定”的概念。

定义3（正定核）.若\(k\)对于任意\(n\in N,x_i\in \mathcal{X},i\in [n]\)（N 自然数集合），对应的核矩阵都是正定的，则\(k\)称为正定核；若对应的核矩阵是严格正定的，则\(k\)称为严格正定核。

证明： 步骤1： \((2.1)\)是正定核。对任意\(c_i,i\in [n]\)，有 \[\sum_{i,j}c_ic_j\langle \Phi(x_i), \Phi(x_j)\rangle = \langle \sum_i \Phi(x_i), \sum_j c_j\Phi(x_j)\rangle\geq 0.\] 由正定核定义得证。

步骤2： 正定核满足\((2.1)\)式。令\(\Phi(x)=k(x,\cdot)\)，由再生性可得 \[K(x,x') = \langle \Phi(x), \Phi(x')\rangle_{\mathcal{H}}.\] \(\mathcal{H}\)为再生核\(k\)诱导出的再生核空间。 ♣

注.这里的再生性是由再生核空间的性质得到的，后面会证明这个性质。

再生核空间的构造

从核函数出发的构造思路如下：第一步构造一个线性空间；第二步在该线性空间上定义内积，于是得到一个内积空间；第三步对该内积空间作完备化处理，于是得到Hilbert空间；这样得到的空间称为再生核希尔伯特空间，简称为再生核空间。 令\(\Phi(x)=k(x,\cdot)\)将预测变量\(x\)映射到一个函数空间，该函数空间的函数\(g: \mathcal{X} \rightarrow R\).

步骤1. 构造线性空间。令 \[f(\cdot)=\sum_{i=1}^n \alpha_i \Phi(x_i)=\sum_{i=1}^n \alpha_i k(x_i,\cdot).\]其中，\(n \in N,\alpha_i \in R, x_i \in \mathcal{X}\)取遍各自空间所有值。容易证明，它是定义在实数域上的线性空间。

步骤2.定义内积。设\(g(\cdot)=\sum_{i=1}^{n'}\beta_j k(\cdot, x_j')\)，定义内积为 \[\langle f, g\rangle = \sum_{i=1}^n\sum_{j=1}^{n'} \alpha_i\beta_j k(x_i,x_j).\] 由该内积定义可知： \[\langle \Phi(x), \Phi(x')\rangle=k(x,x'). \tag{3.1}\] 实际上，我们只需定义\(\Phi(x)\)与\(\Phi(x')\)之间的内积\(\langle \Phi(x), \Phi(x')\rangle=k(x,x')\),然后根据内积的线性性质，就可以推出\(g\)和\(f\)之间的内积值。可以证明，我们这样定义的内积确实是一个内积，满足内积所需的性质。

非常重要的一点是，根据该内积定义，我们推导出 \[\langle k(\cdot, x), f\rangle = f(x), \tag{3.2}\] 该性质称为核函数的再生性，顾名思义，核函数在某点\(x\)的映射和函数\(f\)的内积可以生出\(f\)在该点\(x\)的函数值，这是多么神奇的性质呀！特别地，\((3.2)\)可以得 \[\langle k(\cdot, x), k(\cdot, x')\rangle = k(x,x'),\] 这个和\((3.1)\)的内积定义是一致的，也就是说，它可以由再生性推导出来，也可以由内积的定义推导出来。

接下来，我们利用再生性证明：\(\langle f,f\rangle =0 \Rightarrow f=0.\) 根据\((3.2)\)式和柯西施瓦茨不等式得， \[|f(x)|^2=|\langle k(\cdot, x),f\rangle|^2\leq k(x,x)*\langle f,f\rangle.\] 若存在\(x_0\)使得\(f(x_0)\neq 0\)，则\(\langle f,f\rangle>0\)，于是矛盾，故\(f=0\)。

正定核的运算封闭性

正定核的保运算性使得构造正定核变得更加easy。

命题1.设\(k_1, k_2, \cdots\)为任意定义在同一定义域上的正定核，则(i)若\(\alpha_1,\alpha_2\geq 0\)，则\(\alpha_1 k_1 + \alpha_2 k_2\)也是正定核；若对任意\(x,x'\)有\(k(x,x')=\lim_{n\rightarrow \infty} k_n(x,x')\)存在,则\(k\)也是正定核；(ii)逐点乘积\(k=k_1k_2\)也是正定的；(iii)张量积\(k_1 \otimes k_2\)和直和\(k_1 \oplus k_2\)都是定义在\((\mathcal{X}_1 \times\mathcal{X}_2) \times(\mathcal{X}_1 \times\mathcal{X}_2)\)上的正定核。

定义(度量空间的稠密性)：设\(X\)是度量空间，\(E\subset X\)，若对任意\(x\in X\)和\(\epsilon >0\)，都存在\(y\in E\)使得\(x \in B(y,\epsilon)\)，则称\(E\)在\(X\)中是稠密的，其中\(B(y,\epsilon)\)表示中心为\(y\)，半径为\(\epsilon\)的小球。

该定义表明，对于任意\(X\)中的点，我们可以找到一个\(E\)中的点\(y\)，它与\(x\)的距离成分小。于是，易知空间稠密是一个相对概念，有理数集在实数集是稠密的。

定义(一致核)：设\(C(X)\)是定义于紧子集\(\mathcal{S}\subset R^d\)上的连续函数空间，若正定核\(k\)生成的再生核希尔伯特空间\(\mathcal{H}\)关于\(C(X)\)在\(\|\cdot\|_\infty\)范数意义上是稠密的，则称\(k\)是一致核。

该定义表示一致核生成的RKHS几乎和连续函数空间等价，这类核非常重要，它使得该RKHS几乎可以逼近任意连续函数。Steinwart 证明高斯核就是一致核。

参考文献:
Hofmann, T. , SchLkopf, B. , & Smola, A. J. . (2008). Kernel methods in machine learning. Annals of Stats, 36(3).

STEINWART, I. (2002). On the influence of the kernel on the consistency of support vector machines. J. Mach. Learn. Res. 2 67–93