首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【分类战车SVM】第三话:最大间隔分类器

【分类战车SVM】第三话:最大间隔分类器

作者头像
数说君
发布2018-03-28 16:11:17
1.2K0
发布2018-03-28 16:11:17
举报
文章被收录于专栏:数说工作室数说工作室

分类战车SVM

(第三话:最大间隔分类器)

查看本《分类战车SVM》系列的内容:

第一话:开题话

第二话:线性分类

第三话:最大间隔分类器

第四话:拉格朗日对偶问题(原来这么简单!)

第五话:核函数(哦,这太神奇了!)

第六话:SMO算法(像Smoke一样简单!)

附录:用Python做SVM模型

转载请注明来源


1.回顾

前面说到,线性分类器就是找一个平面,能最好的区分不同类别的样本,logistic模型找的那个超平面,是尽量让所有点都远离它,而SVM寻找的那个超平面,是只让最靠近中间分割线的那些点尽量远离,即只用到那些“支持向量”的样本——所以叫“支持向量机”。

上一文中,我们把线性分类器的分类标准用数学语言给表达了,原来的标准是:

  • 当某点带入f(x)使得f(x)>0时,则该点在直线上方,则说明属于圆圈;
  • 当某点带入f(x)使得f(x)<0时,则该点在直线下方,则说明属于叉叉;
  • f(x)=0时,哪一类都可以;

转化为数学语言是:

具体来看,SVM是怎么利用这个思想去选择超平面的呢?先从函数间隔说起。

2.函数间隔

有一个常识大家应该都同意,将某个点带入到超平面的分割线f(x)中,f(x)的绝对值|f(x)|越大说明越远离这条线(因为如果f(x)>>0,那么就越可以有信心的把这个点评为圆圈即y=1,如果f(x)<<0,那么就可以越有信心的把这个点评为叉叉即y=-1),反过来说,这条超平面的分隔功能越好——因为它能把各个点分的很开。那么,f(x)的绝对值大小,就可以在一定程度上反映了这个超平面的优良,这个绝对值|f(x)|就被称为“函数间隔”,注意我们不用|f(x)|,而是用yf(x),因为yf(x)=|f(x)|。

函数间隔:yf(x),它用来评价一个超平面对点的分类情况,我们用

来表示(

)。

刚才我们说的,是用函数间隔去分一个点的情况,如下面这个图,同样一个点,一定有

yf1(x) > yf2(x)

假如我们要分全部的样本点,比如有10个、20个或者100个点,应该如何评价这个超平面的函数间隔?

答案是用全部函数间隔中的最小值,如下图,左边这条超平面的函数间隔是红色圆圈对应的yf(x),而右边超平面的函数间隔是绿色叉叉对应的yf(x)。

3.几何间隔

有人说,函数间隔yf(x)从道理上虽然可以作为判断标准,但是感觉上比较抽象,不太容易去理解。既然要用点到直线的远近去衡量一个超平面的优良,为什么不直接用几何距离呢?——就是这个点到线段的垂直距离呀!对的,所以有了我们更好的一个衡量标准——几何间隔。它比函数间隔更加“几何、直观”。

就像之前的那个例子,我用几何距离,即直观又好理解,如下图的两个橙色线段,这就是几何间隔,也即点到线段的几何距离。

几何距离的公式是什么?它和函数间隔就很像,想不起来的同学需要好好复习一下解析几何了。

其实,几何间隔就是等于函数间隔再除以一个范式。

刚才说几何间隔比函数间隔要直形好(直观、形象、好理解),真的只是因为这样吗?当然不。试想一下,我们同比例缩放f(x)中系数w与b的值,线还是那条线,但点到线的距离就变了,等比例的放大或缩小。而几何间隔则没有这个问题,因为它除了图中的那个分母。缩放w和b的时候,点到线的距离还是不变的。

另外,这是一个点到超平面的几何间隔,全部样本到一个超平面的几何间隔呢?就是距离超平面最近的那个点,到超平面的几何间隔,即,所有点到超平面的几何距离中,最小的那个。

那么问题就来了,我们现在知道,用几何间隔来评价超平面的优良——几何间隔越大,说明超平面把样本分的越开分的越清楚。所以,我们要选择的那个超平面,它到一组样本点的几何间隔一定要是最大的——最大间隔分类器。

4.最大间隔分类器

将前面做一个总结,最大间隔分类器也就找到了。SVM是如何寻找超平面的?

① 用几何间隔来衡量点到超平面之间的距离

② 一组样本中,将距超平面最近的点到超平面的距离,作为这组样本到超平面的距

③ 寻找的那个超平面,是可以使该组样本到它的距离最大,即能最好的讲样本分开。

将上面三个转换成数学语言,那么我们的求解目标也就出来了,它们三个对应的分别是:

这样,就把问题转化成了一个求极大值的数学问题,为了方便推导价和优化的目的,我们可以令函数间隔|f(x)|=yf(x)=1,即固定函数间隔的值为1(对目标函数的优化没有影响,为什么?在微信公众号中回复“svma”查看),那么③就变成了

,求

的最大值相当于求

的最小值,那么最终问题进一步等价转化为了一个二次规划问题:

接下来,就是如何进行求解了。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2015-04-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数说工作室 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分类战车SVM
  • (第三话:最大间隔分类器)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档