您可以捐助,支持我们的公益事业。

1元 10元 50元





认证码:  验证码,看不清楚?请点击刷新验证码 必填



  求知 文章 文库 Lib 视频 iPerson 课程 认证 咨询 工具 讲座 Modeler   Code  
会员   
 
   
 
 
     
   
 订阅
  捐助
支持向量机通俗导论(理解SVM的三层境界)
 

火龙果软件 发布于:2014-09-05

  2747  次浏览      16
 

前言

动笔写这个支持向量机(support vector machine)是费了不少劲和困难的,原因很简单,一者这个东西本身就并不好懂,要深入学习和研究下去需花费不少时间和精力,二者这个东西也不好讲清楚,尽管网上已经有朋友写得不错了(见文末参考链接),但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明,我还是想尝试写一下,希望本文在兼顾通俗易懂的基础上,真真正正能足以成为一篇完整概括和介绍支持向量机的导论性的文章。

本文在写的过程中,参考了不少资料,包括《支持向量机导论》、《统计学习方法》及网友pluskid的支持向量机系列等等,于此,还是一篇学习笔记,只是加入了自己的理解和总结,有任何不妥之处,还望海涵。全文宏观上整体认识支持向量机的概念和用处,微观上深究部分定理的来龙去脉,证明及原理细节,力保逻辑清晰 & 通俗易懂。

同时,阅读本文时建议大家尽量使用chrome等浏览器,如此公式才能更好的显示,再者,阅读时可拿张纸和笔出来,把本文所有定理.公式都亲自推导一遍或者直接打印下来(可直接打印网页版或本文文末附的PDF,享受随时随地思考、演算的极致快感),在文稿上演算。

Ok,还是那句原话,有任何问题,欢迎任何人随时不吝指正 & 赐教,感谢。

第一层、了解SVM

支持向量机,因其英文名为support vector machine,故一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

1.1、分类标准的起源:Logistic回归

理解SVM,咱们必须先弄清楚一个概念:线性分类器。

给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点,用y表示类别(y可以取1或者-1,分别代表两个不同的类),一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane),这个超平面的方程可以表示为( wT中的T代表转置):

可能有读者对类别取1或-1有疑问,事实上,这个1或-1的分类标准起源于logistic回归。

Logistic回归目的是从特征学习出一个0/1分类模型,而这个模型是将特性的线性组合作为自变量,由于自变量的取值范围是负无穷到正无穷。因此,使用logistic函数(或称作sigmoid函数)将自变量映射到(0,1)上,映射后的值被认为是属于y=1的概率。

假设函数

其中x是n维特征向量,函数g就是logistic函数。

的图像是

可以看到,将无穷映射到了(0,1)。

而假设函数就是特征属于y=1的概率。

从而,当我们要判别一个新来的特征属于哪个类时,只需求即可,若大于0.5就是y=1的类,反之属于y=0类。

进一步,可以将假设函数中的g(z)做一个简化,将其简单映射到y=-1和y=1上。映射关系如下:

1.2、线性分类的一个例子

下面举个简单的例子,如下图所示,现在有一个二维平面,平面上有两种不同的数据,分别用圈和叉表示。由于这些数据是线性可分的,所以可以用一条直线将这两类数据分开,这条直线就相当于一个超平面,超平面一边的数据点所对应的y全是 -1 ,另一边所对应的y全是1。

这个超平面可以用分类函数表示,当f(x) 等于0的时候,x便是位于超平面上的点,而f(x)大于0的点对应 y=1 的数据点,f(x)小于0的点对应y=-1的点,如下图所示:

(有一朋友飞狗来自Mare_Desiderii,看了上面的定义之后,问道:请教一下SVM functional margin 为=y(wTx+b)=yf(x)中的Y是只取1和-1 吗?y的唯一作用就是确保functional margin的非负性?真是这样的么?当然不是,详情请见本文评论下第43楼)

当然,有些时候,或者说大部分时候数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问题我们后面会讲),这里先从最简单的情形开始推导,就假设数据都是线性可分的,亦即这样的超平面是存在的。

换言之,在进行分类的时候,遇到一个新的数据点x,将x代入f(x) 中,如果f(x)小于0则将x的类别赋为-1,如果f(x)大于0则将x的类别赋为1。

接下来的问题是,如何确定这个超平面呢?从直观上而言,这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以,得寻找有着最大间隔的超平面。

1.3、函数间隔Functional margin与几何间隔Geometrical margin

在超平面w*x+b=0确定的情况下,|w*x+b|能够表示点x到距离超平面的远近,而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确,所以,可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此,我们便引出了函数间隔(functional margin)的概念。

定义函数间隔(用表示)为:

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

= mini (i=1,...n)

但这样定义的函数间隔有问题,即如果成比例的改变w和b(如将它们改成2w和2b),则函数间隔的值f(x)却变成了原来的2倍(虽然此时超平面没有改变),所以只有函数间隔还远远不够。

事实上,我们可以对法向量w加些约束条件,从而引出真正定义点到超平面的距离--几何间隔(geometrical margin)的概念。

假定对于一个点 x ,令其垂直投影到超平面上的对应点为 x0 ,w 是垂直于超平面的一个向量,为样本x到分类间隔的距离,如下图所示:

,其中||w||表示的是范数。

又由于 x0 是超平面上的点,满足 f(x0)=0 ,代入超平面的方程即可算出:

(有的书上会写成把||w|| 分开相除的形式,如本文参考文献及推荐阅读条目11,其中,||w||为w的二阶泛数)

为了得到的绝对值,令乘上对应的类别 y,即可得出几何间隔(用表示)的定义:

从上述函数间隔和几何间隔的定义可以看出:几何间隔就是函数间隔除以||w||,而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|,只是人为定义的一个间隔度量,而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。

1.4、最大间隔分类器Maximum Margin Classifier的定义

对一个数据点进行分类,当超平面离数据点的“间隔”越大,分类的确信度(confidence)也越大。所以,为了使得分类的确信度尽量高,需要让所选择的超平面能够最大化这个“间隔”值。这个间隔如下图中的gap / 2所示。

通过由前面的分析可知:函数间隔不适合用来最大化间隔值,因为在超平面固定以后,可以等比例地缩放w的长度和b的值,这样可以使得的值任意大,亦即函数间隔可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了,使得在缩放w和b的时候几何间隔的值是不会改变的,它只随着超平面的变动而变动,因此,这是更加合适的一个间隔。所以,这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。

于是最大间隔分类器(maximum margin classifier)的目标函数可以定义为:

同时需满足一些条件,根据间隔的定义,有

其中,s.t.,即subject to的意思,它导出的是约束条件。

回顾下几何间隔的定义可知:如果令函数间隔等于1(之所以令等于1,是为了方便推导和优化,且这样做对目标函数的优化没有影响,至于为什么,请见本文评论下第42楼回复),则有 = 1 / ||w||且,从而上述目标函数转化成了

这个目标函数便是在相应的约束条件下,最大化这个1/||w||值,而1/||w||便是几何间隔

如下图所示,中间的实线便是寻找到的最优超平面(Optimal Hyper Plane),其到两条虚线的距离相等,这个距离便是几何间隔,两条虚线之间的距离等于2,而虚线上的点则是支持向量。由于这些支持向量刚好在边界上,所以它们满足(还记得我们把 functional margin 定为 1 了吗?上节中:处于方便推导和优化的目的,我们可以令=1),而对于所有不是支持向量的点,则显然有

OK,到此为止,算是了解到了SVM的第一层,对于那些只关心怎么用SVM的朋友便已足够,不必再更进一层深究其更深的原理。

   
2747 次浏览       16
     
相关文章 相关文档 相关视频



我们该如何设计数据库
数据库设计经验谈
数据库设计过程
数据库编程总结
数据库性能调优技巧
数据库性能调整
数据库性能优化讲座
数据库系统性能调优系列
高性能数据库设计与优化
高级数据库架构师
数据仓库和数据挖掘技术
Hadoop原理、部署与性能调优
最新课程计划
信息架构建模(基于UML+EA)3-21[北京]
软件架构设计师 3-21[北京]
图数据库与知识图谱 3-25[北京]
业务架构设计 4-11[北京]
SysML和EA系统设计与建模 4-22[北京]
DoDAF规范、模型与实例 5-23[北京]

MySQL索引背后的数据结构
MySQL性能调优与架构设计
SQL Server数据库备份与恢复
让数据库飞起来 10大DB2优化
oracle的临时表空间写满磁盘
数据库的跨平台设计
更多...   


并发、大容量、高性能数据库
高级数据库架构设计师
Hadoop原理与实践
Oracle 数据仓库
数据仓库和数据挖掘
Oracle数据库开发与管理


GE 区块链技术与实现培训
航天科工某子公司 Nodejs高级应用开发
中盛益华 卓越管理者必须具备的五项能力
某信息技术公司 Python培训
某博彩IT系统厂商 易用性测试与评估
中国邮储银行 测试成熟度模型集成(TMMI)
中物院 产品经理与产品管理
更多...