机器学习周志华学习笔记-第6章＜支持向量机＞

机器学习周志华学习笔记-第6章<支持向量机>

6支持向量机

支持向量机是一种经典的二分类模型，是一种监督学习算法。基本模型定义为特征空间中最大间隔的线性分类器，其学习的优化目标便是间隔最大化，因此支持向量机本身可以转化为一个凸二次规划求解的问题。

6.1 函数间隔与几何间隔

对于二分类学习，假设现在的数据是线性可分的，这时分类学习最基本的想法就是找到一个合适的超平面，该超平面能够将不同类别的样本分开，类似二维平面使用$ax+by+c=0$来表示，超平面实际上表示的就是高维的平面，如下图所示：
对数据点进行划分时，易知：当超平面距离与它最近的数据点的间隔越大，分类的鲁棒性越好，即当新的数据点加入时，超平面对这些点的适应性最强，出错的可能性最小。因此需要让所选择的超平面能够最大化这个间隔Gap（如下图所示）， 常用的间隔定义有两种，一种称之为函数间隔，一种为几何间隔，下面将分别介绍这两种间隔，并对SVM为什么会选用几何间隔做了一些阐述。

6.1.1 函数间隔

在超平面$\omega ’x+b=0$确定的情况下，$|\omega ’x^{\ast }+b|$能够代表点$x^{\ast }$距离超平面的远近，易知：当$\omega ’x^{\ast }+b>0$时，表示$x^{\ast }$在超平面的一侧（正类，类标为1），而当$\omega ’x^{\ast }+b<0$时，则表示$x^{\ast }$在超平面的另外一侧（负类，类别为-1）。因此 $（\omega ’x^{\ast }+b）y^{\ast }$的正负性恰能表示数据点$x^{\ast }$是否被分类正确。于是便引出了函数间隔的定义（functional margin）：
$$\hat{\gamma }=y\left({\omega }^{T}x+b\right)=yf(x)$$
而超平面$（\omega ,b）$关于所有样本点$（X_i，Y_i）$的函数间隔最小值则为超平面在训练数据集T上的函数间隔：
$$\hat{\gamma }=\min {\hat{\gamma }}_i,(i=1,\dots ,n)$$
可以看出：这样定义的函数间隔在处理SVM上会有问题，当超平面的两个参数$\omega$和$b$同比例改变时，函数间隔也会跟着改变，但是实际上超平面还是原来的超平面，并没有变化。例如：${\omega }_1{x}_1+{\omega }_2{x}_2+{\omega }_3{x}_3+b=0$其实等价于$2{\omega }_1{x}_1+2{\omega }_2{x}_2+2{\omega }_3{x}_3+2b=0$，但计算的函数间隔却翻了一倍。从而引出了能真正度量点到超平面距离的概念–几何间隔（geometrical margin）。

6.1.2 几何间隔

几何间隔代表的则是数据点到超平面的真实距离，对于超平面$\omega ’x+b=0$，$\omega$代表的是该超平面的法向量，设$x^{\ast }$为超平面外一点$x$在法向量$\omega$方向上的投影点，$x$与超平面的距离为$\gamma$，则有$x^{\ast }=x-\gamma (\omega /||\omega ||)$，又$x^{\ast }$在超平面上，即$\omega ’x^{\ast }+b=0$，代入即可得：

$$\gamma =\frac{{\omega }^{T}x+b}{\Vert \omega \Vert }=\frac{f(x)}{\Vert \omega \Vert }$$
为了得到$\gamma$的绝对值，令$\gamma$乘上其对应的类别$y$，即可得到几何间隔的定义：
$$\tilde{\gamma }=y\gamma =\frac{\hat{\gamma }}{\Vert \omega \Vert }$$
从上述函数间隔与几何间隔的定义可以看出：实质上函数间隔就是$|\omega ’x+b|$，而几何间隔就是点到超平面的距离。

6.2 最大间隔与支持向量

通过前面的分析可知：函数间隔不适合用来最大化间隔，因此这里我们要找的最大间隔指的是几何间隔，于是最大间隔分类器的目标函数定义为：

$$\begin{array}{l}\max \tilde{\gamma }\\ y_i\left({\omega }^T{x}_i+b\right)={\hat{\gamma }}_i\ge \hat{\gamma },i=1,\dots ,n\end{array}$$

一般地，我们令$\hat{\gamma }$为1（这样做的目的是为了方便推导和目标函数的优化），从而上述目标函数转化为：
$$\max \frac{1}{\Vert \omega \Vert },\text{ s.t. }{y}_i\left({\omega }^T{x}_i+b\right)\ge 1,i=1,\dots ,n$$
对于$y(\omega ’x+b)=1$的数据点，即右图中位于$\omega ’x+b=1$或$\omega ’x+b=-1$上的数据点，我们称之为支持向量（support vector），易知：对于所有的支持向量，它们恰好满足$y^{\ast }(\omega ’x^{\ast }+b)=1$，而所有不是支持向量的点，有$y^{\ast }(\omega ’x^{\ast }+b)>1$

6.3 对偶问题

对于上述得到的目标函数，求$1/||\omega ||$的最大值相当于求$||\omega |{|}^2$的最小值，因此很容易将原来的目标函数转化为：
$$\min \frac{1}{2}\Vert \omega {\Vert }^2,\text{ s.t. }{y}_i\left({\omega }^T{x}_i+b\right)\ge 1,i=1,\dots .,n$$
即变为了一个带约束的凸二次规划问题，按书上所说可以使用现成的优化计算包（QP优化包）求解，但由于SVM的特殊性，一般我们将原问题变换为它的对偶问题，接着再对其对偶问题进行求解。为什么通过对偶问题进行求解，有下面两个原因：

• 一是因为使用对偶问题更容易求解；
• 二是因为通过对偶问题求解出现了向量内积的形式，从而能更加自然地引出核函数。

对偶问题，顾名思义，可以理解成优化等价的问题，更一般地，是将一个原始目标函数的最小化转化为它的对偶函数最大化的问题。对于当前的优化问题，首先我们写出它的朗格朗日函数：

上式很容易验证：当其中有一个约束条件不满足时，L的最大值为 ∞（只需令其对应的$\alpha$为 ∞即可）；当所有约束条件都满足时，L的最大值为$1/2||\omega |{|}^2$（此时令所有的$\alpha$为0），因此实际上原问题等价于：
$$\underset{\omega ,b}{\min }\theta (\omega )=\underset{\omega ,b}{\min }\underset{{\alpha }_i\ge 0}{\max }L(\omega ,b,\alpha )=p^{\ast }$$
由于这个的求解问题不好做, 因此一般我们将最小和最大的位置交换一下(需满足 KKT 条件),变成原问题的对偶问题:
$$\underset{{\alpha }_i\ge 0}{\max }\underset{\omega ,b}{\min }L(\omega ,b,\alpha )=d^{\ast }$$

这样就将原问题的求最小变成了对偶问题求最大 (用对偶这个词还是很形象), 接下来便可先求 L 对 $\omega$ 和 $b$ 的极小, 再求 L 对 $\alpha$ 的极大。

1. 首先求 L 对 $\omega$ 和 $b$ 的极小, 分别求 L 关于 $\omega$ 和 $b$ 的偏导, 可以得出:

$$\begin{array}{l}\frac{\partial L}{\partial \omega }=0\Rightarrow \omega ={\sum }_{i=1}^n{\alpha }_i{y}_i{x}_i\\ \\ \frac{\partial L}{\partial b}=0\Rightarrow {\sum }_{i=1}^n{\alpha }_i{y}_i=0\end{array}$$
将上述结果代入 L 得到:
$$\begin{array}{rl}L(\omega ,b,\alpha )& =\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j-\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j-b\sum _{i=1}^n{\alpha }_i{y}_i+\sum _{i=1}^n{\alpha }_i\\ & =\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\to \text{ 现在只包含 }\alpha \end{array}$$

1. 接着 L 关于 $\alpha$ 极大求解 $\alpha$ （通过 SMO 算法求解，此处不做深入）。
   $$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ \text{ s.t. }& {\alpha }_i\ge 0,i=1,\dots ,n\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

2. 最后便可以根据求解出的 , 计算出 $\omega$ 和 $b$ , 从而得到分类超平面函数。
   $$\begin{array}{rl}{\omega }^{\ast }& =\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\\ b^{\ast }& =-\frac{{\max }_{i:y_i=-1}{\omega }^{\ast T}{x}_i+{\min }_{i:y_i=1}{\omega }^{\ast T}{x}_i}{2}\end{array}$$
   在对新的点进行预测时, 实际上就是将数据点 $x^{\ast }$ 代入分类函数 $f(x)={\omega }^{\prime }x+b$ 中, 若 $f(x)>0$ ,则为正类, $f(x)<0$ , 则为负类, 根据前面推导得出的 $\omega$ 与 $b$ , 分类函数如下所示, 此时便出现了上面所提到的内积形式。
   $$\begin{array}{rl}f(x)& ={\left(\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\right)}^{T}x+b\\ & =\sum _{i=1}^n{\alpha }_i{y}_i⟨x_i,x⟩+b\end{array}$$

这里实际上只需计算新样本与支持向量的内积, 因为对于非支持向量的数据点, 其对应的拉格朗日乘子一定为 0 , 根据最优化理论（ K-T 条件），对于不等式约束 $\mathrm{y}\left({\omega }^{\prime }\mathrm{x}+\mathrm{b}\right)-1⩾0$ ，满足：

$${\partial }_i\left({\mathrm{y}}_i\left({\omega }^T{\mathrm{x}}_i+\mathrm{b}\right)-1\right)=0\Rightarrow \text{ 即总有一个为 }0$$

6.4 核函数

由于上述的超平面只能解决线性可分的问题, 对于线性不可分的问题, 例如: 异或问题, 我们需要使用核函数将其进行推广。一般地, 解决线性不可分问题时, 常常采用咉射的方式, 将低维原始空间映射到高维特征空间, 使得数据集在高维空间中变得线性可分, 从而再使用线性学习器分类。如果原始空间为有限维, 即属性数有限, 那么总是存在一个高维特征空间使得样本线性可分。若 $\varnothing$ 代表一个映射, 则在特征空间中的划分函数变为:

$$f(\mathbf{x})={\mathbf{\omega }}^{\mathrm{T}}\varphi (\mathbf{x})+b$$

按照同样的方法, 先写出新目标函数的拉格朗日函数, 接着写出其对偶问题, 求 L 关于 $\omega$ 和 b的极大, 最后运用 SOM 求解 $\alpha$ 。可以得出:
(1) 原对偶问题变为:
$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j⟨\varphi \left(x_i\right),\varphi \left(x_j\right)⟩\\ \text{ s.t. }& {\alpha }_i\ge 0,i=1,\dots ,n\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$
等价于：

(2) 原分类函数变为：
$$\begin{array}{r}f(x)=\sum _i^n{\alpha }_i{y}_i⟨\varphi \left(x_i\right),\varphi \left(x\right)⟩+b\end{array}$$
等价于：

求解的过程中，只涉及到了高维特征空间中的内积运算，由于特征空间的维数可能会非常大，例如：若原始空间为二维，映射后的特征空间为5维，若原始空间为三维，映射后的特征空间将是19维，之后甚至可能出现无穷维，根本无法进行内积运算了，此时便引出了核函数（Kernel）的概念。

因此，核函数可以直接计算隐式映射到高维特征空间后的向量内积，而不需要显式地写出映射后的结果，它虽然完成了将特征从低维到高维的转换，但最终却是在低维空间中完成向量内积计算，与高维特征空间中的计算等效（低维计算，高维表现），从而避免了直接在高维空间无法计算的问题。引入核函数后，原来的对偶问题与分类函数则变为：
(1) 对偶问题:
$$\begin{array}{ll}{\max }_{\alpha }& {\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K\left(x_i,x_j\right)\\ \text{ s.t. }& {\alpha }_i\ge 0,i=1,\dots ,n\\ & {\sum }_{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

(2) 分类函数:
$$f(x)=\sum _{i=1}^n{\alpha }_i{y}_{i}K\left(x_i,x\right)+b$$
因此，在线性不可分问题中，核函数的选择成了支持向量机的最大变数，若选择了不合适的核函数，则意味着将样本映射到了一个不合适的特征空间，则极可能导致性能不佳。同时，核函数需要满足以下这个必要条件：

由于核函数的构造十分困难，通常我们都是从一些常用的核函数中选择，下面列出了几种常用的核函数：

6.5 软间隔支持向量机

前面的讨论中，我们主要解决了两个问题：当数据线性可分时，直接使用最大间隔的超平面划分；当数据线性不可分时，则通过核函数将数据映射到高维特征空间，使之线性可分。然而在现实问题中，对于某些情形还是很难处理，例如数据中有噪声的情形，噪声数据（outlier）本身就偏离了正常位置，但是在前面的SVM模型中，我们要求所有的样本数据都必须满足约束，如果不要这些噪声数据还好，当加入这些outlier后导致划分超平面被挤歪了，如下图所示，对支持向量机的泛化性能造成很大的影响。

为了解决这一问题，我们需要允许某一些数据点不满足约束，即可以在一定程度上偏移超平面，同时使得不满足约束的数据点尽可能少，这便引出了“软间隔”支持向量机的概念

• 允许某些数据点不满足约束$y({\omega }^{\prime }x+b)\ge 1$；
• 同时又使得不满足约束的样本尽可能少。

这样优化目标变为：

如同阶跃函数，0/1损失函数虽然表示效果最好，但是数学性质不佳。因此常用其它函数作为“替代损失函数”。

图像如下所示：

支持向量机中的损失函数为hinge损失，引入“松弛变量”，目标函数与约束条件可以写为：

书中描述如下：

其中C为一个参数，控制着目标函数与新引入正则项之间的权重，这样显然每个样本数据都有一个对应的松弛变量，用以表示该样本不满足约束的程度，将新的目标函数转化为拉格朗日函数得到：

按照与之前相同的方法，先让L求关于$\omega ，b$以及松弛变量的极小，再使用SMO求出$\alpha$，有：

将$\omega$代入$L$化简，便得到其对偶问题：

将“软间隔”下产生的对偶问题与原对偶问题对比可以发现：新的对偶问题只是约束条件中的$\alpha$多出了一个上限C，其它的完全相同，因此在引入核函数处理线性不可分问题时，便能使用与“硬间隔”支持向量机完全相同的方法。

6.6 支持向量机

对样本 $(\mathbf{x},y)$ , 传统回归模型通常直接基于模型输出 $f(\boldsymbol{x}) $ 与真实输出 $y $ 之间的差别来计算损失, 当且仅当 $f(\mathbf{x})$ 与 $y$ 完全相同时, 损失才为零. 与此不同,支持向量回归(Support Vector Regression, 简称 SVR) 假设我们能容忍 $f(\mathbf{x})$ 与$y$之间最多有$ϵ$的偏差, 即仅当 $f(\mathbf{x})$ 与 $y$ 之间的差别绝对值大于 $ϵ$ 时才计算损失. 如下图所示, 这相当于以 $f(x)$ 为中心, 构建了一个宽度为 2 $ϵ$ 的间隔带, 若训练样本落入此间隔带, 则认为是被预测正确的。


与之前类似，根据拉格朗日与对偶问题的最终转换可得：

6.7核方法

表示定理对损失函数没有限制，对正则化项Ω仅要求单调递增，甚至不要求几是凸函数，意味着对于一般的损失函数和正则化项，优化问题(6.57)的最优解$h\ast (x)$都可表示为核函数$\kappa (x，x_i)$的线性组合；这显示出核函数的巨大威力。人们发展出一系列基于核函数的学习方法，统称为“核方法”(内核
方法)。最常见的，是通过“核化”(即引入核函数)来将线性学习器拓展为非线性学习器。