机器学习(十七) ——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求偏导数,令每个偏导数分别等于0。公式如下:

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

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

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

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

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

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

当点在附近时,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)初始化α为0;

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

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

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

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

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

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

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

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

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

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

假设我们来求α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最小不能小于0,所以α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是<x1∗x2>内积。可以看到后面一堆与α1,α2就没有关系。又因为有上面那个old、new的α的等式,可以消去α1new,而两个old又是上一次迭代结果,是已知数,故就变成了α2 new的式子。在令W对α2 new的导数为0,可以求出α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

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

R语言与机器学习(分类算法)支持向量机

说到支持向量机,必须要提到july大神的《支持向量机通俗导论》,个人感觉再怎么写也不可能写得比他更好的了。这也正如青莲居士见到崔颢的黄鹤楼后也...

2734
来自专栏机器学习算法全栈工程师

机器学习之——自动求导

作者:叶虎 小编:张欢 随机梯度下降法(SGD)是训练深度学习模型最常用的优化方法。在前期文章中我们讲了梯度是如何计算的,主要采用BP算法,或者说利用链式法则...

2978
来自专栏闪电gogogo的专栏

霍夫变换

霍夫变换是一种特征提取技术,通过一种投票算法检测具有特定形状的物体。该过程在一个参数空间中通过计算累计结果的局部最大值得到一个符合该特定形状的集合作为hough...

723
来自专栏机器之心

基于注意力机制,机器之心带你理解与训练神经机器翻译系统

3108
来自专栏个人分享

Kmeans算法学习与SparkMlLib Kmeans算法尝试

K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归...

521
来自专栏绿巨人专栏

机器学习中的基本数学知识

3637
来自专栏ATYUN订阅号

机器学习入门——使用python进行监督学习

? 什么是监督学习? 在监督学习中,我们首先要导入包含训练特征和目标特征的数据集。监督式学习算法会学习训练样本与其相关的目标变量之间的关系,并应用学到的关系对...

37410
来自专栏目标检测和深度学习

Hinton向量学院推出神经ODE:超越ResNet 4大性能优势

【导读】Hinton创建的向量学院的研究者提出了一类新的神经网络模型,神经常微分方程(Neural ODE),将神经网络与常微分方程结合在一起,用ODE来做预测...

793
来自专栏书山有路勤为径

Generative Adversarial Network

这里我们将建立 一个对抗生成网络 (GAN)训练MNIST,并在最后生成新的手写数字。

682
来自专栏CVer

风格迁移三部曲(二)之固定风格任意内容的快速风格迁移

上篇介绍了风格迁移三部曲(一)之普通风格迁移,本文将继续介绍第二种风格迁移方式:固定风格任意内容的快速风格迁移。

730

扫描关注云+社区