关灯

学习SVM(二) 如何理解支持向量机的最大分类间隔

[复制链接]
admin 发表于 2019-1-20 13:13:45 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
 

SVM算法在在1995年正式发表,在针对中小型数据规模的分类任务上有着卓越的效果,同时有着完整的理论证明,在20世纪末的几年和21世纪初的10年完胜神经网络,吴恩达在其2003年的《Machien learning》公开课上用两节课的时间对其进行讲解,而神经网络讲解了20min左右。就是这个算法把神经网络按在地上摩擦了大概15年的时间,直到深度学习的兴起。但即便这样,现在SVM算法依旧被广泛的使用。 


SVM大概的可以不确切的分为三个程度理解: 
(1)线性可分情况下的线性分类器,这是最原始的SVM,它最核心的思想就是最大的分类间隔(margin maximization); 
(2)线性不可分情况下的线性分类器,引入了软间隔(soft margin)的概念; 
(3)线性不可分情况下的非线性分类器,是SVM与核函数(kernel function)的结合。 
在下面只会第一部分的内容。

  什么是最大分类间隔

SVM最大分类间隔的灵感来自于一个非常符合直觉的观察,如果存在两类数据,数据的特征是二维的,那么我们就可以把数据画在一个二维平面上,此时我想找到一个决策面(决策边界)去将这两类数据分开。如下图所示: 
1532929874646816232.jpg

 
理论上这个决策边界有无数种选择,就像图中画出的四条黑色的线,都能实现分类,但是哪一种是最好的分类方式呢?SVM算法认为在上图中靠近决策平边界的点(正负样本)与决策边界的距离最大时,是最好的分类选择: 
1532929884860430432.jpg

 
上图中红色的线就是要优化的目标,它表征了数据到决策边界的距离,这个距离就是所谓的最大分类间隔。同时在上面的几个数据,如果靠近两侧的数据少了几个,也不会影响决策边界的确定,而被红色框框出来三个数据才决定了最终的决策边界,所以这三个数据被称之为支持向量。

  线性分类器

支持向量机算法如何实现最大分类间隔的任务呢?我们可以先从线性分类器开始理解它,支持向量在没有引入核函数的时候就是一个线性的分类器,我们假设与决策边界垂直的向量(决策面的法向量)为V: 
1532929904922091432.jpg

 
黑色的线是假设的决策边界,X1和X2是决策边界两侧的两个点,Xt1和Xt2是两个点在法向量V上面的投影,那么可以很直观看到,原点到Xt1的距离<原点到Xt2的距离,而且可以推广延伸到只要数据点在决策边界的两侧,那么在决策边界左侧的数据点在法向量上面的投影距离永远比右侧的距离短,这就是支持向量机实现分类预测的依据。那么怎么用公式表征出这个点到直线投影的距离呢? 
可以做这样一个假设验证一下: 
1532929916103892593.jpg

 
如上图中的情况所示:要求向量b在向量a上的投影距离d,向量的内积可以表示为: 
1532930002674470862.jpg

 
于是角度的余弦为: 
1532930014426053875.jpg

 
距离d可以表示为: 
1532930023455500442.jpg

 

而在SVM的特征空间中,a是决策边界的法向量,那么a为单位法向量的时候其模为1,所以就有:

1532930032200646038.jpg

 

最后我们把a和b换成上面设定的值就会有: 
1532930042268832276.jpg

 
有了这个东西,我们总能找到一个常数C分开两类数据,也就是说:

1532930054641024685.jpg

 

到了上面的公式后,问题就非常的清晰了,法向量V其实就是决策边界的系数(这是解析几何里面的知识),那么大家肯定见过一种和它非常像的公式,叫做样本空间下的超平面线性方程:

1532930066057440496.jpg

 

线性分类器就是这个样子!!! 
不经过sigmoid函数的Logistic模型也是这个样子!! 
不激活的神经网络中的单个神经元还是这个样子!!

  如何实现最大分类间隔

从上面可以看到,此时的支持向量机(没有加核函数)就是个线性的分类器,它的卓越性能就体现在在线性分类器基础上的最大分类间隔。 
所以本质上SVM要训练的参数只有w和b,关键就在于SVM如何在优化中体现最大分类间隔的思想! 
针对所有的训练数据(traindata),SVM都希望: 
1532930081915558855.jpg

 
这里的正负1就体现的最大分类间隔,这里是选择用正负1是为了计算方便,因为无论间隔是多少,都可以依靠伸缩w和b约为1。上述公式就是SVM的最大间隔假设。如下图: 
1532930091662042897.jpg

 
在这个图中,决策边界两边的线之间的距离(最大间隔)为: 
1532930167602649382.jpg

 
它是这样求出来的,数据中的支持向量在影响着最大间隔,那么假设两个支持向量x1和x2分别为正负,最大间隔就应该是x2-x1在法向量上的投影: 
1532930182009354738.jpg


所以求取d的过程为: 
1532930206885503999.jpg  
 

1532930216798301176.jpg

 
这就是SVM的优化目标,它想要找到max(d),然后大家可能发现了,这个目标里面没有b,之和w有关,那么是不是任意的b都可以呢? 
显然不是的,这个优化有一个约束条件,因为推导的过程就有假设条件是两个支持向量要求在两侧,所以这个约束条件可以写成: 
1532930239056709270.jpg

 

所以最终的目标为:

1532930248043068632.jpg

 
或者为: 
1532930262096605148.jpg

 
需要注意的是,约束条件中的i=1…….n,n为样本的个数。

回复

使用道具 举报

 
*滑块验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


1关注

0粉丝

1603帖子

排行榜

关注我们:微信订阅号

官方微信

APP下载

全国服务热线:

4000-018-018

公司地址:上海市嘉定区银翔路655号B区1068室

运营中心:成都市锦江区东华正街42号广电仕百达国际大厦25楼

邮编:610066 Email:3318850993#qq.com

Copyright   ©2015-2016  比特趋势Powered by©Discuz!技术支持:迪恩网络