`
iwebcode
  • 浏览: 1997296 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

支持向量机(SVM)基础

 
阅读更多

前言:

关于SVM的论文、书籍都非常的多,引用强哥的话“SVM是让应用数学家真正得到应用的一种算法”。SVM对于大部分的普通人来说,要完全理解其中的数学是非常困难的,所以要让这些普通人理解,得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些数学,对学习其他的内容也是大有裨益的。我就是属于绝大多数的普通人,为了看明白SVM,看了不少的资料,这里把我的心得分享分享。

一、线性分类器:

首先给出一个非常非常简单的分类问题(线性可分),我们要用一条直线,将下图中黑色的点和白色的点分开,很显然,图上的这条直线就是我们要求的直线之一(可以有无数条这样的直线)

image

假如说,我们令黑色的点 = -1, 白色的点 = +1,直线f(x) = w.x + b,这儿的x、w是向量,其实写成这种形式也是等价的f(x) = w1x1 + w2x2 … + wnxn + b, 当向量x的维度=2的时候,f(x) 表示二维空间中的一条直线,当x的维度=3的时候,f(x) 表示3维空间中的一个平面,当x的维度=n > 3的时候,表示n维空间中的n-1维超平面。

刚刚说了,我们令黑色白色两类的点分别为+1, -1,所以当有一个新的点x需要预测属于哪个分类的时候,我们用sgn(f(x)),就可以预测了,sgn表示符号函数,当f(x) > 0的时候,sgn(f(x)) = +1, 当f(x) < 0的时候sgn(f(x)) = –1。

但是,我们怎样才能取得一个最优的划分直线f(x)呢?下图的直线表示几条可能的f(x)

image

一个很直观的感受是,让这条直线到给定样本中最近的点最远,这句话读起来比较拗口,下面给出几个图,来说明一下:

第一种分法:

image

第二种分法:

image

这两种分法哪种更好呢?从直观上来说,就是分割的间隙越大越好,把两个类别的点分得越开越好。就像我们平时判断一个人是男还是女,就是很难出现分错的情况,这就是男、女两个类别之间的间隙非常的大导致的,让我们可以更准确的进行分类。在SVM中,称为Maximum Marginal,是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是有很多道理的,比如说从概率的角度上来说,就是使得置信度最小的点置信度最大(听起来很拗口

上图被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)。

image

上图就是一个对之前说的类别中的间隙的一个描述。Classifier Boundary就是f(x),红色和蓝色的线(plus plane与minus plane)就是support vector所在的面,红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。

image

这里直接给出M的式子:(从高中的解析几何就可以很容易的得到了,也可以参考后面Moore的ppt)

image

另外支持向量位于wx + b = 1与wx + b = -1的直线上,我们在前面乘上一个该点所属的类别y(还记得吗?y不是+1就是-1),就可以得到支持向量的表达式为:y(wx + b) = 1,这样就可以更简单的将支持向量表示出来了。

当支持向量确定下来的时候,分割函数就确定下来了,两个问题是等价的。得到支持向量,还有一个作用是,让支持向量后方那些点就不用参与计算了。这点在后面将会更详细的讲讲。

在这个小节的最后,给出我们要优化求解的表达式:

image

||w||的意思是w的二范数,跟上面的M表达式的分母是一个意思,之前得到,M = 2 / ||w||,最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数,我们可以对其加入平方,和前面的系数,熟悉的同学应该很容易就看出来了,这个式子是为了方便求导。

这个式子有还有一些限制条件,完整的写下来,应该是这样的:(原问题

image

s.t的意思是subject to,也就是在后面这个限制条件下的意思,这个词在svm的论文里面非常容易见到。这个其实是一个带约束的二次规划(quadratic programming, QP)问题,是一个凸问题,凸问题就是指的不会有局部最优解,可以想象一个漏斗,不管我们开始的时候将一个小球放在漏斗的什么位置,这个小球最终一定可以掉出漏斗,也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体,我们要做的就是在这个凸多面体中找到最优解。这些问题这里不展开,因为展开的话,一本书也写不完。如果有疑问请看看wikipedia。

二、转化为对偶问题,并优化求解:

这个优化问题可以用拉格朗日乘子法去解,使用了KKT条件的理论,这里直接作出这个式子的拉格朗日目标函数:

image

求解这个式子的过程需要拉格朗日对偶性的相关知识(另外pluskid也有一篇文章专门讲这个问题),并且有一定的公式推导,如果不感兴趣,可以直接跳到后面蓝色公式表示的结论,该部分推导主要参考自plukids的文章

首先让L关于w,b最小化,分别令L关于w,b的偏导数为0,得到关于原问题的一个表达式

image

将两式带回L(w,b,a)得到对偶问题的表达式

image

新问题加上其限制条件是(对偶问题):

image

这个就是我们需要最终优化的式子。至此,得到了线性可分问题的优化式子

求解这个式子,有很多的方法,比如SMO等等,个人认为,求解这样的一个带约束的凸优化问题与得到这个凸优化问题是比较独立的两件事情,所以在这篇文章中准备完全不涉及如何求解这个话题,如果之后有时间可以补上一篇文章来谈谈:)。

三、线性不可分的情况(软间隔):

接下来谈谈线性不可分的情况,因为线性可分这种假设实在是太有局限性了:

下图就是一个典型的线性不可分的分类图,我们没有办法用一条直线去将其分成两个区域,每个区域只包含一种颜色的点。

image 要想在这种情况下的分类器,有两种方式,一种是用曲线去将其完全分开,曲线就是一种非线性的情况,跟之后将谈到的核函数有一定的关系:

image另外一种还是用直线,不过不用去保证可分性,就是包容那些分错的情况,不过我们得加入惩罚函数,使得点分错的情况越合理越好。其实在很多时候,不是在训练的时候分类函数越完美越好,因为训练函数中有些数据本来就是噪声,可能就是在人工加上分类标签的时候加错了,如果我们在训练(学习)的时候把这些错误的点学习到了,那么模型在下次碰到这些错误情况的时候就难免出错了(假如老师给你讲课的时候,某个知识点讲错了,你还信以为真了,那么在考试的时候就难免出错)。这种学习的时候学到了“噪声”的过程就是一个过拟合(over-fitting),这在机器学习中是一个大忌,我们宁愿少学一些内容,也坚决杜绝多学一些错误的知识。还是回到主题,用直线怎么去分割线性不可分的点:

我们可以为分错的点加上一点惩罚,对一个分错的点的惩罚函数就是这个点到其正确位置的距离:

image

在上图中,蓝色红色的直线分别为支持向量所在的边界,绿色的线为决策函数,那些紫色的线表示分错的点到其相应的决策面的距离,这样我们可以在原函数上面加上一个惩罚函数,并且带上其限制条件为:

image

公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分,当xi在正确一边的时候,ε=0,R为全部的点的数目,C是一个由用户去指定的系数,表示对分错的点加入多少的惩罚,当C很大的时候,分错的点就会更少,但是过拟合的情况可能会比较严重,当C很小的时候,分错的点可能会很多,不过可能由此得到的模型也会不太正确,所以如何选择C是有很多学问的,不过在大部分情况下就是通过经验尝试得到的。

接下来就是同样的,求解一个拉格朗日对偶问题,得到一个原问题的对偶问题的表达式:

image

蓝色的部分是与线性可分的对偶问题表达式的不同之处。在线性不可分情况下得到的对偶问题,不同的地方就是α的范围从[0, +∞),变为了[0, C],增加的惩罚ε没有为对偶问题增加什么复杂度。

四、核函数:

刚刚在谈不可分的情况下,提了一句,如果使用某些非线性的方法,可以得到将两个分类完美划分的曲线,比如接下来将要说的核函数。

我们可以让空间从原本的线性空间变成一个更高维的空间在这个高维的线性空间下,再用一个超平面进行划分。这儿举个例子,来理解一下如何利用空间的维度变得更高来帮助我们分类的(例子以及图片来自pluskid的kernel函数部分):

下图是一个典型的线性不可分的情况

image

但是当我们把这两个类似于椭圆形的点映射到一个高维空间后,映射函数为:

image 用这个函数可以将上图的平面中的点映射到一个三维空间(z1,z2,z3),并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。

rotate

用另外一个哲学例子来说:世界上本来没有两个完全一样的物体,对于所有的两个物体,我们可以通过增加维度来让他们最终有所区别,比如说两本书,从(颜色,内容)两个维度来说,可能是一样的,我们可以加上作者 这个维度,是在不行我们还可以加入 页码,可以加入 拥有者,可以加入购买地点,可以加入 笔记内容等等。当维度增加到无限维的时候,一定可以让任意的两个物体可分了

回忆刚刚得到的对偶问题表达式:

image

我们可以将红色这个部分进行改造,令:

image 这个式子所做的事情就是将线性的空间映射到高维的空间,k(x, xj)有很多种,下面是比较典型的两种:

image 上面这个核称为多项式核,下面这个核称为高斯核,高斯核甚至是将原始空间映射为无穷维空间,另外核函数有一些比较好的性质,比如说不会比线性条件下增加多少额外的计算量,等等,这里也不再深入。一般对于一个问题,不同的核函数可能会带来不同的结果,一般是需要尝试来得到的。

五、一些其他的问题:

1)如何进行多分类问题:

上面所谈到的分类都是2分类的情况,当N分类的情况下,主要有两种方式,一种是1 vs (N – 1)一种是1 vs 1,前一种方法我们需要训练N个分类器,第i个分类器是看看是属于分类i还是属于分类i的补集(出去i的N-1个分类)。

后一种方式我们需要训练N * (N – 1) / 2个分类器,分类器(i,j)能够判断某个点是属于i还是属于j。

这种处理方式不仅在SVM中会用到,在很多其他的分类中也是被广泛用到,从林教授(libsvm的作者)的结论来看,1 vs 1的方式要优于1 vs (N – 1)。

2)SVM会overfitting吗?

SVM避免overfitting,一种是调整之前说的惩罚函数中的C,另一种其实从式子上来看,min ||w||^2这个看起来是不是很眼熟?在最小二乘法回归的时候,我们看到过这个式子,这个式子可以让函数更平滑,所以SVM是一种不太容易over-fitting的方法。

参考文档:

主要的参考文档来自4个地方,wikipedia(在文章中已经给出了超链接了),pluskid关于SVM的博文Andrew moore的ppt(文章中不少图片都是引用或者改自Andrew Moore的ppt,以及prml

分享到:
评论

相关推荐

    11支持向量机SVM.zip

    机器学习之支持向量机SVM代码

    支持向量机SVM

    让新手快速了解支持向量机的一篇PPT,PPT讲解充分照顾新手的基础,可以作为其他资料的补充

    支持向量机原理.pdf

    2.重点讲解了支持向量机的原理,首先深入讲解支持向量机的最基础类型——线性可分支持向量机,在此基础上拓展到广义线性支持向量机、非线性支持向量机以及回归支持向量机,并介绍了近来支持向量机的改进算法;...

    使用Python实现支持向量机(SVM)分类器:从理论到实践

    svm支持向量机python代码在机器学习领域,支持向量机(Support Vector Machine,简称SVM)是一种强大的分类器,广泛应用于图像分类、文本分类、人脸识别等任务。本篇博客将为您详细介绍SVM的理论基础,并通过Python...

    基于机器学习的支持向量机SVM的股票交易策略研究学习源码.zip

    1、该资源内项目代码经过严格调试,下载即用确保可以运行! 2、该资源适合计算机相关专业(如计科、人工智能、大数据、数学、电子信息等)正在做课程设计、...基于机器学习的支持向量机SVM的股票交易策略研究学习源码.zip

    支持向量机SVM理论基础和应用

    该软件可以解决C- SVM分类、-SVM分类、-SVM回归和-SVM回归等问题,包括基于一对一算法的多类模式识别问题。在第2章中我们也介绍了该软件的一些优点,因此通过综合考虑,我们决定采用该软件作为工作软件。SVM用于模式...

    从零推导支持向量机(SVM)

    这是关于:支持向量机的基础内容-从零推导支持向量机(SVM)

    支持向量机SVM-light

    支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期...

    基于Matlab实现支持向量机SVM算法股票涨跌预测仿真(源码+数据).rar

    1、资源内容:基于Matlab实现支持向量机SVM算法股票涨跌预测仿真(源码+数据).rar 2、适用人群:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业或毕业设计,作为“参考资料”使用。 3、解压说明:...

    Python《基于机器学习算法支持向量机SVM的股票交易策略》+源代码+文档说明

    -机器学习(股票),基于机器学习算法支持向量机SVM的交易策略 - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心...

    支持向量机

    支持向量机 SVM的理论基础 线性判别函数和判别面 最优分类面 支持向量机 SVM的研究与应用

    本科毕业论文 基于支持向量机(SVM)的蘑菇毒性检测系统

    2.1支持向量机基础理论 3 2.2 C-SVM算法及其变形算法 7 2.3 V-SVM算法 9 3 LIBSVM软件 12 3.1 LIBSVM软件简介 12 3.2 LIBSVM软件的使用方法 12 3.3 LIBSVM的工具包 15 4 Qt图形库 18 5 系统的设计与实现 19 5.1分类...

    基于支持向量机(SVM)的乳腺癌诊断

    支持向量机SVM是一种新的机器学习方法,其基础是统计学理论。模型泛化能力强;进行非线性分类时通过高维空间变换。

    SVM(支持向量机)入门

    SVM(支持向量机)入门,对SVM主要内容进行介绍,能够让初学者很快的掌握SVM基本内容,宏观上了解SVM的应用,对以后的学习打下基础

    支持向量机导论

    支持向量机(SVM)是在统计学习理论的基础上发展起来的新一代学习算法,它在文本分类、手写识别、图像分类、生物信息学等领域中获行较好的应用。本书是第一本综合介绍支持向量机(SVM)的书籍,它从机器学习算法的...

    svm-chinese.rar_SVM支持向量机_support vector _svm non linear_向量机_支持向量

    非线形回归,支持向量机理论。详细地介绍了支持向量机的数据基础。举例说明支持向量机的应用。

    支持向量机理论与算法研究综述

    统计学习理论(statistical learning theory,SLT)是一种小样本...该文系统介绍了支持向量机的理论基础,综述了传统支持向量机的主流训练算法以及一些新型的学习模型和算法,最后指出了支持向量机的研究方向与发展前景。

Global site tag (gtag.js) - Google Analytics