机器学习——SVM进一步认识

机器学习(十七)

——SVM进一步认识

(原创内容,转载请注明来源,谢谢)

注:这两天边看ng的svm视频,边看机器学习实战的书的svm代码,两边都看的云里雾里的,故开始各种搜索资料,最终现在有了比两天前刚学svm时候认识更深一些些,现在就说说这两天对svm的认识。

一、概念

svm称为支持向量,所谓的支持向量,就是在后面划分最大间距的时候,参与运算的向量,且最终新的样本进行比较,也只需要通过支持向量进行比较就可以了,不关心离边界线太远的其他向量。

下图,在一个二维环境中,其中点R,S,G点和其它靠近中间黑线的点可以看作为支持向量,它们可以决定分类器,也就是黑线的具体参数。

对于函数:f(x)=xwT+bf(x)=xwT+b

对于C1类的数据xwT+b⩾1。其中至少有一个点xi,f(xi)= 1。这个点称之为最近点。

对于C2类的数据xwT+b⩽−1。其中至少有一个点xi,f(xi)=−1。这个点称也是最近点。

上面两个约束条件可以合并为:

yif(xi)=yi(xiwT+b)⩾1,yif(xi)=yi(xiwT+b)⩾1。yi是点xi对应的分类值(-1或者1)。因此,线性条件下,f(x)的公式为:f(x)=xwT+b;限制条件为:yif(xi)=yi(xiwT+b)⩾1,i=1,...,n

二、最大几何间隔

f(x)为函数间隔γ。γ=yf(x)/||w||,其中||w||=。因此,问题可以转变为max 1/||w||,要求的条件是yi(xiwT+b)⩾1,i=1,...,n。可以将求max 1/||w||等价转换成球min 0.5||w||2。

现在考虑需要用拉格朗日乘子法和KKT条件来求w和b。这里要求的最优化问题是min 0.5 ||w||2,限制条件是1- yi(xiwT+b)≤0。

为了求解最大几何间隔,求出w和b,使用拉格朗日乘子法,要引入参数α,并对w和b求偏导数,令每个偏导数分别等于。公式如下:

注意到,上图中的第二个式子,αy相乘求和为,是L对b求偏导数,并令其为的结果;第四个式子,关于w的式子,是L对w求偏导数,并令其为的结果。

把上面的w的结果,带入其他的式子,得到:

非常有趣的是,w被消掉了,可以通过α和b就可以直接使用到分类器中。并且都不需要考虑线性问题,可以用于解非线性的情况。

另外,需要注意到的是,前一幅图中的不等式,在这幅图中(最后一个公式,α乘以括号一串那个公式)变成了等式。特别注意的是,由于α是要求大于等于,而后面那一串是要求小于等于,因此为了满足这个等式,必须是α等于或是后面括号内的结果等于。

根据这个性质,会有一个非常重要的结论:SVM训练过程中,只需要拿在支持向量进行训练即可。支持向量,即括号内的等式等于的。

可以这么考虑,当点远离这个边界,可以很明确的被分类到某处,此时明显xiwT+b远大于1,则为了满足拉格朗日的条件,必须是对应的α等于。而看到上面拉格朗日的式子,如果α等于,则整个式子都是,因此可以不用考虑这个点。

当点在附近时,xiwT+b约等于1,此时,就需要对这个点再次训练其对应的α和b,因此这样的边界上的点,也就称为支持向量。

三、处理异常点

如下图的w点,就是一个异常点,会导致无法找到合适的超平面:

为了解决这个问题,引入了一个叫做松弛变量(slackvariable)ξ的概念。公式变成了xiwT+b⩾1-ξi。对于拉格朗日乘子,主要是对α的限定变化了,如下:

这个C越大,表示对异常的情况容忍度越大。C太小会限制α。

四、求解α——SMO法

JohnPlatt发布了一个称为SMO的强大算法,用于训练SVM。SMO表示序列最小优化(Sequential Minimal Optimization)。这个大神在1998年写了一篇论文,讲述这个内容,《Sequential-Minimal-Optimization---A-Fast-Algorithm-for-Training-Support-Vector-Machines》,后面又有一个大神对其进行了改进和补充,写了《Improvements to Platt’s SMO Algorithm for SVM Classifier》,这两篇全英文的论文,后面准备找时间研究一下。

SMO的主要思想是每次取一对αi和αj,调整这两个值,迭代求解,过程如下:

1)初始化α为;

2)在每次迭代中(小于等于最大迭代数),

-找到第一个不满足KKT条件的训练数据,对应的αi

-在其它不满足KKT条件的训练数据中,找到误差最大的x,对应的index的αj

-αi和αj组成了一对,根据约束条件调整αi,αj

这里提到的KKT条件,即拉格朗日乘子中的约束条件。

这里可以调整的点,包括:

(1)yw≤1但是αi0;(3)yw≤1但是αi=0或αi=C。如下图所示:

当迭代完一次后,会发现若干不满足条件且可以调整的点,这个时候SMO采取的策略是选择这10个中的两个α出来,假设为α1,α2,这里先给出结论,调整方式如下:

上图中的E,表示这个点的预测的误差。另外,因为所有对应的α*y的和是,因此调整前后要求满足:

下面是推导过程。【这个问题我想了好久】

假设我们来求α2。观察上面那个等式,y1,y2是标签,要么1要么-1。而两个α>=0。所以新的α是有范围的。假设现在y1=y2=1,那么αnew1+αnew2=αold1+αold2=ϵ

因为αnew1是在0-C之间,所以假设αnew1=0,那么αnew2可以取到最大值为ϵ,也就是αold1+αold2。而αnew2又不能大于C,所以其最大取值为min(C,αold1+αold2)。同理如果αnew1=C,那么αnew2可以取到最小值为ϵ−C,也就是αold1+αold2−C,而αnew2最小不能小于,所以αnew2的下限值就为max(0,αold1+αold2−C)。这是相等取1。

当y1=y2=-1,同理,−αnew1−αnew2=−αold1−αold2=ϵ两边乘以-1,就是αnew1+αnew2=αold1+αold2=−ϵ,因为ϵ就是一个字母,用ϵ代替−ϵ,接下来的讨论过程一模一样,从而属于同类别的时候αnew2上下限就有了。同理去计算下不同类(1,-1)的时候的上下限。最终也能得到一个类似的结果,最终α的范围如下:

下面要求解α,把含有α1,α2都单独拿出来,其他的作为一堆,就变成下面这样:

,v是一个与α1,α2,y1,y2有关的长式子,K是内积。可以看到后面一堆与α1,α2就没有关系。又因为有上面那个old、new的α的等式,可以消去α1new,而两个old又是上一次迭代结果,是已知数,故就变成了α2 new的式子。在令W对α2 new的导数为,可以求出α2 new,进而求出α1 new。

这个计算过程太复杂,不详细描写。这里算出来的α,还需要满足上面的最大值和最小值的限制条件,超过最大值则令其为最大值,低于最小值则令其为最小值。

求出α后,可以根据w的公式,直接求出w。再带回到上面的带b的等式yi(w∗x+b)−1=0,可以求出b。但是由于一次性更新了两个α,对应的会求出两个b的值,要选择哪个b,规则是就是变换后的哪个α在0~C之间,也就是在分界线的边界上,也就是属于支持向量了,那么谁就准,就选那个α带入求出的b的值。

【推导结束】

接下来,剩下的就是循环,再次选择两个α,看是否需要更新(如果不满足KKT条件),不需要就重新选α,需要就更新α。一直到程序循环很多次(通常是用户设定的次数),都没有选择到两个不满足KKT条件的点,也就是所有的点都满足KKT了,那么就大功告成了。

改进:

当随机选取α,到后期时,由于大部分α已经被优化,剩下有问题的那些α很可能一直没有随机到,这样会浪费时间在不断的选择α中。因此,有了启发思想如下:

上一次的一些点的α在0-C之间,也就是这些点不满足条件需要调整,那么一次循环后,选中的α调整了一点,在下一次中,因为每一次的调整比较不可能完全,这些点还是更有可能不满足条件。而那些在上一次本身满足条件的点,那么在下一次后更有可能满足条件的。

所以在启发式的寻找α过程中,并不是遍历所有的点的α,而是遍历那些在0~C之间的α,而0~C反应到点上就是那些属于边界之间的点。当某次遍历在0~C之间找不到α了,那么再去整体遍历一次,这样就又会出现属于边界之间α了,然后再去遍历这些α,如此循环。

那么在遍历属于边界之间α的时候,因为是需要选两个α的,第一个可以随便选,第二个用一个启发式的思想,第1个α选择后,其对应的点与实际标签有一个误差,属于边界之间α的,所以每个点都会有一个自己的误差,这个时候选择剩下的点与第一个α点产生误差之差最大的那个点。

五、非线性分类

非线性分类,由于引入了拉格朗日,变成非常简单,只需要把上面求解α、b的公式中,对应的K函数,换成相应的非线性的核函数即可,常用的有高斯核函数,又称径向基函数(radial basis function)。

——written by linhxx 2018.01.19

本文来自企鹅号 - PHP思想家媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

分类回归树算法---CART

一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

52690
来自专栏小鹏的专栏

感知机--模型与策略

看到模型和策略,应该很快联想到了李航的《统计学习方法》,统计学习方法的三要素定义为:模型、策略、算法。 感知机 感知机是二分类的线性分类模型,输入为实例的...

22150
来自专栏机器学习算法工程师

RNN入门与实践

作者:叶虎 编辑:黄俊嘉 引言 递归神经网络(Recurrent Neural Network, RNN)是神经网络家族的重要成员,而且也是深度学习领域中的得...

39970
来自专栏闪电gogogo的专栏

《统计学习方法》笔记二 感知机

感知机(perceptron)是二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别,取±1。感知机对应与输入空间中将实例划分为正负两类的分离超平面,属...

8720
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

基于模糊集理论的一种图像二值化算法的原理、实现效果及代码

  这是篇很古老的论文中的算法,发表与1994年,是清华大学黄良凯(Liang-kai Huang) 所写,因此国外一些论文里和代码里称之为Huang's fu...

324110
来自专栏Pulsar-V

原-图像处理基础(二)图像的放大与缩小

最近邻插值法 ? 其中 size(g(x))代表图像像素矩阵列宽 size(g(y))代表图像像素矩阵行高 scale 代表缩放倍数 \begin{matr...

61370
来自专栏小鹏的专栏

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

Deep face:论文。 a. 人脸检测,使用6个基点 b. 二维剪切,将人脸部分裁剪出来 c. 67个基点,然后Delaunay三角化,在轮廓处添加三角形来...

37050
来自专栏用户2442861的专栏

聚类算法原理及python实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

29140
来自专栏拂晓风起

验证码去噪 分离背景 分离文字 最大类间方差

13420
来自专栏张俊红

Sklearn参数详解—GBDT

这篇介绍Boosting的第二个模型GBDT,GBDT和Adaboost都是Boosting模型的一种,但是略有不同,主要有以下两点不同:

23240

扫码关注云+社区

领取腾讯云代金券