机器学习系列：支持向量机

鉴于研究方向，我也会加入这个全新的系列，希望能和zhang88a的内容相互补充。写作目的主要是方便日后对算法理论部分的复习，因此很多概念不会出现在内容中。由于内容会从理论出发，可能会有公式推导以及造轮子的代码，但怎么开车是肯定会介绍的。

预计阅读时间：15min

序

封面中，支持向量机的作者Vapnik这样写着：All your bayes are belong to us。虽然是句玩笑话，但支持向量机在深度神经网络出现以前，一直是机器学习的主流技术，并且是少有的具有完备数学理论的机器学习方法。在学习中可以很清楚的看到统计学习理论和凸优化的概念。本文将从线性分类面出发，完整地推导出支持向量机，并介绍其对偶问题和核函数地使用，然后介绍其求解算法序列最小优化算法，并给出其matlab实现，最后介绍sklearn中有关SVM的使用。

目录

从线性分类面到线性可分支持向量机

支持向量机的求解

核函数与非线性可分支持向量机

分类器构造

序列最小优化算法SMO

sklearn中的SVM

◆◆◆◆◆

1. 从线性分类面到线性可分支持向量机

线性分类面的函数形式为

其中，w和b分别为分类面的法向量和偏置。

几何解释：线性分类器的作用就是把输入样本投影在法向量上，然后给一个阈值进行分类。

直观解释：如下图，在二维情况下线性分类器就是一条直线，在三维情况下是一个平面，更高维的情况就是超平面。

其中分类超平面为

用于判断类别的分类决策函数为

能正确分类的分类面有无数个，但其中样本与分类面距离最大的只有一个，该最大间隔的分类器满足分类器构造的直观想象，如下图所示。

利用最大间隔的分类器，可以比较容易地引出SVM。从上图很容易得到关于间隔的几点表示，以及分类面与两侧样本之间的间隔

直接最大化该间隔，作为优化问题既不是凸问题也不是凹问题，很难求解。对其进行等效变换，得到等价的凸优化问题

该问题是一个标准的二次规划问题(目标函数为二次型，约束函数为仿射函数)，现有的凸优化工具包cvx能直接对其求解，而求解出来的w和b就是我们想要的分类器函数。

如果真的这么方便的话，那关于线性支持向量机的介绍到这里就该完结了。事实上，当数据量增大时，我们的约束函数同样在增多，在约束函数较多时，cvx工具包求解的过程是很慢很慢的，因此，在后面的内容中会专门介绍svm的快速求解算法。

◆◆◆◆◆

2. 支持向量机求解

第一部分以给出线性可分支持向量机的基本形式，下面利用凸优化理论对该二次规划问题进行求解。

对于约束优化问题，利用Lagrange乘子得到其对应的Lagrange函数和Lagrange对偶函数分别为

我们的目标为极小化Lagrange函数，因此对w和b分别求导，并令其导数为0，可以得到

从上式就可以看出，权值w实际上可以理解为输入样本之和。但其只依赖少量Lagrange乘子不为0的样本，即支持向量。将上式代回Lagrange函数，就可以得到其Lagrange对偶函数。根据定义，对偶函数为原函数的下界，为了求出对偶函数最好的下界，即最大的下界，我们可以得到原始问题的对偶优化问题为

此时的优化变量变为Lagrange乘子。分析原始Lagrange函数的最优性条件以及对偶问题的最优性条件，即导数为0的条件，可以得到其KKT条件为

对条件5进行分析，可以得到如下结论：

边界上的点，乘子不为0，括号部分为0

非边界上的点，乘子为0

因此，只有边界上的点对权重w有贡献，因此被称为支持向量。上述结论同样是SMO算法的理论指导。

将数据对(x,y)带入Lagrange对偶函数，可以得到对偶问题关于Lagrange乘子的函数。求该对偶问题的最大值，即要求其导数为0，可以得到关于Lagrange乘子的线性方程组，因而得到Lagrange乘子。将其带入前面的式子进而可以得到权值w和偏置b，完成对支持向量机的求解。

可以看出，利用优化理论可以从解析的角度求出支持向量机的理论可行解，也是调用cvx工具包的求解思路，这是很多机器学习方法，尤其是现有的神经网络类方法做不到的。

◆◆◆◆◆

3. 核函数与非线性可分支持向量机

在第二部分的推导中已经得到硬间隔支持向量机的对偶问题形式。对于软间隔支持向量机，原问题目标函数增加一项罚函数，约束条件增加一项不等约束；但对偶问题中目标函数形式完全相同，并对Lagrange增加一个约束，推导过程完全相同，下面直接给出软间隔支持向量机的对偶问题为

在对偶问题中，样本x仅以内积的形式存在。

有关核函数的概念对使用影响不大，不做介绍。将内积替换为核函数的直观想法如下图，原始数据在低维空间可能是线性不可分的，但将其映射到高维空间或许能够获得良好的分类性能。

将内积变为核函数，实际上变为高维空间的内积！使用中直接将样本内积进行替换即可。

引入核函数后，目标函数变为

但具体的求解过程没有发生改变。

线性支持向量机和非线性支持向量机(核支持向量机)在形式和使用上是完全相同的。可以很容易地将核函数使用到支持向量机中。

◆◆◆◆◆

4. 分类器构造

这部分内容很简单，只是为了提醒自己不忘初心。我们的目标是获得最大间隔的分类器，前面推导出了分类器权值和偏置的求解，下面给出分类器的具体形式。

对于线性SVM，分类器为

对于非线性的Kernel SVM，将内积简单替换就可以得到相应的分类器为:

可以看出，分类器实际上是支持向量和测试样本的内积，因此在预测时的速度是很快的。

◆◆◆◆◆

5. 序列最小优化算法

现在我们已经知道想要求解的问题为如下的对偶问题

该问题同样是凸的二次规划问题，但其变量和约束数量较大，直接使用cvx工具包求解会耗费大量时间。因此提出序列最小优化算法SMO，其本质可以理解为只针对两个变量的二次规划算法。作为一种启发式算法，其基本思路为：如果所有变量的解都满足KKT条件，那么该优化问题就被解决了。否则，选择两个变量而固定其他变量，只针对这两个变量构建二次规划问题。两个变量的选择如下：

违反KKT条件最严重的变量；

根据约束条件自动确定的变量。

因此，SMO算法实际只包含两部分：１.求解两个变量的二次规划问题；２.启发式选择两个变量。两部分的解析解参考《统计学习方法》，下面直接给出算法简化版的matlab实现。

SMO算法:

初始化lagrange乘子为0；

根据要求选择两个变量，并求解两个变量的二次规划问题；

判断精度是否满足要求，以及是否所有变量都满足KKT条件，若是，则输出，否则，继续选择新的变量，继续2。

调用该SMO算法进行二分类，可以得到如下结果，

造轮子部分到此结束，下面开始介绍怎么使用sklearn库函数开车，日常使用中还是以方便的库函数为主，并针对自己的特殊需求调整。

◆◆◆◆◆

6. sklearn中的SVM

欢迎直接从这部分内容开始起飞。

使用数据集为鸢尾花数据集，完整数据集参考zhang88a在KNN中的图，这里选择的特征及其直观显示如下图所示。

左图为三类鸢尾花的特征分布情况，右图表示我们只判断是否为标签为0的鸢尾花。

下面直接导入svc模块，对上述右图数据进行分类，并画出决策函数。

决策函数即前面介绍的分类器

C是我们在软间隔支持向量机中给出的一个超参数，C越大，表示边界越硬，越不允许样本在两个边界之间出现，效果见上图。

换一组鸢尾花特征，可以得到如下图所示的非线性可分的数据集

对于非线性可分情况，我们要使用核函数支持向量机。下面看一下多项式核以及高斯核在不同超参数下的结果。

结果见下图，图中的黑色实线为决策函数，黑色虚线为支持向量所在边界，黑色点为支持向量。

a. 不同阶数的多项式核，以及不同的参数C

b. 不同‘半径’的高斯核，以及不同的参数C

结论分析：

gamma越大，每一个样本的影响范围就越小；反之影响范围越大。

C越大，越不允许错误分类的样本出现，越容易过拟合；反之可以允许错误分类，越容易欠拟合。

degree越大，阶数越高，越容易过拟合，且计算量越大。

对不同的gamma、C、degree分析可知，如果模型过拟合，应该减小它们，反之应该增加它们。

SVM优劣讨论：

优势：

模型占用内存很小，仅依赖几个支持向量；

模型预测速度快，只需要测试样本和支持向量做内积；

核函数支持向量机能适应多种不同的数据分布；

对高维数据的学习能力优秀，即使特征数目多过样本数目

劣势：

对参数C十分敏感；

计算量在数据量大的时候很大

◆◆◆◆◆

到此，支持向量机分类器部分的内容就完成了，小伙伴们有神马想法的话，欢迎在下方留言~~