机器学习： 支持向量机(SVM)算法
支持向量机(Support Vector Machine,以下简称SVM)，作为传统机器学习的一个非常重要的分类算法，它是一种通用的前馈网络类型，最早是由Vladimir N.Vapnik 和 Alexey Ya.Chervonenkis在1963年提出，目前的版本（soft margin）是Corinna Cortes 和 Vapnik在1993年提出，1995年发表。深度学习（2012）出现之前，如果不考虑集成学习的算法，不考虑特定的训练数据集，在分类算法中的表现SVM说是排第一估计是没有什么异议的。
SVM本来是一种线性分类和非线性分类都支持的二元分类算法，但经过演变，现在也支持多分类问题，也能应用到了回归问题。本篇文章重点讲解线性支持向量机的模型原理和目标函数优化原理。
目录
感知机模型
理解线性支持向量机
一、感知机模型
在讲解SVM模型之前，我们可以先简单了解感知机模型的原理，因为这两个模型有一些相同的地方。在二维平面中，感知机模型是去找到一条直线，尽可能地将两个不同类别的样本点分开。同理，在三维甚至更高维空间中，就是要去找到一个超平面。定义这个超平面为wTx+b=0（在二维平面中，就相当于直线w_1*x+w_1*y+b=0），而在超平面上方的点，定义为y=1，在超平面下方的点，定义为y=-1。而这样的超平面可能是不唯一的，那么感知机是怎么定期最优超平面呢？从感知机模型的目标函数中，我们了解到它是希望让所有误分类的点(定义为M)到超平面的距离和最小。其目标函数如下：
(注：加入y_i是因为点若在超平面下，w*x_i+b为负数，需要乘上对应的y)
当w和b成比例增加了之后，比如都扩大N倍，会发现，分子和分母都会同时扩大N倍，这对目标函数并不影响。因此，当我们将W扩大或缩小一定倍数使得，||w||=1，分子也会相应的扩大或缩小，这样，目标函数就能简化成以下形式：
这个思想将会应用到支持向量机的目标函数优化上，后文将会详细讲解。
二、理解线性支持向量机
2.1线性支持向量机思想
正如上文所说，线性支持向量机的思想跟感知机的思想很相似。其思想也是对给定的训练样本，找到一个超平面去尽可能的分隔更多正反例。不同的是其选择最优的超平面是基于正反例离这个超平面尽可能远。
线性支持向量机模型
从上图可以发现，其实只要我们能保证距离超平面最近的那些点离超平面尽可能远，就能保证所有的正反例离这个超平面尽可能的远。因此，我们定义这些距离超平面最近的点为支持向量（如上图中虚线所穿过的点）。并且定义正负支持向量的距离为Margin。
2.2函数间隔和几何间隔
对SVM思想有一定理解之后，设超平面为wTx+b=0。我们讲解一下函数间隔和几何间隔的区别。
给定一个样本x，|wTx+b|表示点x到超平面的距离。通过观察wTx+b和y是否同号，我们判断分类是否正确。所以函数间隔定义γ'为：
而函数间隔不能正常反应点到超平面的距离，因为当我们等比例扩大w和b的时候，函数间隔也会扩大相应的倍数。因此，我们引入几何间隔。
几何间隔就是在函数间隔的基础下，在分母上对w加上约束（这个约束有点像归一化），定义为γ：
其实参考点到直线的距离，我们可以发现几何间隔就是高维空间中点到超平面的距离，才能真正反映点到超平面的距离。
2.3 SVM目标函数及优化
根据SVM的思想，我们可以知道是要取最大化支持向量到超平面的几何间隔，所以目标函数可以表示为：
在感知机模型最后，我们知道当同时扩大w和b，分子分母都会同样扩大，对目标函数不影响，所以在这里我们将分子(支持向量到超平面的函数间隔)扩大或压缩等于1，则目标函数可以转化为：
但是上式并不是凸函数，不好求解，再进一步转化为：
上式就是一个凸函数，并且不等式约束为仿射函数，因此可以使用拉格朗日对偶去求解该问题。
根据拉格朗日乘子法，引入拉格朗日乘子α，且α≥0我们可以知道，先不考虑min，(2)问题等价于：
然后再考虑min，则有：
应用拉格朗日对偶性，通过求解对偶问题得到最优解，则对偶问题的目标函数为：
这就是线性可分条件下支持向量机的对偶算法。这样做的优点在于：
一是原问题的对偶问题往往更容易求解；
二者可以自然的引入核函数，进而推广到非线性分类问题。
从(4)中，我们可以先求目标函数对于w和b的极小值，再求拉格朗日乘子α的极大值。首先，分别对w和b分别求偏导数，并令为0：
将(5)和(6)代入(4)得到：
对(7)取反得到：
只要我们可以求出(8)中极小化的α向量，那么我们就可以对应的得到w和b，而求解α需要使用SMO算法，由于该算法比较复杂，我们将在下一篇文章专门讲解。假设我们现在已经使用SMO算法得到了最优的α值，记为α_*。
再求b：
对于任一样本(x_s, y_s)有：
注意到任一样本都有y_s^2=1，则将右式的1用y_s^2代：
将(9)代入上式，可以得到：
这样，我们就能够求解得到线性支持向量机的目标函数的各个参数，进而得到最优的超平面，将正负样本分隔开。
一、线性可分的支持向量机存在的问题
前面介绍了当数据集是线性可分的时候，我们可以使用线性可分的支持向量机将数据进行分类（由于隔了很长时间才更新，因此忘记了支持向量机一的读者可以回看支持向量机一讲解）。但是，在现实生活中，还存在着很多数据是线性不可分的，或者说本来是线性可分的数据因为存在一些异常点，使得不能线性划分。
第一种情况如果数据是不能线性可分的话，线性可分的支持向量机是不适用。而第二种情况下，我们通过下图发现，如果在没有A点的情况，我们学到的超平面是黑线所示，但是由于A点的存在，模型会尽可能的拟合所有训练样本点，使得学习到的超平面就是红线所示。但我们可以很清楚的发现黑线是一个更好的超平面，能够将两类样本点分的更开，从而有更好的泛化能力。因此当有异常点的存在时会很大程度影响模型的泛化能力。
二、软间隔最大化的线性支持向量机问题定义
在线性可分的支持向量机中，是需要保证支持向量到超平面的函数间隔大于等于1的（如果忘记了可以回去查看支持向量机一讲解）。为了解决这类数据问题，使得支持向量机有更强的泛化能力，引入了软间隔最大化的支持向量机。所谓的软间隔就是说为每个样本点引入了一个松弛变量ε，这样支持向量到超平面的函数间隔不需要严格保证大于等于1，可以有ε的弹性范围。即约束条件就变成：
当然这个弹性范围不是随便给的，如果样本需要这个弹性范围，那就必须支付一定的代价，因此目标函数会加上每个样本点的这个弹性范围的代价，使得目标函数变成：
其中，C为惩罚参数，C值越大说明模型更加关注这个弹性范围带来的代价，对误分类的样本点的惩罚就越大。
三、优化软间隔最大化的支持向量机
和线性可分的支持向量机的优化方式类似，我们还是将目标函数以及约束条件使用拉格朗日函数转化为无约束问题：
其中μ和α均为拉格朗日乘子，且α_i≥0，μ_i≥0。
那么我们现在要优化的目标函数是：
当满足KKT条件时，以上问题可以等价于求解其对偶问题。
因此我们可以先求对于w、b、ε的极小值，然后再求拉格朗日乘子α和μ。
L对于w、b、ε求偏导，得：
得到以上三个式子，我们就可以将目标函数L进行优化，消除w和b，得：
现在得到的优化目标函数为：
细心的读者可能发现这跟线性可分的支持向量机的式子只是约束条件有不一样，其他都时一样的。另外，因为目标函数中已经没有了μ参数，因此约束条件可以将后面三个约束条件进行合并，得到进一步的优化目标函数：
同样的，求解α还是使用SMO算法即可。假设现在已经求得了一个最优解α_*，那么我们就可以进一步得到w、b的最优解w_*和b_*，即：
其中，(x_s, y_s)是任一个支持向量对应的样本。每一个支持向量对应的样本就可以得到一个b_*，因此最优解b_*也可以是所有支持向量对应的b的平均值。
求得这些参数之后，我们就可以得到分离超平面：
最终的分类决策函数：
四、KKT条件
上一节中目标函数的优化是通过求解对偶问题求得的，为了保证对偶问题的解就是原问题的解，需要满足以下的KKT条件：
五、支持向量
因为支持向量是跟目标函数有关的样本点，因此，在软间隔最大化的支持向量机中，支持向量要比线性可分的支持向量机的情况复杂一些，支持向量或者在间隔边界上，或者在边界内，或者被误分到超平面的另一边。
如果α = 0， 那么样本点在间隔边界上或者被正确分类，因此在间隔边界上的点是支持向量；如果0<α<C，那么样本点是在间隔边界，因为为了保证ε_i=0，y_i*(w'*x_i+b)-1=0，即样本点就在间隔边界，因此这些点都是支持向量；如果α=C，则μ=0，此时ε_i≠0.因为当ε_i≠0会带来一定惩罚代价，因此会尽量保证其等于0，如前面两种情况。但是现在已经没法保证了，因为要保证u*ε=0，u等于0说明ε没法保证。而当ε_i≠0说明这可能是一个异常点了，并且其也是支持向量。当0≤ε_i<1，那么点还是被正确分类，只是落在了超平面和间隔边界之间，如下图样本点2和4；当ε_i＝1，那么点在超平面上，无法正确分类；当ε_i＞1，那么点被误分类，如下图样本点1和3：
软间隔的支持向量
六、合页损失函数(hinge loss)
线性支持向量机的损失函数还有另一种解释，也是大家通常说支持向量机的损失函数时会提及的，原因可能是它有个专业学名，而上面说的软间隔最大化，不是一个学名。Hinge loss的形式如下：
其中有：
其实hingeloss和软间隔最大化中提及的是等价的。
当令：
hingeloss就可以写成：
若取λ = 1/ 2C，则：
可以发现这个形式跟软间隔最大化中的损失函数是等价的。
hingeloss的图形如下图：
合页损失函数