支持向量机

**支持向量机（Support Vector Machine，简称SVM）**是一种针对二分类任务设计的分类器，它的理论相对神经网络模型来说更加完备和严密，并且效果显著，结果可预测，是非常值得学习的模型。

这一章的内容大致如下：

间隔与支持向量：如何计算空间中任一点到超平面的距离？什么是支持向量？什么是间隔？支持向量机求解的目标是什么？
对偶问题：求取最大间隔等价于怎样的对偶问题？KKT条件揭示出支持向量机的什么性质？如何用SMO算法进行高效求解？为什么SMO算法能高效求解？
核函数：如何处理非线性可分问题？什么是核函数？为什么需要核函数？有哪些常用的核函数？核函数具有什么性质？
软间隔与正则化：如何应对过拟合问题？软间隔和硬间隔分别指什么？如何求解软间隔支持向量机？0/1损失函数有哪些可选的替代损失函数？支持向量机和对率回归模型有什么联系？结构风险和经验风险分别指什么？
支持向量回归：什么是支持向量回归？与传统回归模型有什么不同？支持向量回归的支持向量满足什么条件？
核方法：什么是表示定理？什么是核方法？如何应用？

间隔与支持向量

给定一个二分类数据集，正类标记为+1，负类标记为-1（对率回归中负类标记是0，这点是不同的）。

分类学习试图从样本空间中找到一个超平面，使得该超平面可以将不同类的样本分隔开。但是满足这样条件的平面可能有很多，哪一个才是最好的呢？

支持向量

在SVM中，我们试图找到处于两类样本正中间的超平面，因为这个超平面对训练数据局部扰动的容忍性最好，新样本最不容易被误分类。也就是说这个超平面对未见示例的泛化能力最强。

上图的实线就是划分超平面，在线性模型中可以通过方程来描述，在二维样本空间中就是一条直线。图中的是使用了核函数进行映射，这里暂且不讨论。是线性模型的权重向量（又叫投影向量），也是划分超平面的法向量，决定着超平面的方向。偏置项又被称为 位移项，决定了超平面和空间原点之间的距离。

假设超平面能够将所有训练样本正确分类，也即对于所有标记为+1的点有，所有标记为-1的点有。只要这个超平面存在，那么我们必然可以对和进行适当的线性放缩，使得：

而SVM中定义使得上式等号成立的训练样本点就是支持向量（support vector）（如果叫作支持点可能更好理解一些，因为事实上就是样本空间中的数据点，但因为我们在表示数据点的时候一般写成向量形式，所以就称为支持向量），它们是距离超平面最近的几个样本点，也即上面图中两条虚线上的点（但图中存在比支持向量距离超平面更近的点，这跟软间隔有关，这里暂不讨论）。

在SVM中，我们希望实现的是最大化两类支持向量到超平面的距离之和，那首先就得知道怎么计算距离。怎样计算样本空间中任意数据点到划分超平面的距离呢？

画了一个图，方便讲解。图中蓝色线即超平面，对应直线方程。投影向量垂直于超平面，点对应向量，过点作超平面的垂线，交点对应向量。假设由点指向点的向量为，长度（也即点与超平面的距离）为。有两种方法计算可以计算出的大小：

方法1：向量计算

由向量加法定义可得。

那么向量等于什么呢？它等于这个方向的单位向量乘上，也即有

因此又有。

由于点在超平面上，所以有

由可得，代入直线方程消去：

简单变换即可得到:

又因为我们取距离为正值，所以要加上绝对值符号：

方法2：点到直线距离公式

假设直线方程为，那么有点到直线距离公式：

令，，则可以把写成向量形式。把截距项设为，则直线方程变为，代入距离公式可得：

该式扩展到多维情况下也是通用的。

间隔

前面已经提到，我们希望实现的是最大化两类支持向量到超平面的距离之和，而根据定义，所有支持向量都满足：

代入前面的距离公式可以得到支持向量到超平面的距离为。

定义间隔（margin）为两个异类支持向量到超平面的距离之和：

SVM的目标便是找到**具有最大间隔（maximum margin）**的划分超平面，也即找到使最大的参数和：

约束部分指的是全部样本都被正确分类，此时标记乘上预测值必定是一个大于等于1的数值。

看上去间隔只与有关，但实际上位移项也通过约束影响着的取值，进而对间隔产生影响。

由于最大化等价于最小化，所以可以重写目标函数为：

这便是支持向量机的基本型。

特别地，还有以下定义：

函数间隔：

几何间隔：

对偶问题

式（1）是一个带约束的凸二次规划（convex quadratic programming）问题（凸问题就意味着必定能求到全局最优解，而不会陷入局部最优）。对这样一个问题，可以直接用现成的优化计算包求解，但这一小节介绍的是一种更高效的方法。

首先为式（1）的每条约束添加拉格朗日乘子（对应m个样本的m条约束），得到该问题的拉格朗日函数：

其中，对拉格朗日函数求和的偏导，并令偏导为0可以得到：

将式（3）代入式（2）可以消去和，然后再考虑式（4）的约束就得到了式（1）的对偶问题（dual problem）：

只要求出对偶问题的解，就可以推出和，从而得到模型（不过实际计算时一般不这样做，特别是需要用核函数映射到高唯空间时，因为映射后做内积很困难，而用少量支持向量进行表示，在原始空间进行计算显然更优，这点在后续章节会详细讲解）：

注意，由于式（1）的约束条件是不等式约束，所以求解过程要求满足KKT（Karush-Kuhn-Tucker）条件：

KKT条件说明了，对任何一个样本来说，要么对应的拉格朗日乘子为0，要么函数间隔等于1（即式（1）的约束条件取等号）。如果拉格朗日乘子为0，则这个样本对式（6）毫无贡献，不会影响到模型；如果函数间隔为1，则表明这个样本位于最大间隔边界上，是一个支持向量。它揭示了SVM的一个重要性质：最终模型只与支持向量有关，因此训练完成后，大部分的训练样本都不需保留（支持向量被保留下来用于计算新样本的预测值，也即式（6））。

SMO算法

可以发现对偶问题式（5）是一个二次规划问题，可以使用通用的二次规划算法求解。但问题规模正比于样本数，因此开销相当大。为了避免这个开销，可以使用高效的SMO（Sequential Minimal Optimization）算法。

初始化参数后，SMO算法重复下面两个步骤直至收敛：

选取一对需要更新的变量和
固定和以外的参数，求解式（5）来更新和

怎么选取和呢？

注意到，只要选取的和中有一个不满足KKT条件，那么更新后目标函数的值就会增大。而且违背KKT调成的程度越大，则更新后导致目标函数增幅就越大。

因此，SMO算法先选取一个违背KKT条件程度最大的变量，然后再选一个使目标函数增长最快的变量，但由于找出的开销较大，所以SMO算法采用了一个启发式，使选取的两变量对应的样本之间间隔最大。这样两个变量差别很大，与选取两个相似变量相比，这种方法能为目标函数带来更大的变化，从而更快搜索到全局最大值。

由于SMO算法在每次迭代中，仅优化两个选定的参数，其他参数是固定的，所以会非常高效。此时，可将对偶问题式（5）的约束重写为：

其中，看作是固定的常数。

利用式（7），我们可以把从式（5）中消去，这样就得到了一个单变量二次规划问题，只需考虑这个约束。这样的问题具有闭式解，所以我们连数值优化方法都不需要了，可以直接算出和。

使用SMO算法计算出最优解之后，我们关注的是如何推出和，从而得到最终模型。获得很简单，直接用式（3）就可以了。而位移项则可以通过支持向量导出。

对于任一支持向量，都有函数间隔等于1：

这里的是所有支持向量的下标集（事实上，用所有样本的下标也行，不过非支持向量的拉格朗日乘子等于0，对求和没贡献，这一点前面已经提到了）。

理论上，我们只要选取任意一个支持向量代入式（8）就可以把算出来了。但实际任务中往往采用一种更鲁棒的做法：用所有支持向量求解的平均值。

核函数

如何处理非线性划分

在现实任务中，我们更常遇到的是在原始样本空间中非线性可分的问题。对这样的问题，一种常用的思路是将样本从原始空间映射到一个更高维的特征空间，使得样本在该特征空间中线性可分。幸运的是，只要原始空间是有限维的（也即属性数目有限），那就必然存在一个高维特征空间使样本线性可分。

举个例子，二维平面上若干样本点呈如下分布：

此时要划分两类样本，需要一个非线性的圆型曲线。假设原始空间中两个属性是和，如果我们做一个映射，把样本点都映射到一个三维特征空间，维度取值分别为，和，则得到下面的分布：

可以看到这个时候，我们只需要一个线性超平面就可以将两类样本完全分开了，也就是说可以用前面的方法来求解了。

什么是核函数

在上面的例子中，我们是把每个样本对应的二维的特征向量映射为一个三维的特征向量，假设我们用来表示映射所得的特征向量。则在映射的高维特征空间中，用于划分的线性超平面可以表示为：

类似式（1），可以得到此时的目标函数为：

对应的对偶问题为：

注意到对偶问题中，涉及到的计算，也即和映射到高维特征空间后的内积（比如，，那么内积就等于），由于特征空间维数可能很高，所以直接计算映射后特征向量的内积是很困难的，如果映射后的特征空间是无限维，根本无法进行计算。

为了解决这样的问题，就引入了核函数（kernel function）。

打个比方，假设输入空间是二维的，每个样本点有两个属性和，存在映射将每个样本点映射到三维空间：

给定原始空间中的两个样本点和，则它们映射到高维特征空间后的内积可以写作：

可以看到在这个例子里，高维特征空间中两个点的内积，可以写成一个关于原始空间中两个点的函数 ，这就是核函数。

特别地，上面的例子中，映射用的是多项式核，多项式的次数取2。

为什么需要核函数

这里的例子为了计算方便，映射的空间维数依然很低，这里稍微解释一下为什么需要核函数？假设原始空间是二维的，那么对于两个属性和，取一阶二阶的组合只有5个（也即，，，，）。但当原始空间是三维的时候，仍然取一阶二阶，组合就多达19个了（也即，，，，，，，，，，，，，，，，，，）。随着原始空间维数增长，新空间的维数是呈爆炸性上升的。何况现实中我们遇到的问题的原始空间往往本来就已经是高维的，如果再进行映射，新特征空间的维度是难以想象的。

然而有了核函数，我们就可以在原始空间中通过函数计算（这称为核技巧（kernel trick）），而不必直接计算高维甚至无穷维特征空间中的内积。

使用核函数后，对偶问题式（10）可以重写为：

求解后得到的模型可以表示为：

这条式子表明了模型最优解可通过训练样本的核函数展开，称为支持向量展式（support vector expansion）。

在需要对新样本进行预测时，我们无须计算和新样本映射到高维（甚至无限维）空间后的内积，而是最后一个等式的方式，利用保存下来的训练样本中的支持向量进行求解。

注意，核函数本身不等于映射！！！它只是用来计算两个数据点映射到高维空间之后的内积的一种简便方法。当我们发现数据在原始空间线性不可分时，会有把数据映射到高维空间来实现线性可分的想法，比方说引入原有属性的幂或者原有属性之间的乘积作为新的维度。假设我们把数据点都映射到了一个维数很高甚至无穷维的特征空间，而模型求解和预测的过程需要用到映射后两个数据点的内积，这时直接计算就没辙了。但我们又幸运地发现，原来高维空间中两点的内积在数值上等于原始空间通过某个核函数算出的函数值，无需先映射再求值，就很好地解决了计算的问题了。

核函数的性质

核函数定理：给定一个输入空间，函数是定义在上的对称函数。当且仅当对于任意数据集 , 对应的**核矩阵（kernel matrix）**都是半正定的时候，是核函数。

核矩阵是一个规模为的函数矩阵，每个元素都是一个函数，比如第行列的元素是。也即是说，任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间（Reproducing Kernel Hilbert Space，简称RKHS）”的特征空间。

做映射的初衷是希望样本在新特征空间上线性可分，新特征空间的好坏直接决定了支持向量机的性能，但是我们并不知道怎样的核函数是合适的。一般来说有以下几种常用核函数：

名称	表达式	参数
线性核		-
多项式核		为多项式的次数，d=1时退化为线性核
高斯核（亦称RBF核）		为高斯核的带宽（width）
拉普拉斯核
Sigmoid核		为双曲正切函数，

特别地，文本数据一般用线性核，情况不明可尝试高斯核。

除了这些常用的核函数，要产生核函数还可以使用组合的方式：

若和都是核函数，则也是核函数，其中。
若和都是核函数，则其直积也是核函数。
若是核函数，则对于任意函数，也是核函数。

软间隔与正则化

上一节中，通过利用核函数映射来解决非线性可分的问题，但现实中很难找到合适的核函数，即使某个核函数能令训练集在新特征空间中线性可分，也难保这不是过拟合造成的结果。

比方说上面这张图，黑色虚线是此时的划分超平面，最大间隔很小。但事实上，黑色圆圈圈起的蓝点是一个 outlier，可能是噪声的原因，它偏离了正确的分布。而训练模型时，我们并没有考虑这一点，这就导致把训练样本中的 outlier当成数据的真实分布拟合了，也即过拟合。

但当我们允许这个 outlier 被误分类时，得到的划分超平面可能就如图中深红色线所示，此时的最大间隔更大，预测新样本时误分类的概率也会降低很多。

在实际任务中，outlier 的情况可能更加严重。比方说，如果图中的 outlier 再往右上移动一些距离的话，我们甚至会无法构造出一个能将数据划分开的超平面。

缓解该问题的一个思路就是允许支持向量机在一些样本上出错，为此，引入**软间隔（soft margin）的概念。软间隔是相对于硬间隔（hard margin）**的一个概念，硬间隔要求所有样本都必须划分正确，也即约束：

软间隔则允许某些样本不满足约束（根据约束条件的不同，有可能某些样本出现在间隔内，甚至被误分类）。此时目标函数可以重写为：

其中是0/1损失函数：

它的含义很简单：如果分类正确，那么函数间隔必定大于等于1，此时损失为0；如果分类错误，那么函数间隔必定小于等于-1，此时损失为1。

而则是一个大于0的常数，当趋于无穷大时，式（12）等效于带约束的式（1），因为此时对误分类的惩罚无限大，也即要求全部样本分类正确。当取有限值时，允许某些样本分类错误。

由于0/1损失函数是一个非凸不连续函数，所以式（12）难以求解，于是在实际任务中，我们采用一些凸的连续函数来取替它，这样的函数就称为替代损失（surrogate loss）函数。

最常用的有以下三种：

hinge损失：
指数损失（exponential loss）：
对率损失（logistic loss）：

不妨作图观察比较一下这些损失函数（code文件夹下有实现代码）：

这里有个问题是，书中提到对率损失中指，也即底数为自然对数，但这种情况下对率损失在处不为1，而是0.693。但是书中的插图里，对率损失经过点，此时底数应为2，上面的插图就是按底数为2计算的。

实际任务中最常用的是hinge损失，这里就以hinge损失为例，替代0/1损失函数，此时目标函数式（12）可以重写为：

引入松弛变量（slack variables） ，可以把式（13）重写为：

该式描述的就是软间隔支持向量机，其中每个样本都对应着一个松弛变量，用以表征该样本误分类的程度，值越大，程度越高。

求解软间隔支持向量机

式（14）仍然是一个二次规划问题，类似于前面的做法，分以下几步：

通过拉格朗日乘子法把个约束转换个拉格朗日乘子，得到该问题的拉格朗日函数。
分别对求偏导，代入拉格朗日函数得到对偶问题。
使用SMO算法求解对偶问题，解出所有样本对应的拉格朗日乘子。
需要进行新样本预测时，使用支持向量及其对应的拉格朗日乘子进行求解。

特别地，因为式（14）有两组个不等式约束（一组是函数间隔，一组是），所以该问题的拉格朗日函数有和两组拉格朗日乘子。对求导会得到一条约束式：

有意思的是，软间隔支持向量机的对偶问题和硬间隔几乎没有不同，只是约束条件修改了一下：

这里的不仅要求大于等于0，还要求小于等于。

类似地，由于式（14）的约束条件是不等式约束，所以求解过程要求满足KKT（Karush-Kuhn-Tucker）条件：

KKT条件可以理解为下面几点：

对任意训练样本，要么对应的拉格朗日乘子等于0，要么函数间隔等于1和对应的松弛变量之差。
如果一个样本的拉格朗日乘子等于0，则它对模型没有任何影响，不需要保留。
如果一个样本的拉格朗日乘子大于0，则它是支持向量。
- 如果拉格朗日乘子小于，按照式（15）的约束，，因此，此时函数间隔为1，样本落在最大间隔边界上。
- 如果拉格朗日乘子等于，按照式（15）的约束，，因此。
  - 若，则样本落在间隔内，但依然被正确分类。
  - 若，则样本落在另一个类的间隔外，被错误分类

上图就展示了一个典型的软间隔支持向量机，图中的也即是。图的底部有一个间隔内的蓝点，一个间隔外的红点，对应的就是和两种情况。特别地，在 R. Collobert. 的论文 Large Scale Machine Learning 中，提到取值训练集的大小（也即训练样本的个数）。

支持向量机和逻辑回归的联系与区别

上面用的是hinge损失，不过我们也提到了还有其他一些替代损失函数，事实上，使用对率损失时，SVM得到的模型和LR是非常类似的。

支持向量机和逻辑回归的相同点：

都是线性分类器，模型求解出一个划分超平面
两种方法都可以增加不同的正则化项
通常来说性能相当

支持向量机和逻辑回归的不同点：

LR使用对率损失，SVM一般用hinge损失
在LR的模型求解过程中，每个训练样本都对划分超平面有影响，影响力随着与超平面的距离增大而减小，所以说LR的解受训练数据本身的分布影响；SVM的模型只与占训练数据少部分的支持向量有关，所以说，SVM不直接依赖数据分布，所得的划分超平面不受某一类点的影响
如果数据类别不平衡比较严重，LR需要先做相应处理再训练，SVM则不用
SVM依赖于数据表达的距离测度，需要先把数据标准化，LR则不用（但实际任务中可能会为了方便选择优化过程的初始值而进行标准化）。如果数据的距离测度不明确（特别是高维数据），那么最大间隔可能就变得没有意义
LR的输出有概率意义，SVM的输出则没有
LR可以直接用于多分类任务，SVM则需要进行扩展（但更常用one-vs-rest）
LR使用的对率损失是光滑的单调递减函数，无法导出支持向量，解依赖于所有样本，因此预测开销较大；SVM使用的hinge损失有“零区域”，因此解具有稀疏性（书中没有具体说明这句话的意思，但按我的理解是解出的拉格朗日乘子具有稀疏性，而不是权重向量），从而不需用到所有训练样本。