首页
学习
活动
专区
工具
TVP
发布

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

鉴于研究方向,我也会加入这个全新的系列,希望能和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算法实际只包含两部分:1.求解两个变量的二次规划问题;2.启发式选择两个变量。两部分的解析解参考《统计学习方法》,下面直接给出算法简化版的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十分敏感;

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

◆◆◆◆◆

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190120G0D3JJ00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券