机器学习(十七) ——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 条评论
登录 后参与评论

相关文章

来自专栏AI2ML人工智能to机器学习

谱聚类

前面, 我们介绍了Laplace图算子 (参考 “Love Plus 矩阵” ),谱聚类spectral clustering 基本思想已经成立了,我们再概述一...

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

深度学习word2vec笔记(算法篇)

一. CBOW加层次的网络结构与使用说明 Word2vec总共有两种类型,每种类型有两个策略,总共4种。这里先说最常用的一种。这种的网络结构如下图。 ? 其中第...

3484
来自专栏决胜机器学习

机器学习(十八) ——SVM实战

机器学习(十八)——SVM实战 (原创内容,转载请注明来源,谢谢) 一、概述 本篇主要用python来实现SVM算法,并用SVM算法进行预测分类结果。对于SM...

3345
来自专栏wym

模板运算和常见滤波操作

首先我们把所有图像看作矩阵。 模板一般是nxn(n通常是3、5、7、9等很小的奇数)的矩阵。模板运算基本思路:将原图像中某个像素的值,作为它本身灰度值和其相邻...

762
来自专栏YoungGy

KD树和LSH局部敏感哈希

文档结构 文档表示 距离度量 KD树 原理 构建 查询 复杂度 KD树的KNN KD树的逼近KNN 不适用高维数据 LSH LSH潜在的问题 LSH算法 复杂度...

2208
来自专栏CreateAMind

浅析互信息与特征选择

那么什么是互信息呢?变量x与变量y之间的互信息,可以用来衡量已知变量x时变量y的不确定性减少的程度,同样的,也可以衡量已知变量y时变量x的不确定性减少的程度。

822
来自专栏企鹅号快讯

机器学习——SVM实战

机器学习(十八) ——SVM实战 (原创内容,转载请注明来源,谢谢) 一、概述 本篇主要用python来实现SVM算法,并用SVM算法进行预测分类结果。对于SM...

1988
来自专栏PPV课数据科学社区

这是一份文科生都能看懂的线性代数简介

选自Medium 作者:Niklas Donges 机器之心编译 参与:Tianci LIU、思源 线性代数的概念对于理解机器学习背后的原理非常重要,尤其是在深...

32710
来自专栏MyBlog

#数值分析读书笔记(4)求非线性方程的数值求解

是否同号, 然后即可知根落在左侧还是右侧, 用这个中点来代替掉原来的端点, 然后得到一个新的区间, 如此反复迭代下去之后, 我们会发现区间收敛到接近一个数

972
来自专栏wOw的Android小站

[Tensorflow] Tensor维度理解

Tensor在Tensorflow中是N维矩阵,所以涉及到Tensor的方法,也都是对矩阵的处理。由于是多维,在Tensorflow中Tensor的流动过程就涉...

843

扫码关注云+社区