Kernel Methods

References

• Lecture: 李政軒, https://www.youtube.com/watch?v=p4t6O9uRX-U&list=PLt0SBi1p7xrRKE2us8doqryRou6eDY
• Reading: John Shawe-Taylor and Nello Cristianini, Kernel Methods for Pattern Analysis.
• Reading: Bernhard Schölkopf and Alexander J. Smola, Learning with Kernels.

1. Basic Idea

Kernel Method 的核心思想是通过非线性映射 (Non-linear Mapping) 将原始数据映射到一个更高维的特征空间 (Feature Space), 使得在该空间中, 原本线性不可分的问题变得线性可分. 然后, 我们可以在这个高维空间中应用线性模型, 例如线性分类器或线性回归, 来处理数据.

具体地, 对于这样的线性不可分数据 $x$, 定义一个映射函数 $\varphi :{\mathbb{R}}^d\to \mathcal{H}$, 将数据点 $x$ 映射到高维 Hilbert 空间 $\mathcal{H}$ 中. 此外定义一个核函数 $\kappa :{\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$, 用于衡量输入数据点之间的相似性, 即映射后空间中对应点的内积:

$$\kappa (x,z)=⟨\varphi (x),\varphi (z)⟩.$$

根据理论可以保证, 任意非线性可分的数据集, 只要选择合适的映射函数 $\varphi$ 和核函数 $\kappa$, 就可以将其映射到一个高维空间中, 使得数据在该空间中线性可分. 这使得我们能够利用线性模型来处理复杂的非线性问题.

1.1 Feature Mapping

• 对于原始 ${\mathbb{R}}^2$ 空间中的数据点 $(x_1,x_2)$, 我们需要使用非线性边界, 例如椭圆 $\frac{x_1^2}{a^2}+\frac{x_2^2}{b^2}=1$, 来进行分类.
• 如果将数据映射到 ${\mathbb{R}}^3$ 空间, 使用映射函数 $\varphi :{\mathbb{R}}^2\to {\mathbb{R}}^3$, $(x_1,x_2)\mapsto (z_1,z_2,z_3)=(x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2)$, 则此时的椭圆形边界在新空间中变成了一个平面边界: $z_1/a^2+z_2/b^2=1$.
• 因此, 通过适当的映射函数 $\varphi$, 可以将原本线性不可分的问题转化为线性可分的问题.

1.2 Kernel Function

同样以上述映射为例, 关注映射前后数据点之间的内积关系.

在原始空间中, 两个数据点 $(x_1,x_2)$ 和 $(x_1^{\prime },x_2^{\prime })$ 之间的内积为:

$$⟨x,x^{\prime }⟩=x_1{x}_1^{\prime }+x_2{x}_2^{\prime }.$$

在映射后的空间中, 对应的两个数据点 $(z_1,z_2,z_3)$ 和 $(z_1^{\prime },z_2^{\prime },z_3^{\prime })$ 之间的内积为:

$$⟨\varphi (x),\varphi (x^{\prime })⟩=z_1{z}_1^{\prime }+z_2{z}_2^{\prime }+z_3{z}_3^{\prime }=(x_1{x}_1^{\prime }+x_2{x}_2^{\prime }{)}^2.$$

不难发现, 映射后空间中的内积可以通过原始空间中的内积来表示, 简记为 $\kappa (x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$. 这个函数 $\kappa (x,x^{\prime })$ 被称为核函数 (Kernel Function). 在本例中, 具体形式为 $\kappa (x,x^{\prime })=(x_1{x}_1^{\prime }+x_2{x}_2^{\prime }{)}^2=(⟨x,x^{\prime }⟩{)}^2$.

Definition (Kernel Function). 称函数 $\kappa :{\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$ 为 $\mathcal{X}$ 上的核函数 (Kernel Function), 若存在 feature mapping $\varphi :\mathcal{X}\to \mathcal{H}$, 使得对于任意 $x,x^{\prime }\in \mathcal{X}$,

$$\kappa (x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩.$$

因此, Kernel Function 变成了高维映射 $\varphi$ 的一种替代表示. 只要知道核函数 $\kappa (x,x^{\prime })$, 就等价于知道了映射 $\varphi$ 后的内积关系. 若只关注高维空间中的内积运算, 则无需显式地知道映射 $\varphi$ 本身. 这就是核方法的核心思想.

1.3 Geometry from Kernels

即使只知道 Feature Space 中的内积关系, 即核函数, 也能推导出一些最重要的几何性质, 例如距离和角度.

Distance in Feature Space.

$$\begin{array}{rl}{d}^2(\varphi (x),\varphi (x^{\prime }))& =\Vert \varphi (x)-\varphi (x^{\prime }){\Vert }^2\\ & =⟨\varphi (x),\varphi (x)⟩-2⟨\varphi (x),\varphi (x^{\prime })⟩+⟨\varphi (x^{\prime }),\varphi (x^{\prime })⟩\\ & =\kappa (x,x)-2\kappa (x,x^{\prime })+\kappa (x^{\prime },x^{\prime }).\end{array}$$

Angle in Feature Space.

$$\begin{array}{rl}\theta & =\arccos \frac{⟨\varphi (x),\varphi (x^{\prime })⟩}{\Vert \varphi (x)\Vert \Vert \varphi (x^{\prime })\Vert }\\ & =\arccos \frac{\kappa (x,x^{\prime })}{\sqrt{\kappa (x,x)\kappa (x^{\prime },x^{\prime })}}.\end{array}$$

1.4 Gram Matrix

给定一组数据点 $\{x^{(1)},x^{(2)},\dots ,x^{(m)}\}$, 可以构造一个 $m\times m$ 的矩阵 $K$:

$$K=\left[\begin{array}{cccc}\kappa (x^{(1)},x^{(1)})& \kappa (x^{(1)},x^{(2)})& \cdots & \kappa (x^{(1)},x^{(m)})\\ \kappa (x^{(2)},x^{(1)})& \kappa (x^{(2)},x^{(2)})& \cdots & \kappa (x^{(2)},x^{(m)})\\ ⋮& ⋮& \ddots & ⋮\\ \kappa (x^{(m)},x^{(1)})& \kappa (x^{(m)},x^{(2)})& \cdots & \kappa (x^{(m)},x^{(m)})\end{array}\right].$$

这个矩阵 $K$ 被称为内积矩阵 (Inner Product Matrix), Gram 矩阵 (Gram Matrix) 或 核矩阵 (Kernel Matrix). 它包含了所有数据点在 Feature Space 中的内积信息, 因此可以用于计算距离和角度等几何性质.

2. Characterization of Kernels

核定理指出, 只要一个函数 $\kappa (x,x^{\prime })$ 满足有限半正定条件, 就存在一个映射 $\varphi$, 使得 $\kappa (x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$. 这意味着可以通过设计合适的核函数, 来隐式地定义一个高维映射 $\varphi$, 而无需显式构造该映射.

Theorem (Moore-Aronszajn Theorem). 设 $\mathcal{X}$ 为任意非空集合, 若函数 $\kappa :\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 是对称函数. 则下列命题等价:

1. $\kappa$ 是有限半正定核 (PSD Kernel), 即对于任意有限点集 $\{x^{(1)},x^{(2)},\dots ,x^{(m)}\}\subset \mathcal{X}$ 及任意实数系数 $\{c_1,c_2,\dots ,c_m\}\subset \mathbb{R}$,

   $$\sum _{i=1}^m\sum _{j=1}^m{c}_i{c}_j\kappa (x^{(i)},x^{(j)})\ge 0.$$

2. 由 $\kappa$ 定义的 Gram 矩阵 $K$ 为半正定矩阵, $K⪰0$.

3. 存在一个 Hilbert 空间 $\mathcal{H}$ 和一个特征映射 $\varphi :\mathcal{X}\to \mathcal{H}$, 使得对于任意 $x,x^{\prime }\in \mathcal{X}$,

   $$\kappa (x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime }){⟩}_{\mathcal{H}}.$$

故此定理保证了, 只要设计的核函数 $\kappa$ 满足有限半正定条件, 就一定存在一个对应的高维映射 $\varphi$ 和 Hilbert 空间 $\mathcal{H}$, 使得 $\kappa (x,x^{\prime })$ 可以表示为 $\varphi (x)$ 和 $\varphi (x^{\prime })$ 在该空间中的内积.

2.1 Commonly Used Kernels

Definition (Polynomial Kernel). 对于任意 $x,x^{\prime }\in {\mathbb{R}}^N$ 及常数 $c\ge 0$ 和整数 $d\ge 1$, 定义多项式核为:

$$\kappa (x,x^{\prime })=(x^{\top }{x}^{\prime }+c{)}^d.$$

例如 $N=2,d=2$, 则

$$\begin{array}{rl}\kappa (x,x^{\prime })& =(x_1{x}_1^{\prime }+x_2{x}_2^{\prime }+c{)}^2\\ & =x_1^2{x}_1^{\prime 2}+x_2^2{x}_2^{\prime 2}+2x_1{x}_1^{\prime }{x}_2{x}_2^{\prime }+2c{x}_1{x}_1^{\prime }+2c{x}_2{x}_2^{\prime }+c^2\\ & ={\left[\begin{array}{c}{x}_1^2\\ x_2^2\\ \sqrt{2}{x}_1{x}_2\\ \sqrt{2c}{x}_1\\ \sqrt{2c}{x}_2\\ c\end{array}\right]}^{\top }\left[\begin{array}{c}{x}_1^{\prime 2}\\ x_2^{\prime 2}\\ \sqrt{2}{x}_1^{\prime }{x}_2^{\prime }\\ \sqrt{2c}{x}_1^{\prime }\\ \sqrt{2c}{x}_2^{\prime }\\ c\end{array}\right].\end{array}$$

对应的 feature mapping 为:

$$\varphi \left(\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\right)=\left[\begin{array}{c}{x}_1^2\\ x_2^2\\ \sqrt{2}{x}_1{x}_2\\ \sqrt{2c}{x}_1\\ \sqrt{2c}{x}_2\\ c\end{array}\right].$$

事实上可以计算出, 对于任意 $N$ 维输入和 $d$ 次多项式核, 对应的 feature mapping $\varphi$ 会将输入映射到一个维度为 $\left(\genfrac{}{}{0ex}{}{N+d}{d}\right)$ 的空间中.

Definition (Gaussian / RBF Kernel). 对于任意 $x,x^{\prime }\in {\mathbb{R}}^N$ 及常数 $\sigma >0$, 定义高斯核为:

$$\kappa (x,x^{\prime })=\exp \left(-\frac{\Vert x-x^{\prime }{\Vert }^2}{2{\sigma }^2}\right).$$

Definition (Laplacian Kernel). 对于任意 $x,x^{\prime }\in {\mathbb{R}}^N$ 及常数 $\sigma >0$, 定义拉普拉斯核为:

$$\kappa (x,x^{\prime })=\exp \left(-\frac{\Vert x-x^{\prime }{\Vert }_1}{\sigma }\right).$$

Definition (Sigmoid Kernel). 对于任意 $x,x^{\prime }\in {\mathbb{R}}^N$ 及常数 $\alpha >0$ 和 $c\in \mathbb{R}$, 定义 Sigmoid 核为:

$$\kappa (x,x^{\prime })=\tanh (\alpha x^{\top }{x}^{\prime }+c).$$

3. Dual Representation and Kernel Trick

考虑在 feature space $\mathcal{H}$ 中的线性函数 $f(x)=w^{\top }\varphi (x)+b$, 其中 $w\in \mathcal{H}$, $b\in \mathbb{R}$. 我们希望仅通过核函数 $\kappa (x,x^{\prime })$ 来表示这个函数 $f(x)$.

Theorem (Representer Theorem). 给定训练数据集 $\{(x^{(i)},y^{(i)}){\}}_{i=1}^N$, 假设希望最小化以下正则化经验风险:

$$J(w)=\sum _{i=1}^{N}L(y^{(i)},f(x^{(i)}))+\lambda \Vert w{\Vert }^2,$$

其中 $L$ 是损失函数, $\lambda >0$ 是正则化参数. 则最优解 $w^{\ast }$ 可以表示为训练数据点在 feature space 中的线性组合:

$$w^{\ast }=\sum _{i=1}^N{\alpha }_i\varphi (x^{(i)}),$$

其中 ${\alpha }_i\in \mathbb{R}$ 是系数.

换言之, 最优权重向量 $w^{\ast }$ 可以完全由训练数据点的映射 $\varphi (x^{(i)})$ 线性组合而成, 即 $w^{\ast }\in \text{span}\{x^{(1)},x^{(2)},\dots ,x^{(N)}\}$. 这意味着可以将原始优化问题转化为关于系数 ${\alpha }_i$ 的优化问题.

将 $w^{\ast }$ 代入线性函数 $f(x)$ 中, 可得 dual representation:

$$\begin{array}{rl}f(\varphi (x))& =w^{\ast \top }\varphi (x)+b\\ & ={\left(\sum _{i=1}^N{\alpha }_i\varphi (x^{(i)})\right)}^{\top }\varphi (x)+b\\ & =\sum _{i=1}^N{\alpha }_i⟨\varphi (x^{(i)}),\varphi (x)⟩+b\\ & =\sum _{i=1}^N{\alpha }_i\kappa (x^{(i)},x)+b.\end{array}$$

因此, 线性函数 $f(x)$ 可以表示为核函数 $\kappa (x^{(i)},x)$ 的线性组合, 其中系数为 ${\alpha }_i$.

综上, 我们可以通过核函数 $\kappa (x,x^{\prime })$ 来隐式地处理高维映射 $\varphi$, 这就是所谓的核技巧 (Kernel Trick).

4. Kernel-Based Linear Regression

给定训练数据集 $\{({\mathbf{x}}_{\mathbf{i}},y_i){\}}_{i=1}^N$, 其中 ${\mathbf{x}}_{\mathbf{i}}\in {\mathbb{R}}^d$ 为输入特征, $y_i\in \mathbb{R}$ 为对应目标值. 给定一个核函数 $\kappa :{\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$, 对应的映射函数为 $\varphi :{\mathbb{R}}^d\to \mathcal{H}$.

输入矩阵为:

$$\Phi :=\left[\begin{array}{cc}1& \varphi ({\mathbf{x}}_1{)}^{\top }\\ 1& \varphi ({\mathbf{x}}_2{)}^{\top }\\ ⋮& ⋮\\ 1& \varphi ({\mathbf{x}}_{\mathbf{N}}{)}^{\top }\end{array}\right]\in {\mathbb{R}}^{N\times (D+1)}.$$

输出标签仍为 $\mathbf{y}=[y_1,y_2,\dots ,y_N{]}^{\top }\in {\mathbb{R}}^N$. 假设线性回归模型为:

$$\mathbf{y}=\Phi \mathbf{w}+\mathbf{ϵ},\mathbf{ϵ}\sim \mathcal{N}(0,{\sigma }^{2}I).$$

对应的 OLS 问题为 ${\min }_{\mathbf{w}}\Vert \mathbf{y}-\Phi \mathbf{w}{\Vert }_2^2$, 其 normal equation 为:

$${\Phi }^{\top }\Phi \hat{\mathbf{w}}={\Phi }^{\top }\mathbf{y}.$$

若 ${\Phi }^{\top }\Phi$ 可逆, 则有闭式解:

$$\hat{\mathbf{w}}={\left({\Phi }^{\top }\Phi \right)}^{-1}{\Phi }^{\top }\mathbf{y}.$$

根据 Representer Theorem, 最优解 ${\mathbf{w}}^{\ast }$ 可以表示为训练数据点在特征空间中的线性组合, 即存在系数向量 $\mathbf{\alpha }\in {\mathbb{R}}^N$, 使得:

$${\mathbf{w}}^{\ast }={\Phi }^{\top }\mathbf{\alpha }.$$

为了求解 $\mathbf{\alpha }$, 将 ${\mathbf{w}}^{\ast }$ 代入 normal equation:

$$\Vert \mathbf{y}-\Phi {\mathbf{w}}^{\ast }{\Vert }_2^2=\Vert \mathbf{y}-\Phi {\Phi }^{\top }\mathbf{\alpha }{\Vert }_2^2.$$

定义核矩阵 $K=\Phi {\Phi }^{\top }\in {\mathbb{R}}^{N\times N}$, 其中 $K_{ij}=1+\kappa ({\mathbf{x}}_{\mathbf{i}},{\mathbf{x}}_{\mathbf{j}})$. 则上式可写为:

$$\underset{\mathbf{\alpha }}{\min }\Vert \mathbf{y}-K\mathbf{\alpha }{\Vert }_2^2.$$

对应的 normal equation 为:

$$K^{\top }K\hat{\mathbf{\alpha }}=K^{\top }\mathbf{y}.$$

若 $K$ 可逆, 则有闭式解:

$$\hat{\mathbf{\alpha }}=K^{-1}\mathbf{y}.$$

对于任意新的输入样本 ${\mathbf{x}}_{\ast }$, 其预测值为:

$$\begin{array}{rl}\widehat{y_{\ast }}& =\varphi ({\mathbf{x}}_{\ast }{)}^{\top }{\mathbf{w}}^{\ast }\\ & =\varphi ({\mathbf{x}}_{\ast }{)}^{\top }{\Phi }^{\top }\hat{\mathbf{\alpha }}\\ & =\sum _{i=1}^N\widehat{{\alpha }_i}\left(1+\kappa ({\mathbf{x}}_{\mathbf{i}},{\mathbf{x}}_{\ast })\right).\end{array}$$

实践中往往通过 KRR (Kernel Ridge Regression) 来避免核矩阵 $K$ 不可逆的问题, 即在目标函数中加入正则化项 $\lambda \Vert \mathbf{\alpha }{\Vert }_2^2$:

$$\mathbf{\alpha }=(K+\lambda I{)}^{-1}\mathbf{y}.$$

5. RKHS and Representer Theorem

关于 RKHS, 我们最终想得到如下目标:

1. 从一个核函数 $\kappa$ 出发, 构造出一个以函数为元素的 Hilbert 空间 $\mathcal{H}$.
2. 该 Hilbert 空间 $\mathcal{H}$ 可以定义一个内积 $⟨\cdot ,\cdot {⟩}_{\mathcal{H}}$, 使得 $\kappa (x,z)=⟨\kappa (\cdot ,x),\kappa (\cdot ,z){⟩}_{\mathcal{H}}$.
3. 在该内积下, 任意函数 $f\in \mathcal{H}$ 满足再生性质: $f(x)=⟨f,\kappa (\cdot ,x){⟩}_{\mathcal{H}}$.

为了达到这一目标, 整体思路为:

1. 首先定义 PSD 核函数 $\kappa$ 和对应的核截断 $\kappa (\cdot ,x)$.
2. 利用核截断构造一个函数线性空间 ${\mathcal{F}}_{\kappa }$.
3. 在该函数空间上定义由 kernel 诱导的内积.
4. 用这个内积直接推出 reproducing property.
5. 最后对该空间进行完备化, 得到 RKHS.

更详细的 RKHS 定义和构造见 RKHS and Representer Theorem.

Related Notes

• RKHS and Representer Theorem
• Support Vector Machine
• Regularization