从零开始学人工智能(30)--Python · SVM(四)· SMO 算法 射命丸咲

浏览: 625

作者:射命丸咲    Python 与 机器学习 爱好者

知乎专栏:https://zhuanlan.zhihu.com/carefree0910-pyml 

个人网站:http://www.carefree0910.com 


GitHub 地址:https://github.com/carefree0910/MachineLearning/blob/master/e_SVM/SVM.py#L17

(这篇东西我真是觉得又臭又长 ┑( ̄Д  ̄)┍)

=============正文如下===========

SMO 算法概述

SMO 是由 Platt 在 1998 年提出的、针对软间隔最大化 SVM 对偶问题求解的一个算法,其基本思想很简单:在每一步优化中,挑选出诸多参数(image.png)中的两个参数(ai、aj)作为“真正的参数”,其余参数都视为常数,从而问题就变成了类似于二次方程求最大值的问题,从而我们就能求出解析解

具体而言,SMO 要解决的是如下对偶问题:

image.png

使得对image.png都有

image.png

其大致求解步骤则可以概括如下:

image.png


KKT 条件

先来看如何选取参数。在 SMO 算法中,我们是依次选取参数的:

  • 选出违反 KKT 条件最严重的样本点、以其对应的参数作为第一个参数

  • 第二个参数的选取有一种比较繁复且高效的方法,但对于一个朴素的实现而言、第二个参数即使随机选取也无不可

这里就有了一个叫 KKT 条件的东西,其详细的陈列会放在文末,这里就仅简要的说明一下。具体而言,对于已有的模型f=wx+b来说,ai及其对应样本(xi,yi)的 KKT 条件为:

image.png

image.png


(画得有点乱,见谅……)

图中外面有个黑圆圈的其实就是传说中的“支持向量”,其定义会在文末给出

那么我们到底应该如何刻画“违反 KKT 条件”这么个东西呢?从直观上来说,我们可以有这么一种简单有效的定义:

image.png

最后则可以简单的将三份差异向量的平方相加来作为“损失”,从而直接选出使该损失最大的作为 SMO 的第一个参数即可。具体而言:

image.png

得益于 Numpy 强大的 Fancy Indexing,上述置 0 的实现非常好写(???):

# 得到 alpha > 0 和 alpha < C 的 mask
con1 = alpha > 0
con2 = alpha < C
# 算出“差异向量”并拷贝成三份
err1 = y * y_pred - 1
err2 = err1.copy()
err3 = err1.copy()
# 依次根据三个 KKT 条件,将差异向量的某些位置设为 0
# 不难看出为了直观、我做了不少重复的运算,所以这一步是可以优化的
err1[(con1 & (err1 <= 0)) | (~con1 & (err1 > 0))] = 0
err2[((~con1 | ~con2) & (err2 != 0)) | ((con1 & con2) & (err2 == 0))] = 0
err3[(con2 & (err3 >= 0)) | (~con2 & (err3 < 0))] = 0
# 算出平方和并取出使得“损失”最大的 idx
err = err1 ** 2 + err2 ** 2 + err3 ** 2
idx = np.argmax(err)

第二个参数则可以简单地随机选取,虽然这不是特别好,但效果已然不错,而且不仅实现起来更简便、运行起来也更快(其实就是我太懒)(喂)。具体代码如下:

idx = np.random.randint(len(self._y))
# 这里的 idx1 是第一个参数对应的 idx
while idx == idx1:
idx = np.random.randint(len(self._y))
return idx

至于 SMO 算法的第二步,正如前文所说,它的本质就是一个带约束的二次规划,虽然求解过程可能会比较折腾,但其实难度不大。具体步骤会放在文末,这里就暂时按下

SMO 的效果

仍是先看看螺旋线数据集上的训练过程:

略显纠结,不过还是不错的

接下来看看蘑菇数据集上的表现;单就这个数据集而言,我们实现的朴素 SVM 和 sklearn 中的 SVM 表现几乎是一致的(在使用 RBF 核时),比较具有代表性的训练曲线则如下图所示:

image.png

也算是符合 SMO 这种每次只取两个参数进行更新的训练方法的直观

相关数学理论

1)KKT 条件的详细陈列

注意到原始问题为

image.png

image.png

2)何谓“支持向量”

为方便说明,这里再次放出上文给出过的图:

image.png

图中带黑圈的样本点即是支持向量,数学上来说的话,就是对应的样本点即是支持向量。从图中不难看出,支持向量从直观上来说,就是比较难分的样本点

此外,支持向量之所以称之为“支持”向量,是因为在理想情况下,仅利用支持向量训练出来的模型和利用所有样本训练出来的模型是一致的。这从直观上是好理解的,粗略的证明则可以利用其定义来完成:非支持向量的样本对应着ai=0,亦即它对最终模型——

image.png

没有丝毫贡献,所以可以直接扔掉

3)带约束的二次规划求解方法

不妨设我们选取出来的两个参数就是和,那么问题的关键就在于如何把和相关的东西抽取出来并把其它东西扔掉

注意到我们的对偶问题为

image.png

而带约束的二次规划求解过程也算简单:只需先求出无约束下的最优解,然后根据约束“裁剪”该最优解即可

image.png

image.png

image.png

image.png

综上所述,我们就完成了一次参数的更新,之后就不断地更新直至满足停机条件即可

此外,我在 Python · SVM(三)· 核方法 这篇文章中提到过,对 SVM 的对偶形式应用核方法会非常自然。表现在 SMO 上的话就是,我们可以通过简单粗暴地将核矩阵K代替 Gram 矩阵G来完成核方法的应用。直观地说,我们只需将上面所有出现过的G都换成K就行了

至此,SVM 算法的介绍就大致告一段落了。我们从感知机出发,依次介绍了“极大梯度法”、MBGD(Batch 梯度下降)法、核方法和 SMO 算法;虽然都有点浅尝辄止的味道,但覆盖的东西……大概还是挺多的

希望观众老爷们能够喜欢~


公众号后台回复关键词学习

回复 人工智能          揭开人工智能的神秘面纱

回复 贝叶斯算法      贝叶斯算法与新闻分类

回复 机器学习          R&Python机器学习

回复 阿里数据          阿里数据系列课程

回复 Python            Python机器学习案例实战

回复 Spark              征服Spark第一季

回复 kaggle             机器学习kaggle案例

回复 大数据             大数据系列视频

回复 数据分析         数据分析人员的转型

回复 数据挖掘         数据挖掘与人工智能

回复 机器学习         R&Python机器学习

回复 阿里数据         阿里数据系列课程

回复 R                     R&Python机器学习入门

image.png

推荐 1
本文由 人工智能爱好者社区 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册