【干货】支持向量机SVM算法推演

【干货】支持向量机SVM算法推演

来源：海阔心

尽管早就听说SVM比较复杂，当真正下笔推导时其复杂程度还是出乎意料，上周花了整整两天的时间把支持向量机分类算法的每一个细节推导了一遍，但很遗憾智力及时间有限，最核心的SMO算法仍然有几个公式没能推导出为什么，因此本文将只推导出一个完整的SVM算法，SMO部分留待日后再续。

本文旨在进一步理顺SVM的算法思路，加深理解，关于SMO算法、KKT法则以及核函数的介绍并不细致（以后有机会逐个拿出来介绍），算是一个粗略的学习笔记，欢迎各位大神指正、拍砖、给出好的建议，无论是关于SVM的还是其他算法抑或机器学习的任何方面。

当然，关于SVM的内容已经有很多经典的论文、书籍包括博文问世，最基本的原理部分免不了会有重复，文末会给出本文的参考文献及其版本。好了，步入正题。

一、逻辑回归

支持向量机（support vector machine），简称SVM，是一种二类分类模型。理解SVM需要先理解逻辑回归，我们先简单回顾逻辑回归的知识，再引出SVM。

给出一堆n维样本数据（x,y）其中x是表示样本的特征数据，y表示样本的类别标签（-1,1），此处-1和1并无特别含义，仅仅是代表两个不同的类别，SVM分类器的学习目标便是在这堆样本数据中找到一个超平面可以将这些样本分成两类，这个超平面的方程可以表示为:

逻辑回归的目的是通过训练从样本数据中学习特征，训练出一个0/1分类器，通常以样本所有特征列（不包括标签列，假设标签为0,1）为自变量，表前列为作为因变量，模型对因变量的预测结果是从负无穷到正无穷。成熟做法是用logistic函数将预测结果映射到（0,1）上，映射后的值被认为是y=1的概率。

假设函数

其中x是n维自变量，函数g即为logistic函数，而

的图像如下：

可以看到，logistic 函数将因变量映射到（0,1）范围内，上述假设函数即为y=1的概率

那么当新的样本点到来时，我们只需要算

即可，若大于0.5,就认为是属于y=1的类，反之属于y=0的类。

下面我们对逻辑回归做一个变形，首先将标签由（0,1）变为（-1,1），然后将

（

）中的替换为b，最后将后面的

替换为

，则有了

，由此看来，除了将因变量标签由（0,1）变为（-1,1）外，逻辑回归函数与SVM分类器函数

并没有什么区别。我们通过以下映射函数将y映射到（-1,1）

二、函数间隔（function margin）和几何间隔（geometrical margin）

对于一个样本点，在超平面（w,b）确定的情况下，|w*x+b|可以表示该样本点到超平面的远近（注意不是距离），而通过观察w*x+b与标签y的符号是否一致可以判断分类器分类的正确性，于是，引出函数间隔的概念：

而超平面（w,b）关于所有样本点的函数间隔最小值便为超平面（w,b）关于训练数据集（xi,yi）的函数间隔(其中x表示特征，y表示类别标签，i表示第i个样本)：

=min

i  (i=1，...n)

此时若成比例的改变w和b（比如2w,2b），那么函数间隔也会同比例改变，而此时超平面并未发生改变，间隔却是不确定的！因此需要引出几何间隔，才能更精准的描述样本点到超平面度的距离。

假定对于一个点x，其垂直投影到超平面上的对应点是x0, w是垂直于超平面的一个向量，

为样本x到超平面的距离，如下图：

由平面几何知识知道有：

其中||w||是w的二阶范数，

为单位向量，又有x0位于超平面上，满足f(x0)=0, 带入

有

即

。

两边同时乘以

， 再有

和

可以算出：

令

乘上对应的类别y，即得出几何间隔的定义：

由函数间隔和几何间隔的定义知道，几何间隔就是函数间隔除以||w||,而函数间隔y*(w*x+b)其实就是|f(x)|, 只是认为定义的一个度量，而几何间隔才是直观上点到超平面的距离。

三、最优间隔分类器

对数据点进行分类时，数据点距离超平面的间隔越大则超平面分类的确信度就越高，因此我们需要让找到的超平面使得数据点距离超平面的间隔最大化，如下图间隔：

因为函数间隔

会因为w和b的缩放而等比例缩放，因此认为几何间隔比较适合用来最大化“间隔”，则最大间隔分类器的目标函数可以为：

根据函数间隔的定义有：

又有几何间隔的定义有：

若令函数间隔

为1，则易知

=1/||w||，且

，那么目标函数转化为：

如下图中间的实线就是所找的超平面，两条虚线间隔边界上的点就是支持向量，这些支持向量在虚线间隔边界上，那么满足：

，而所有不在虚线上的点有：

。

四、原始问题转化为对偶问题

前文已得到最优化函数：

等价于：

显然目标函数是二次的，又有线性约束条件，它是一个凸二次规划问题，我们可以使用现有的优化包求解，也可以通过拉格朗日对偶性变换到对偶变量的优化问题，即通过求解与原问题等价的的对偶问题来求解超平面。

定义拉格朗日函数（不知道的请自行查阅高等数学或百度百科）：

令：

在满足约束条件的情况下最小化1/2||w||^2,目标函数变为：

表示此问题的最优值，同原始问题等价。为易于求解，我们调换最大和最小的位置：

下面可以先求L对w,b的极小值，再求L对

的极大。

五、对偶问题的求解

（1）、先固定

，让L对w,b求偏导：

将偏导结果带入L函数有：

化简可得（此化简过程用到了线性代数的转置和乘积运算，感兴趣可以自己推导，并不难）：

此时拉格朗日函数只包含一个变量

（求出了

就能求出w,b）。

（2）、求拉格朗日函数对

的极大

由（1）得知：

这样求出

，又有可以求出w：

那么只剩下b可以这样表示

这样就得出了分离超平面和分类函数。

在L对w,b最小化以及对

最大化时，最后一步可以用SMO算法求解拉个让日乘子

，本文并不推导SMO算（以后会单独拿出一篇的章节来介绍和推导SMO），下面介绍非线性求解情况，并以此引入核函数。

六、线性不可分情况

通过以上推导我们知道所谓超平面其实就是把自变量x带入：

得到结果后以正负号划分分类。并有w:

分类函数为：

仔细观察分类函数，对于一个新的需要预测的点来说，只需要计算它与训练数据点的内积即可。另外回忆一下我们之前得到的一个目标函数：

注意到若数据点xi是支持向量的话，上式中红色部分为0（支持向量的函数间隔为1），而所有非支持向量的函数和间隔均大于1，红色部分大于0，

是非负的，为满足最大化，非支持向量的

均必须为0，因此针对新点的预测只需要针对少量支持向量进行计算即可。

目前我们的支持向量机分类器还只能处理线性分类，为推广到非线性形式，下面稍稍介绍下核函数。

七、核函数

对于非线性数据分类的问题，SVM的通常做法是用一个和函数将数据由低维空间映射到高维空间，在高维空间中解决原始空间中线性不可分问题。

如下图一堆数据点在二维空间中不可分，映射带到三维空间中划分：

由于对偶形式是线性学习器的一个重要性质，这意味着假设集可以表示为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：

若可以在特征空间中直接计算内积〈φ(xi · φ(x)〉，就像在原始输入点的函数中一样，将两个步骤融合到一起建立一个非线性的学习器，这样直接计算法的方法称为核函数方法。

八、引入松弛变量处理 outliers

现实世界中的数据集常常是伴随着大量的噪音，他们偏离正常的位置很远，我们成为outliers，这些outliers对超平面的划分会有很大的干扰，因为超平面本身就是由几个支持向量决定的，如图：

用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己本应所在的那个半空间，若直接忽略掉它，超平面还是挺好的，但是由于 outlier 的出现，分隔超平面被挤歪，变成途中黑色虚线，同时间隔也相应变小了。若这个 outlier 再往右上移动一点，也许我们将无法建立成超平面。

在原本我们的约束条件上考虑到outliers的因素：

为松弛变量，表示我们能够容忍对应的数据点偏离函数间隔的程度，松弛变量不能无限大，在目标函数加上一项约束他：

其中C是一个常数，用来平衡“寻找最优超平面”和“保证数据点偏差总量最小”这两个约束的权重。将新的约束条件加入到目标函数又有新的拉格朗日函数：

同样转为对偶问题，让L先对w,b和

极小化，

将以上结果带入L函数然后化简，你会惊奇的发现松弛变量竟然消失了！得到了和之前一样的目标函数：

上面化简得到

，又有

，因此有

，那么整个目标函数和约束条件可以写做：

把目标函数和约束条件同之前对比发现只是对

的约束多了一个C，Kernel 化的非线性形式只需要把（xi,xj）换成K（xi,xj）。这样一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机就终于介绍完毕了。

SVM本质上是一个分类方法，用w^T+b定义分类函数，于是求w、b，为寻最大间隔，引出1/2||w||^2，继而引入拉格朗日因子，化为对拉格朗日乘子

的求解（求解过程中会涉及到一系列最优化或凸二次规划等问题），如此，求w.b与求

等价，而

的求解可以用一种快速学习算法SMO，至于核函数，是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。

关于SVM的深层理论我也不是理解的很透彻，本文仅作学习笔记之用，还有很多细节需要来回追究，还是那句话，欢迎各位大神指正、拍砖、给出好的建议，无论是关于SVM的还是其他算法抑或机器学习的任何方面。

参考文献：

《深度学习》周志华版本

《统计学习方法》李航

《数据挖掘导论》Pang-Ning Tan, Michacl Sterinbach, Vipin Kumar

《支持向量机导论》Nello Cristianini, John Shawe-Taylor

了解更多：

http://blog.pluskid.org/?page_id=683

http://www.cnblogs.com/jerrylead/

http://blog.csdn.net/johnnyconstantine/article/details/46335763