前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >机器学习之SVM原理

机器学习之SVM原理

原创
作者头像
汪毅雄
发布2019-10-14 22:40:15
8440
发布2019-10-14 22:40:15
举报
文章被收录于专栏:汪毅雄的专栏

相信了解机器学习的同学都知道,SVM的“完美强迫症”使得其在各大模型中,几乎是一个“统治性”的地位。但是也不是那么绝对啦,SVM比较耗时,因此不适合那些超大样本。

认识SVM

性质:首先一般情况,它主要解决的是分类问题(当然,回归也是可以做)。

解决的2个主要问题:

1、最大间隔问题

先看一组图片 (图片出处

假设有一堆球,想用一根棍子把它们分开,怎么做?

有人这么做,确实分开了,那就可以下班了吗?显然不行

SVM看到后,强行把棍子扭一扭才舒服,扭完后棍子离两边的球都比较远了。

OK,先给出几个关于SVM的术语

小球:数据

棍子:超平面

间隔:离超平面最近的那个数据,到超平面距离

如图,假设间隔为f(x),则SVM做的事就是找的一个棍子(超平面),使得max{ 2f(x) },也就是找到最大间距对应的那个超平面。

核函数

还是先看一张图

星星和圆分别代表一些样本,这时候需要分开它们怎么处理?

这时候用一个简单的核函数就能处理了,我们令z = x^2 + y^2,这样在z轴上就能得到一些数据,如下图。

这个超平面在z轴的值我们随便举说个,比如9,那超平面可以描述为x^2 + y^2 = 9

回到第一张图,看这个核函数的超平面就是这样的划分的。

好了,SVM的认识到此,如果只是想了解SVM是什么的,可以就此打住了,后面的是数学的推导。

详解+数学推导

最大间隔问题

我们知道一个平面的方程可以用

来表示。而点x0到面的距离可以这么表示:

好了,开始真正的说SVM了,这里我们沿用经典的SVM推导方式。

如上图(图片来自wiki),我们假设样本是线性可分的,如果采用最大间隔的方法的话,那么它一定可以表示成如上的模型。也就是说对于所有的白点和黑点都满足:

yi用-1和1来区分,方便推导

而他们的间隔则为

那么最大间隔问题模型就转化为求解使得间隔r最大的w和b,即(s.t.表示受限制于):

为了方便计算,我们把问题转化成:

这个就是最大间隔问题的最初模型。可以看到这个是一个带不等式约束条件的求最小值问题,而目标函数又是一个凸函数,这个问题就转化成一个凸优化问题!

在我的另一篇文章《 怎么理解凸优化及其在SVM中的应用 》中,详细的解释了凸优化及上述问题的推导,这里直接给出结论。

对于带约束条件的极值问题,肯定也是采用拉格朗日乘子法,其函数:

上述问题的等价问题为:

其对偶问题为:

先求min(L),对w和b分别求偏导得:

代回L中即得到minL,手撕一段吧:

上图最后一行就是最大间隔的对偶问题的最终形式,对偶问题和原始问题等价的话,需要满足KKT条件,令

则KKT条件为:

模型最终转化成参数为alpha的函数最大值问题,也就是由w,b两个参数变成一个参数了!

怎么求?显然,梯度下降法绝对是可行的,但是效率太低。

为了提高效率,大牛们提出了很多高效的算法,其中最著名的一个是SMO算法,这个放到文章最后讲!

核函数

核函数不是SVM独有的,只是SVM让它发扬光大了!在最大间隔问题中,我们的分割平面设为:

这就是说,它只能处理线性分割。而要实现非线性分割,则必须使用核函数了。核函数的作用,其实就是把样本映射到更高维的空间,使得原本线性不可分的样本变得在某一个纬度变得线性可分。

在模型上看来就是把

,代入最大间隔模型中就是

其对偶问题为:

核函数即为:

如果已知φ(x),那核函数肯定就能求出来,但是通常情况

1、我们往往很难求出合适的。

2、纬度太高的话,求内积会非常非常吓人

因此对于核函数,只能定义一些常用的。但是不是随便定义的,由于是做φ(x)的内积,学过矩阵的应该知道,其核矩阵必须是半正定的

一些常见的核函数有(内容来自wiki):

而我们最常用的核函数主要是:线性核(φ(x)=x)、高斯核。

软间隔

先看几幅图

如果样本是如上图,那么沿用上述理论划分是没问题的。

要是这样呢?

有一个样本跑到上面去了(脏数据),如果依然采用之前的理论,那么它会这么划分,这显然不是什么更好的结果。

更好的结果是,我们接受一个错误样本,使得其容错性更强。

怎么在数学上体现呢,SVM采用的是引入松弛变量ε,也就是把目标函数改成:

其中ε指的样本的损失程度,如果样本符合最大间隔条件,那么ε=0。

而C指的是人为引入的权值。比如说上图那个突出的黑点,我们人为的干预它,认为它十分重要/它一定是黑色的。那么C可以设为很大,以致如果把它分错了的话,后果相当严重(损失函数值很大,反映出来的也就是误差很大)

对于软间隔同理,我们可以采用相同的计算方式,得到它的对偶问题为:

和不加损失函数一样,只不过

这个约束条件变成

其KKT条件也变化为:

当然损失函数不是只有这一种啦,还有一些甚至可以扩展至回归的,有兴趣的同学可以研究一下。

SMO算法

在最大间隔中,提到了一个解对偶问题的算法也就是SMO,这里也介绍下。刚才我们的优化问题最终描述为:

其中y、x和C都是已知数,要解决的是以α为参数的最大值问题,其中α有m个。

通常,我们的优化思路是,这m个参数逐个地优化,比如说,先固定除α1外的其他参数,然后对它求偏导求极值。但是有个问题在于,我们存在一个约束条件:

这就意味着,如果只保留1个参数α1的话,它可以通过下式直接被算出来:

因此,这里SMO采用保留2个参数的方式。

SMO的优化过程是分很多轮的,每一轮都有这么一些步骤:

1、选出两个合适的参数α1、α2,固定其他参数

2、利用约束条件,算出α1和α2关系,代回目标函数中消掉其中一个α1,那么目标的参数就只剩α2了。

3、唯一参数问题,求偏导求极值

这样经过一轮后,目标函数已经在α1、α2两个参数上max了

这样经过n轮后迭代后,可以选出一组符合条件“最”优解(不一定需要到最优才停止)。

那么问题又来了,怎么选参数呢?SMO有这么一些规则

1、只选择不满足KKT条件的,直观来说就是带来误差(错误样本)的α,每次都从中选取带来误差最大的α作为第一个参数,也就是我们要优化的参数,假设为α1。

2、选取第二个参数的时候,我们要选取对待优化参数α1带来积极影响最大的那个参数.怎么算积极影响呢?SMO定义一个指标E:

先算出所有的参数的E值,已知我们优化的参数为α1的话,那么E1如果为正,则取其他参数中负的最大的那个,反之取正的最大的那个,也是使得|E1 - Ei|最大的那个αi.

这样所有环都通畅了,且每次迭代带来的收益都是最高,迭代次数可能会更少。

主要参考文献

机器学习 周志华

知乎 - SVM是什么意思(https://www.zhihu.com/question/21094489/answer/86273196

Wiki - SVM

等等

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 认识SVM
    • 1、最大间隔问题
      • 核函数
      • 详解+数学推导
        • 最大间隔问题
          • 核函数
            • 软间隔
              • SMO算法
              • 主要参考文献
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档