SVM 支持向量机(下):非线性型

核函数和软间隔

Posted by Xiaosheng on April 17, 2017

3. 核函数

在前面的讨论中,我们假设训练样本是线性可分的,即存在一个分隔超平面能将训练样本正确分类。然而在现实任务中,原始样本空间内也许并不存在一个能正确划分两类样本的超平面。对这样的问题,可以将样本从原始空间映射到一个更高维的特征空间,使得样本在新“特征空间”中线性可分。

例如下图,左图中的数据显然是线性不可分的,但将实例空间变换到一个新的由原始特征的平方构成的新“特征空间”后,我们发现这组数据变得几乎线性可分了。

rticle_38_

右图通过将原始数据点 $(x,y)$ 变换为 $(x’,y’)=(x^2,y^2)$,数据的线性可分性大大增强,利用线性决策面 $x’+y’=3$ 便可将该组数据很好地分离。该决策面对应于原始特征空间中圆心位于原点,半径为 $\sqrt{3}$ 的一个圆。

我们将这种特征变换称作特征映射 (feature mapping),映射函数称为 $\phi$。习惯上,我们把变换后的空间称为特征空间 (feature space),而将原始空间称为输入空间 (input space)。我们希望将得到的特征映射后的特征应用于 SVM 分类,而不是最初的特征。

如果原始空间是有限维,即属性数有限,那么一定存在一个高维特征空间使样本可分。

于是,在特征空间中划分超平面对应的模型可以表示为:

\[f(\boldsymbol{x}) = \boldsymbol{w}^\top\phi(\boldsymbol{x})+b \tag{3.1}\]

类似于 $(1.6)$,有

\[\min_{\boldsymbol{w},b} \frac{1}{2} \Vert \boldsymbol{w} \Vert^2\\ \text{s.t. } y^{(i)}(\boldsymbol{w}^\top\phi(\boldsymbol{x}^{(i)}) + b) \ge 1, \quad i = 1,2,...,m \tag{3.2}\]

其对偶问题是

\[\max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\phi(\boldsymbol{x}^{(i)})^\top\phi(\boldsymbol{x}^{(j)}) \tag{3.3}\] \[\begin{align} \mathbb{s.t.}&\sum_{i=1}^m\alpha_iy^{(i)}=0\\ &\alpha_i\ge0,\quad i=1,2,\cdots,m \end{align}\]

式中的 $\phi(\boldsymbol{x}^{(i)})^\top\phi(\boldsymbol{x}^{(j)})$ 就是样本 $\boldsymbol{x}^{(i)}$ 与 $\boldsymbol{x}^{(j)}$ 映射到特征空间之后的内积。但是特征空间的维数可能很高,甚至可能是无穷维,因此直接计算 $\phi(\boldsymbol{x}^{(i)})^\top\phi(\boldsymbol{x}^{(j)})$ 通常是非常困难的。为了避开这个障碍,可以设想这样一个函数:

\[\mathcal{k}(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(j)})=\langle\phi(\boldsymbol{x}^{(i)}),\phi(\boldsymbol{x}^{(j)})\rangle=\phi(\boldsymbol{x}^{(i)})^\top\phi(\boldsymbol{x}^{(j)}) \tag{3.4}\]

即 $\boldsymbol{x}^{(i)}$ 和 $\boldsymbol{x}^{(j)}$ 在特征空间的内积 $\langle\phi(\boldsymbol{x}^{(i)}),\phi(\boldsymbol{x}^{(j)})\rangle$ 等于它们在原始输入空间中通过函数 $\mathcal{k}$ 计算的结果,这里的函数 $\mathcal{k}$ 就是核函 (kernel function)。有了核函数,我们就不必直接去计算高维甚至无穷维特征空间中的内积。

核技巧

核技巧本质上一种特征空间的映射,它的技巧性就体现在它使用核函数(kernel function),无须实际构造新的特征向量便可以得到新空间中对应的内积。具体的示例,可以参考特征的构造与变换

通过使用核函数可以学习非线性支持向量机,等价于隐式地在高维特征空间中学习线性支持向量机。核方法(kernel method)是比支持向量机更为一般的机器学习方法。Cortes 与 Vapnik 提出线性支持向量机,Boser、Guyon 与 Vapnik 又引入核技巧,提出非线性支持向量机。

于是式 $(3.3)$ 可以重写为

\[\max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\mathcal{k}(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(j)}) \tag{3.5}\] \[\begin{align}\mathbb{s.t.} &\sum_{i=1}^m\alpha_iy^{(i)}=0\\ &\alpha_i\ge0,\quad i=1,2,\cdots,m \end{align}\]

求解后即可得对应的模型:

\[\begin{align} f(\boldsymbol{x}) &= \boldsymbol{w}^\top\phi(\boldsymbol{x})+b\\ &=\sum_{i=1}^m\alpha_iy^{(i)}\phi(\boldsymbol{x}^{(i)})^\top\phi(\boldsymbol{x})+b\\ &=\sum_{i=1}^m\alpha_iy^{(i)}\mathcal{k}(\boldsymbol{x},\boldsymbol{x}^{(i)})+b\end{align} \tag{3.6}\]

显然,若已知合适映射 $\phi$ 的具体形式,则可写出核函数 $\mathcal{k}$。但在现实任务中,我们通常不知道 $\phi$ 的具体形式,那么合适的核函数是否一定存在呢?事实上,只要一个对称函数所对应的核矩阵半正定,它就能作为核函数使用。对于一个半正定核矩阵,总能找到一个与之对应的映射 $\phi$。换言之,任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”(Reproducing Kernel Hilbert Space,简称 RKHS)的特征空间。

通过前面的讨论可知,我们希望样本在特征空间内线性可分,因此特征空间的好坏对支持向量机的性能至关重要。问题是,在不知道特征映射的形式时,我们并不知道什么样的核函数是合适的,而核函数也仅是隐式定义了这个特征空间。于是,“核函数选择”成为支持向量机的最大变数,若核函数选择不合适,意味着将样本映射到了一个不合适的特征空间,很可能导致性能不佳。下表列出了常用的核函数:

\[\begin{array}{c|c} \hline 名称 & 表达式 & 参数\\ \hline 线性核 & \mathcal{k}(\boldsymbol{x},\boldsymbol{z})=\boldsymbol{x}^\top\boldsymbol{z} & \\ \hline 多项式核 & \mathcal{k}(\boldsymbol{x},\boldsymbol{z})=(\boldsymbol{x}^\top\boldsymbol{z})^d & d\ge1 \text{ 为多项式的次数}\\ \hline 高斯核 & \mathcal{k}(\boldsymbol{x},\boldsymbol{z})=\exp(-\frac{\Vert\boldsymbol{x}-\boldsymbol{z}\Vert^2}{2\sigma^2}) & \sigma\gt0 \text{ 为高斯核的带宽(width)}\\ \hline 拉普拉斯核 & \mathcal{k}(\boldsymbol{x},\boldsymbol{z})=\exp(-\frac{\Vert\boldsymbol{x}-\boldsymbol{z}\Vert}{\sigma}) & \sigma\gt0\\ \hline \text{Sigmoid 核} & \mathcal{k}(\boldsymbol{x},\boldsymbol{z})=\tanh(\beta\boldsymbol{x}^\top\boldsymbol{z}+\theta) & \tanh \text{ 为双曲正切函数,} \beta\gt0,\theta\lt0\\ \hline \end{array}\]

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

  • 若 $k_1$ 和 $k_2$ 为核函数,则对于任意正数 $\gamma_1$、$\gamma_2$,其线性组合 $\gamma_1k_1+\gamma_2k_2$ 也是核函数。
  • 若 $k_1$ 和 $k_2$ 为核函数,则核函数的直积 $k_1\otimes k_2(\boldsymbol{x},\boldsymbol{z})=k_1(\boldsymbol{x},\boldsymbol{z})k_2(\boldsymbol{x},\boldsymbol{z})$ 也是核函数。
  • 若 $k_1$ 为核函数,则对于任意函数 $g(\boldsymbol{x})$,$k(\boldsymbol{x},\boldsymbol{z})=g(\boldsymbol{x})k_1(\boldsymbol{x},\boldsymbol{z})g(\boldsymbol{z})$ 也是核函数。

在核函数的选择方面有一些基本的经验,例如对于文本数据通常采用线性核,情况不明时可先尝试高斯核。此外,核函数不是 SVM 专用的,只要能将目标函数能完全地用内积的形式来表示,都可使用核函数来高效地计算高维向量空间的分类结果。

4. 软间隔

在之前的讨论中,我们一直假定训练样本在原始空间或者映射后的特征空间中是线性可分的,即存在一个超平面能将不同类的样本完全划分开。然而,在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分;退一步说,即便恰好找到了某个核函数使得训练集在特征空间中线性可分,也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

例如,看下面两张图:

rticle_54_

可以看到当数据集中存在离群点(可能是噪声)时会造成超平面的移动,间隔缩小,可见以前的模型对噪声非常敏感。再有甚者,如果离群点在另外一个类中,那么这时候就线性不可分了。

缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此,要引入软间隔 (soft margin) 的概念。具体来说,前面介绍的支持向量机形式是要求所有样本均满足约束:

\[y^{(i)}(\boldsymbol{w}^\top\boldsymbol{x}^{(i)}+b)\ge1 \tag{4.1}\]

即要求所有样本都必须划分正确,这称为硬间隔 (hard margin),而软间隔则是允许某些样本不满足这个约束。根据软间隔的思想,我们把最优化问题调整为:

\[\min_{\gamma,\boldsymbol{w},b}\frac{1}{2}\Vert\boldsymbol{w}\Vert^2+C\sum_{i=1}^m\xi_i \tag{4.2}\] \[\begin{align} \text{s.t. } &y^{(i)}(\boldsymbol{w}^\top\boldsymbol{x}^{(i)}+b)\ge1-\xi_i\\&\xi_i\ge0,\quad i=1,2,\cdots,m\end{align}\]

这就是常用的软间隔支持向量机。非负变量 $\xi_i$ 被称为“松弛变量” (slack variables),引入 $\xi_i$ 后就允许某些样本点的函数间隔小于 $1$ 甚至为负,即样本点在间隔区间之内甚至可以在对方的区域内。

而放松限制条件后,我们需要重新调整目标函数,以对离群点进行处罚,目标函数后面加上的 $C\sum_{i=1}^m\xi_i$ 就表示离群点越多,目标函数值越大,而我们要求的是尽可能小的目标函数值。这里的 $C$ 是离群点的权重, $C$ 越大表明离群点对目标函数影响越大,也就是越不希望看到离群点。

当 $C$ 无穷大时,$(4.2)$ 迫使所有样本均满足约束 $(4.1)$,于是 $(4.2)$ 等价于 $(1.6)$;当 $C$ 取有限值时,$(4.2)$ 允许一些样本不满足约束。

与之前的做法相似,我们也使用拉格朗日对偶性将最优化问题转换为对偶问题。首先,通过拉格朗日乘子法构造 $(4.2)$ 的拉格朗日函数:

\[\begin{align}L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})&=\frac{1}{2}||\boldsymbol{w}||^2+C\sum_{i=1}^{m}\xi_i\\&\quad+\sum_{i=1}^m\alpha_i\big(1-\xi_i-y^{(i)}(\boldsymbol{w}^\top\boldsymbol{x}^{(i)}+b)\big)-\sum_{i=1}^m\mu_i\xi_i\end{align} \tag{4.3}\]

其中 $\alpha_i\ge0$,$\mu_i\ge0$ 是拉格朗日乘子。根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:

\[\max_{\boldsymbol{\alpha}}\min_{\boldsymbol{w},b,\boldsymbol{\xi}}L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu}) \tag{4.4}\]

令 $L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})$ 对 $\boldsymbol{w},b,\xi_i$ 的偏导为零可得:

\[\begin{align} \boldsymbol{w}&=\sum_{i=1}^m\alpha_iy^{(i)}\boldsymbol{x}^{(i)} \\ 0 &= \sum_{i=1}^m\alpha_iy^{(i)}\\ C &= \alpha_i + \mu_i \end{align} \tag{4.5}\]

把 $(4.5)$ 代入 $(4.3)$,即得:

\[\begin{align}L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})&=\frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w}+C\sum_{i=1}^m\xi_i+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\alpha_i\xi_i\\&\quad-\sum_{i=1}^m\alpha_iy^{(i)}(\boldsymbol{w}^\top\boldsymbol{x}^{(i)})-\sum_{i=1}^m\alpha_iy^{(i)}b-\sum_{i=1}^m\mu_i\xi_i\end{align}\]

因为 $\sum_{i=1}^m\alpha_iy^{(i)}=0$,所以 $\sum_{i=1}^m\alpha_iy^{(i)}b=0$;又因为 $C=\alpha_i+\mu_i$,所以

\[C\sum_{i=1}^m\xi_i-\sum_{i=1}^m\alpha_i\xi_i-\sum_{i=1}^m\mu_i\xi_i=\sum_{i=1}^m(C-\alpha_i-\mu_i)\xi_i=0\]

所以上式可以进一步简化为:

\[\begin{align}L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})&=\frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w}+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\alpha_iy^{(i)}(\boldsymbol{w}^\top\boldsymbol{x}^{(i)})\\&=\frac{1}{2}\boldsymbol{w}^\top\sum_{i=1}^m\alpha_iy^{(i)}\boldsymbol{x}^{(i)}-\boldsymbol{w}^\top\sum_{i=1}^m\alpha_iy^{(i)}\boldsymbol{x}^{(i)}+\sum_{i=1}^m\alpha_i\\&=-\frac{1}{2}\bigg(\sum_{i=1}^m\alpha_iy^{(i)}\boldsymbol{x}^{(i)}\bigg)^\top\sum_{i=1}^m\alpha_iy^{(i)}\boldsymbol{x}^{(i)}+\sum_{i=1}^m\alpha_i\\&=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\boldsymbol{x}^{(i)}{}^\top\boldsymbol{x}^{(j)}\end{align}\]

于是 $(4.4)$ 可以进一步化为

\[\max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\boldsymbol{x}^{(i)}{}^\top\boldsymbol{x}^{(j)} \tag{4.6}\] \[\begin{align}\text{s.t. } &\sum_{i=1}^m\alpha_iy^{(i)}=0,\\&0\le\alpha_i\le C,\quad i=1,2,\cdots,m\end{align}\]

将上式与硬间隔下的对偶问题对比可以看到,两者唯一的差别就在于对偶变量的约束不同,$\alpha_i$ 又多了 $\alpha_i\le C$ 的限制。于是,可采用第 $2$ 节中同样地算法求解 $(4.6)$。同样地,对软间隔支持向量机的 $\text{KKT}$ 条件也发生了变化:

\[\begin{cases}\alpha_i\ge0,\quad\mu_i\ge0\\y^{(i)}(\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b)-1+\xi_i\ge0\\\alpha_i(y^{(i)}(\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b)-1+\xi_i)=0\\\xi_i\ge0,\quad\mu_i\xi_i=0\end{cases} \tag{4.7}\]

于是,对任意训练样本 $(\boldsymbol{x}^{(i)},y^{(i)})$,总有 $\alpha_i=0$ 或 $y^{(i)}(\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b)=1-\xi_i$。

  • 若 $\alpha_i=0$,则该样本不会对模型有任何影响;
  • 若 $\alpha_i\gt0$,则必有 $y^{(i)}(\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b)=1-\xi_i$,即该样本是支持向量:由 $C=\alpha_i+\mu_i$,若 $\alpha_i\lt C$,则 $\mu_i\gt0$,进而有 $\xi_i=0$,即该样本恰在最大间隔边界上;若 $\alpha_i=C$,则有 $\mu_i=0$,此时若 $\xi_i\le 1$ 则该样本落在最大间隔内部,若 $\xi_i\gt1$ 则该样本被错误分类。

由此可以看出,软间隔支持向量机的最终模型仅与支持向量有关。

参考

李航《统计学习方法》
周志华《机器学习》
Peter Flach《机器学习》
JerryLead《支持向量机SVM》