公众号后台回复“python“，立刻领取100本机器学习必备Python电子书
很多人第一次听说 SVM 时都觉得它是个非常厉害的东西，但其实 SVM 本身“只是”一个线性模型。
只有在应用了核方法后，SVM 才会“升级”成为一个非线性模型
不过由于普遍说起 SVM 时我们都默认它带核方法，所以我们还是随大流、称 SVM 的原始版本为 LinearSVM。
不过即使“只是”线性模型，这个“只是”也是要打双引号的——它依旧强大，且在许许多多的问题上甚至要比带核方法的 SVM 要好（比如文本分类）
由于支持向量机内容很多也很重要，所以分为四篇文章来讲，今天首先讲一讲其中的奥秘
在支持向量机原理(一) 线性支持向量机中，我们对线性可分SVM的模型和损失函数优化做了总结。最后我们提到了有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分，本篇就对线性支持向量机如何处理这些异常点的原理方法做一个总结。
1. 线性分类SVM面临的问题
有时候本来数据的确是可分的，也就是说可以用 线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图，本来数据是可以按下面的实线来做超平面分离的，可以由于一个橙色和一个蓝色的异常点导致我们没法按照上一篇线性支持向量机中的方法来分类。
另外一种情况没有这么糟糕到不可分，但是会严重影响我们模型的泛化预测效果，比如下图，本来如果我们不考虑异常点，SVM的超平面应该是下图中的红色线所示，但是由于有一个蓝色的异常点，导致我们学习到的超平面是下图中的粗虚线所示，这样会严重影响我们的分类模型预测效果。
如何解决这些问题呢？SVM引入了软间隔最大化的方法来解决。
2. 线性分类SVM的软间隔最大化
所谓的软间隔，是相对于硬间隔说的，我们可以认为上一篇线性分类SVM的学习方法属于硬间隔最大化。
回顾下硬间隔最大化的条件：
接着我们再看如何可以软间隔最大化呢？
SVM对训练集里面的每个样本引入了一个松弛变量,使函数间隔加上松弛变量大于等于1，也就是说：
对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量, 对应了一个代价，这个就得到了我们的软间隔最大化的SVM学习条件如下：
这里,为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。越大，对误分类的惩罚越大，越小，对误分类的惩罚越小。
也就是说，我们希望尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。
这个目标函数的优化和上一篇的线性可分SVM的优化方式类似，我们下面就来看看怎么对线性分类SVM的软间隔最大化来进行学习优化。
3. 线性分类SVM的软间隔最大化目标函数的优化
和线性可分SVM的优化方式类似，我们首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：
其中 ,均为拉格朗日系数。
也就是说，我们现在要优化的目标函数是：
这个优化目标也满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：
我们可以先求优化函数对于的极小值, 接着再求拉格朗日乘子和 的极大值。
首先我们来求优化函数对于的极小值，这个可以通过求偏导数求得：
好了，我们可以利用上面的三个式子去消除和了。
其中，(1)式到(2)式用到了, (2)式到(3)式合并了同类项，(3)式到(4)式用到了范数的定义, (4)式到(5)式用到了上面的， (5)式到(6)式把和样本无关的提前，(6)式到(7)式合并了同类项，(7)式到(8)式把和样本无关的提前，(8)式到(9)式继续用到，（9）式到(10)式用到了向量的转置。由于常量的转置是其本身，所有只有向量被转置，（10）式到(11)式用到了上面的，（11）式到(12)式使用了的乘法运算法则，（12）式到(13)式仅仅是位置的调整。
仔细观察可以发现，这个式子和我们上一篇线性可分SVM的一样。唯一不一样的是约束条件。现在我们看看我们的优化目标的数学形式：s.t.
对于，，这3个式子，我们可以消去，只留下，也就是说。同时将优化目标函数变号，求极小值，如下：
这就是软间隔最大化时的线性可分SVM的优化目标形式，和上一篇的硬间隔最大化的线性可分SVM相比，我们仅仅是多了一个约束条件。我们依然可以通过SMO算法来求上式极小化时对应的向量就可以求出和了。
4. 软间隔最大化时的支持向量
在硬间隔最大化时，支持向量比较简单，就是满足就可以了。根据KKT条件中的对偶互补条件，如果则有即点在支持向量上，否则如果则有，即样本在支持向量上或者已经被正确分类。
在软间隔最大化时，则稍微复杂一些，因为我们对每个样本引入了松弛变量。我们从下图来研究软间隔最大化时支持向量的情况，第i个点到对应类别支持向量的距离为。根据软间隔最大化时KKT条件中的对偶互补条件我们有：
a) 如果,那么,即样本在间隔边界上或者已经被正确分类。如图中所有远离间隔边界的点。
b) 如果,那么,即点在间隔边界上。
c) 如果，说明这是一个可能比较异常的点，需要检查此时
i)如果,那么点被正确分类，但是却在超平面和自己类别的间隔边界之间。如图中的样本2和4.
ii)如果,那么点在分离超平面上，无法被正确分类。
iii)如果,那么点在超平面的另一侧，也就是说，这个点不能被正常分类。如图中的样本1和3.
5. 软间隔最大化的线性可分SVM的算法过程
这里我们对软间隔最大化时的线性可分SVM的算法过程做一个总结。
输入是线性可分的m个样本,其中x为n维特征向量。y为二元输出，值为1，或者-1.
输出是分离超平面的参数和和分类决策函数。
算法过程如下：
1）选择一个惩罚系数, 构造约束优化问题 s.t.
2）用SMO算法求出上式最小时对应的向量的值向量.
3) 计算
4) 找出所有的S个支持向量对应的样本，通过 ，计算出每个支持向量对应的,计算出这些. 所有的对应的平均值即为最终的
这样最终的分类超平面为：，最终的分类决策函数为：
6. 合页损失函数
线性支持向量机还有另外一种解释如下：
其中称为合页损失函数(hinge loss function)，下标 表示为：
也就是说，如果点被正确分类，且函数间隔大于1，损失是0，否则损失是,如下图中的绿线。我们在下图还可以看出其他各种模型损失和函数间隔的关系：对于0-1损失函数，如果正确分类，损失是0，误分类损失1， 如下图黑线，可见0-1损失函数是不可导的。对于感知机模型，感知机的损失函数是，这样当样本被正确分类时，损失是0，误分类时，损失是，如下图紫线。对于逻辑回归之类和最大熵模型对应的对数损失，损失函数是, 如下图红线所示。
线性可分SVM通过软间隔最大化，可以解决线性数据集带有异常点时的分类处理，但是现实生活中的确有很多数据不是线性可分的，这些线性不可分的数据也不是去掉异常点就能处理这么简单。那么SVM怎么能处理中这样的情况呢？我们在下一篇就来讨论线性不可分SVM和核函数的原理。
至此今天的新内容变讲结束啦！如果有遗忘的知识可以看下昨天的内容，如下：
前情回顾
支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年，但是自一诞生便由于它良好的分类性能席卷了机器学习领域，并牢牢压制了神经网络领域好多年。如果不考虑集成学习的算法，不考虑特定的训练数据集，在分类算法中的表现SVM说是排第一估计是没有什么异议的。
SVM是一个二元分类算法，线性分类和非线性分类都支持。经过演进，现在也可以支持多元分类，同时经过扩展，也能应用于回归问题。本系列文章就对SVM的原理做一个总结。本篇的重点是SVM用于线性分类时模型和损失函数优化的一个总结。
1. 回顾感知机模型
在感知机原理小结中，我们讲到了感知机的分类原理，感知机的模型就是尝试找到一条直线，能够把二元数据隔离开。放到三维空间或者更高维的空间，感知机的模型就是尝试找到一个超平面，能够把所有的二元类别隔离开。对于这个分离的超平面，我们定义为wTx b=0，如下图。在超平面wTx b=0上方的我们定义为y=1，在超平面wTx b=0下方的我们定义为y=−1。可以看出满足这个条件的超平面并不止一个。那么我们可能会尝试思考，这么多的可以分类的超平面，哪个是最好的呢？或者说哪个是泛化能力最强的呢?
接着我们看感知机模型的损失函数优化，它的思想是让所有误分类的点(定义为M)到超平面的距离和最小，即最小化下式：
当w和b和b成比例的增加，比如,当分子的w和b扩大N倍时。也就是说，分子和分母有固定的倍数关系。那么我们可以固定分子或者分母为1，然后求另一个即分子自己或者分母的倒数的最小化作为损失函数，这样可以简化我们的损失函数。在感知机模型中，我们采用的是保留分子，固定分母||w||2=1|，即最终感知机模型的损失函数为：
如果我们不是固定分母，改为固定分子，作为分类模型有没有改进呢？
这些问题在我们引入SVM后会详细解释。
2. 函数间隔与几何间隔
在正式介绍SVM的模型和损失函数之前，我们还需要先了解下函数间隔和几何间隔的知识。
在分离超平面固定为wTx b=0的时候，|wTx b|表示点x到超平面的相对距离。通过观察wTx b和y是否同号，我们判断分类是否正确，这些知识我们在感知机模型里都有讲到。这里我们引入函数间隔的概念，定义函数间隔γ′为：
可以看到，它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中m个样本点对应的m个函数间隔的最小值，就是整个训练集的函数间隔。
函数间隔并不能正常反应点到超平面的距离，在感知机模型里我们也提到，当分子成比例的增长时，分母也是成倍增长。为了统一度量，我们需要对法向量w加上约束条件，这样我们就得到了几何间隔γ,定义为：
几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离。
3. 支持向量
在感知机模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都被准确分类。但是实际上离超平面很远的点已经被正确分类，它对超平面的位置没有影响。我们最关心是那些离超平面很近的点，这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面，最大化几何间隔，那么我们的分类效果会更好一些。SVM的思想起源正起于此。
如下图所示，分离超平面为wTx b=0，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1），那么这样的分类超平面是比感知机的分类超平面优的。可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。
支持向量到超平面的距离为1/||w||2,两个支持向量之间的距离为2/||w||2。
4. SVM模型目标函数与优化
SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：
一般我们都取函数间隔γ′为1，这样我们的优化函数定义为：
也就是说，我们要在约束条件下，最大化1/||w||2。可以看出，这个感知机的优化方式不同，感知机是固定分母优化分子，而SVM是固定分子优化分母，同时加上了支持向量的限制。
由于1||w||2的最大化等同于1/||w||2的最小化。这样SVM的优化函数等价于：
由于目标函数12||w||22是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数，这和最大熵模型原理小结中讲到了目标函数的优化方法一样。具体的，优化函数转化为：
由于引入了朗格朗日乘子，我们的优化目标变成：
和最大熵模型一样的，我们的这个优化函数满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解。如果对凸优化和拉格朗日对偶不熟悉，建议阅读鲍德的《凸优化》。
也就是说，现在我们要求的是：
从上式中，我们可以先求优化函数对于w和bw和b的极小值。接着再求拉格朗日乘子αα的极大值。
首先我们来求L(w,b,α)L(w,b,α)基于w和bw和b的极小值，即min(w)L(w,b,α)。这个极值我们可以通过对w和b分别求偏导数得到：
从上两式子可以看出，我们已经求得了w和α的关系，只要我们后面接着能够求出优化函数极大化对应的α，就可以求出我们的w了，至于b，由于上两式已经没有b，所以最后的b可以有多个。
好了，既然我们已经求出w和α的关系，就可以带入优化函数L(w,b,α)消去w了。我们定义:
现在我们来看将w替换为α的表达式以后的优化函数ψ(α)的表达式：
其中，(1)式到(2)式用到了范数的定义||w||22=wTw, (2)式到(3)式用到了上面的w=∑i=1mαiyixi， (3)式到(4)式把和样本无关的wT提前，(4)式到(5)式合并了同类项，(5)式到(6)式把和样本无关的bb提前，(6)式到(7)式继续用到w=∑i=1mαiyixi，（7）式到(8)式用到了向量的转置。由于常量的转置是其本身，所有只有向量xixi被转置，（8）式到(9)式用到了上面的∑i=1mαiyi=0，（9）式到(10)式使用了(a b c …)(a b c …)=aa ab ac ba bb bc …的乘法运算法则，（10）式到(11)式仅仅是位置的调整。
从上面可以看出，通过对w,b极小化以后，我们的优化函数ψ(α)仅仅只有α向量做参数。只要我们能够极大化ψ(α)，就可以求出此时对应的α，进而求出w,b.
对ψ(α)求极大化的数学表达式如下:
可以去掉负号，即为等价的极小化问题如下：
只要我们可以求出上式极小化时对应的α向量就可以求出w和b了。具体怎么极小化上式得到对应的α，一般需要用到SMO算法，这个算法比较复杂，我们后面会专门来讲。在这里，我们假设通过SMO算法，我们得到了对应的α的值α∗。
那么我们根据w=∑i=1mαiyixi，可以求出对应的w的值
求b则稍微麻烦一点。注意到，对于任意支持向量(xx,ys)，都有
假设我们有S个支持向量，则对应我们求出S个b∗,理论上这些b∗都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的b∗s，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM，b的值是有唯一解的，也就是这里求出的所有b∗都是一样的，这里我们仍然这么写是为了和后面加入软间隔后的SVM的算法描述一致。
怎么得到支持向量呢？根据KKT条件中的对偶互补条件α∗i(yi(wTxi b)−1)=0，如果αi>0则有
yi(wTxi b)=1 即点在支持向量上，否则如果αi=0则有yi(wTxi b)≥1，即样本在支持向量上或者已经被正确分类。
5. 线性可分SVM的算法过程
这里我们对线性可分SVM的算法过程做一个总结。
输入是线性可分的m个样本(x1,y1),(x2,y2),...,(xm,ym),其中x为n维特征向量。y为二元输出，值为1，或者-1.
输出是分离超平面的参数w∗和b∗和分类决策函数。
算法过程如下：
1）构造约束优化问题
2）用SMO算法求出上式最小时对应的α向量的值α∗向量.
3) 计算w∗=∑i=1mα∗iyixi
线性可分SVM的学习方法对于非线性的数据集是没有办法使用的， 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分， 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？我们在下一节的线性SVM的软间隔最大化里继续讲。
