【机器学习基础】第十八课:支持向量机之核函数

核函数,直积

Posted by x-jeff on January 3, 2021

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.核函数

在之前的博客中,我们假设训练样本是线性可分的,即存在一个划分超平面能将训练样本正确分类。然而在现实任务中,原始样本空间内也许并不存在一个能正确划分两类样本的超平面。例如下图中的“异或”问题就不是线性可分的:

对这样的问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。例如在上图中,若将原始的二维空间映射到一个合适的三维空间,就能找到一个合适的划分超平面。⚠️幸运的是,如果原始空间是有限维,即属性数有限,那么一定存在一个高维特征空间使样本可分。

令$\phi (\mathbf x)$表示将$\mathbf x$映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可表示为:

\[f(\mathbf x)=\mathbf w ^T \phi (\mathbf x)+b \tag{1}\]

其中$\mathbf w,b$是模型参数,类似【机器学习基础】第十六课:支持向量机之间隔与支持向量中学到的SVM的基本型,有:

\[\begin{align*} &\min \limits_{\mathbf w,b} \quad \frac{1}{2} \lVert \mathbf w \rVert ^2 \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.& y_i(\mathbf w^T \phi (\mathbf x_i) +b) \geqslant 1,i=1,2,...,m \\ \end{array} \end{align*} \tag{2}\]

对偶问题是:

\[\begin{align*} &\max \limits_{\mathbf \alpha} \quad \sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi(\mathbf x_i)^T \phi(\mathbf x_j) \\ & \begin{array}{r@{\quad}l@{}l@{\quad}l} s.t.& \sum_{i=1}^m \alpha_i y_i=0 \\ & \alpha_i \geqslant 0,i=1,2,...,m \\ \end{array} \end{align*} \tag{3}\]

求解式(3)涉及到计算$\phi (\mathbf x_i)^T \phi (\mathbf x_j)$,这是样本$\mathbf x_i$与$\mathbf x_j$映射到特征空间之后的内积。由于特征空间维数可能很高,甚至可能是无穷维,因此直接计算$\phi (\mathbf x_i)^T \phi (\mathbf x_j)$通常是困难的。为了避开这个障碍,可以设想这样一个函数:

\[\kappa (\mathbf x_i,\mathbf x_j)=<\phi (\mathbf x_i)^T,\phi (\mathbf x_j)>=\phi (\mathbf x_i)^T \phi (\mathbf x_j) \tag{4}\]

即$\mathbf x_i$与$\mathbf x_j$在特征空间的内积等于它们在原始样本空间中通过函数$\kappa (\cdot,\cdot)$计算的结果。有了这样的函数,我们就不必直接去计算高维甚至无穷维特征空间中的内积,于是式(3)可重写为:

\[\begin{align*} &\max \limits_{\mathbf \alpha} \quad \sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \kappa (\mathbf x_i,\mathbf x_j) \\ & \begin{array}{r@{\quad}l@{}l@{\quad}l} s.t.& \sum_{i=1}^m \alpha_i y_i=0 \\ & \alpha_i \geqslant 0,i=1,2,...,m \\ \end{array} \end{align*} \tag{5}\]

求解后即可得到:

\[\begin{align} f(\mathbf x) & = \mathbf w^T \phi(\mathbf x) +b \\ & = \sum_{i=1}^m \alpha_i y_i \phi (\mathbf x_i)^T \phi (\mathbf x) + b \\ & = \sum_{i=1}^m \alpha_i y_i \kappa (\mathbf x, \mathbf x_i) + b \end{align} \tag{6}\]

这里的函数$\kappa(\cdot,\cdot)$就是“核函数(kernel function)”。式(6)显示出模型最优解可通过训练样本的核函数展开,这一展式亦称“支持向量展式(support vector expansion)”

显然,若已知合适映射$\phi (\cdot)$的具体形式,则可写出核函数$\kappa(\cdot,\cdot)$。但在现实任务中我们通常不知道$\phi (\cdot)$是什么形式,那么,合适的核函数是否一定存在呢?什么样的函数能做核函数呢?我们有下面的定理:

核函数定理:令$\chi$为输入空间,$\kappa(\cdot,\cdot)$是定义在$\chi \times \chi$上的对称函数,则$\kappa$是核函数当且仅当对于任意数据$D=\{\mathbf x_1,\mathbf x_2,…,\mathbf x_m \}$,“核矩阵”(kernel matrix)$K$总是半正定的:

\[\mathbf K = \begin{bmatrix} \kappa (\mathbf x_1,\mathbf x_1) & \cdots & \kappa (\mathbf x_1,\mathbf x_j) & \cdots & \kappa (\mathbf x_1,\mathbf x_m) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \kappa (\mathbf x_i,\mathbf x_1) & \cdots & \kappa (\mathbf x_i,\mathbf x_j) & \cdots & \kappa (\mathbf x_i,\mathbf x_m) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \kappa (\mathbf x_m,\mathbf x_1) & \cdots & \kappa (\mathbf x_m,\mathbf x_j) & \cdots & \kappa (\mathbf x_m,\mathbf x_m) \end{bmatrix}\]

上述定理表明,只要一个对称函数所对应的核矩阵半正定,它就能作为核函数使用。事实上,对于一个半正定核矩阵,总能找到一个与之对应的映射$\phi$。换言之,任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”(Reproducing Kernel Hilbert Space,简称RKHS)的特征空间。

通过前面的讨论可知,我们希望样本在特征空间内线性可分,因此特征空间的好坏对支持向量机的性能至关重要。需注意的是,在不知道特征映射的形式时,我们并不知道什么样的核函数是合适的,而核函数也仅是隐式地定义了这个特征空间。

⚠️于是,“核函数选择”成为支持向量机的最大变数。若核函数选择不合适,则意味着将样本映射到了一个不合适的特征空间,很可能导致性能不佳。

这方面有一些基本的经验,例如对文本数据通常采用线性核,情况不明时可先尝试高斯核。

常用的核函数:

$d=1$时退化为线性核,高斯核亦称RBF核。

此外,还可通过函数组合得到,例如:

👉若$\kappa_1$和$\kappa_2$为核函数,则对于任意正数$\gamma_1,\gamma_2$,其线性组合

\[\gamma_1 \kappa_1 + \gamma_2 \kappa_2\]

也是核函数。

👉若$\kappa_1$和$\kappa_2$为核函数,则核函数的直积

\[\kappa_1 \otimes \kappa_2 (\mathbf x,\mathbf z)=\kappa_1(\mathbf x,\mathbf z) \kappa_2 (\mathbf x,\mathbf z)\]

也是核函数。

👉若$\kappa_1$为核函数,则对于任意函数$g(\mathbf x)$,

\[\kappa (\mathbf x,\mathbf z)=g(\mathbf x)\kappa_1 (\mathbf x,\mathbf z)g(\mathbf z)\]

也是核函数。

2.直积

“直积”又称“笛卡尔乘积”:表示为$X \otimes Y$,第一个对象是$X$的成员而第二个对象是$Y$的所有可能有序对的其中一个成员。

例如,$A=\{a,b \},B=\{ 0,1,2 \}$,则:

\[A \otimes B=\{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)\}\] \[B \otimes A=\{(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)\}\]