机器学习十八：支持向量机（LinearSVM）

AI

菌

很多人（包括AI菌）第一次听说 SVM 时都觉得它是个非常厉害的东西，但其实 SVM 本身“只是”一个线性模型。

只有在应用了核方法后，SVM 才会“升级”成为一个非线性模型

不过由于普遍说起 SVM 时我们都默认它带核方法，所以我们还是随大流、称 SVM 的原始版本为 LinearSVM。

不过即使“只是”线性模型，这个“只是”也是要打双引号的——它依旧强大，且在许许多多的问题上甚至要比带核方法的 SVM 要好（比如文本分类）

由于支持向量机内容很多也很重要，所以分为四篇文章来讲，今天首先讲一讲硬间隔最大化

感知机回顾

在进入正题之前，我们先回顾一下感知机，因为 LinearSVM 往简单来说其实就只是改了感知机的损失函数而已，而且改完之后还很像

感知机模型只有权重 w 和偏置 b 这两个参数，它们决定了一张超平面

感知机最终目的是使得没有误差点，即：

其中 D 是训练数据集、y 只能取正负一。

接着我们看感知机模型的损失函数，它的思想是让所有误分类的点(定义为M)到超平面的距离和最小，即最小化下式：

当和w和b成比例的增加，比如,当分子的和w和b扩大N倍时，分母的L2范数也会扩大N倍。

也就是说，分子和分母有固定的倍数关系

所以我们可以固定分子

然后把分母固定为1

从而达到简化函数的目的，但是由感知机损失函数的形式可知，感知机只要求样本被正确分类，而不要求样本被“很好地正确分类”。

这就导致感知机弄出来的超平面（通常又称“决策面”）有点问题，那就是决策面离两坨样本都太近了

从直观上来说，我们希望得到的是这样的决策面：

那么如果我们不是固定分母，改为固定分子，作为分类模型有没有改进呢？

函数间隔与几何间隔

与支持向量

函数间隔和几何间隔

在分离超平面固定为wTx+b=0的时候，|wTx+b| 表示点x到超平面的距离。通过观察 wTx+b和 y 是否同号，我们判断分类是否正确，这些知识我们在感知机模型里都有讲到。这里我们引入函数间隔的概念，定义函数间隔γ′为：

可以看到，对于训练集中m个样本点对应的m个函数间隔的最小值，它就是整个训练集的函数间隔。

函数间隔并不能正常反应点到超平面的距离，在感知机模型里我们也提到，当分子成比例的增长时，分母也是成倍增长。

为了统一度量，我们需要对法向量w加上约束条件，这样我们就得到了几何间隔γ,定义为：

几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离。

支持向量

实际上离超平面很远的点已经被正确分类，我们让它离超平面更远并没有意义。

反而我们最关心是那些离超平面很近的点，这些点很容易被误分类。

如果我们可以让离超平面比较近的点尽可能的远离超平面，那么我们的分类效果会好有一些。SVM的思想起源正起于此。

如下图所示，分离超平面为wTx+b=0，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1）

那么这样的分类超平面是比感知机的分类超平面优的

可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。

 SVM模型目标函数与优化

SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：

一般我们都取函数间隔γ′为1，这样我们的优化函数定义为：

也就是说，我们要在约束条件

最大化

可以看出，这个感知机的优化方式不同，感知机是固定分母优化分子，而SVM是固定分子优化分母，同时加上了支持向量的限制。

由于

的最大化等同于

的最小化。

这样SVM的优化函数等价于：

由于目标函数

是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数。

如果对凸优化和拉格朗日对偶不熟悉，可以参考同时发的另一篇文章《拉格朗日对偶性》

具体的，优化函数转化为：

由于引入了朗格朗日乘子，我们的优化目标变成：

我们的这个优化函数满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解。

也就是说，现在我们要求的是：

从上式中，我们可以先求优化函数对于和w和b的极小值。接着再求拉格朗日乘子α的极大值。

首先我们来求和w和b的极小值，即

这个极值我们可以通过对和w和b分别求偏导数得到：

从上两式子可以看出，我们已经求得了和w和α的关系，只要我们后面接着能够求出优化函数极大化对应的α，就可以求出我们的w了，至于b，由于上两式已经没有b，所以最后的b可以有多个。

好了，既然我们已经求出和w和α的关系，就可以带入优化函数L(w,b,α)消去w了。我们定义:

现在我们来看将w替换为α的表达式以后的优化函数ψ(α)的表达式：

从上面可以看出，通过对w,b极小化以后，我们的优化函数ψ(α)仅仅只有α向量做参数。只要我们能够极大化ψ(α)，就可以求出此时对应的α，进而求出w,b.

对ψ(α)求极大化的数学表达式如下:

可以去掉负号，即为等价的极小化问题如下：

只要我们可以求出上式极小化时对应的α向量就可以求出和w和b了。

具体怎么极小化上式得到对应的α，一般需要用到SMO算法，这个算法比较复杂，我们后面会专门来讲

在这里，我们假设通过SMO算法，我们得到了对应的α的解值 α?。

那么我们根据

可以求出对应的w的值，求b则稍微麻烦一点。注意到，对于任意支持向量

都有

假设我们有S个支持向量，则对应我们求出S个解 b?,理论上这些 b? 都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的

然后将其平均值作为最后的结果。

线性可分SVM的算法过程

这里我们对线性可分SVM的算法过程做一个总结。

输入是线性可分的m个样本(x1,y1),(x2,y2),...,(xm,ym) , 其中x为n维特征向量。y为二元输出，值为1，或者-1.

输出是分离超平面的参数和w?和b?和分类决策函数。

算法过程如下：

    1）构造约束优化问题

    2）用SMO算法求出上式最小时对应的α向量的值α?向量.

    3) 计算

4)  找出所有的S个支持向量,即满足对应的样本

对应的样本

通过

计算出每个支持向量

对应的bs?,计算出这些

所有的bs?对应的平均值即为最终的

这样最终的分类超平面为：

最终的分类决策函数为：

AI

菌

线性可分SVM的学习方法对于非线性的数据集是没有办法使用的

 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分

 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？ 我们在下一节的线性SVM的软间隔最大化里继续讲。