【分类战车SVM】第六话:SMO算法(像smoke一样简单!)

分类战车SVM

(第六话:SMO算法)

查看本《分类战车SVM》系列的内容:

第一话:开题话

第二话:线性分类

第三话:最大间隔分类器

第四话:拉格朗日对偶问题(原来这么简单!)

第五话:核函数(哦,这太神奇了!)

第六话:SMO算法(像Smoke一样简单!)

附录:用Python做SVM模型

转载请注明来源


我有一双神奇的解题小手,不断的化简——代入——化简——代入,不断的迭代——搜索——迭代——搜索,咦,答案出来了!!!

本集大纲:

1.回顾

2.处理奇葩值

3.SMO算法


1. 回顾

第2-4话中,我们介绍了如何去拟合一个SVM模型,第5话我们假设把这个SVM模型拟合好了,讨论如何去实现它,前几话的逻辑关系如下图所示:

看到上面的图,你已经明白,本集第六话要讲的,就是SVM模型的拟合过程——SMO序列最小优化算法。

2. 处理奇葩值

第五话中,我们说到,有一些无法用线性分类器分开的情况,其解决办法是映射到高维。映射到高维是可以解决,但是计算要复杂了,所以我们又用核函数简化计算。这是第五话的内容。但是,看看下面这个例子,你建不建议用映射的办法?

我勒个去!!!

如果把它当做非线性问题,那么要用下面左图的办法(映射+核函数),但是不是觉得太亏了,就因为一个点,计算量要复杂很多,而且这个点非常有可能是噪音!

因此,在实际建模中,我们应该考虑到这样的情况,允许个别离群点的存在。把心放宽一点,用下图右边的方法去解决。

当然,把心放多宽,那要你自己把握了,万一你是处女座……

那么具体到数学表达上,怎么个容忍法呢?我用下面的对照图来说明:

下面这幅图一步一步不用去推,这么展示有两个目的:一是想要说明,加了松弛变量的推导其实也就多了那么个小尾巴ξ,在最后要使用的那个对偶问题里,也就是对偶变量a多了一个上线C;二是正好让大家也复习一下前面的推导过程,忘记的同学可以对照着翻看一下前面五话。

3. SMO算法

前面我们用那么多篇幅,一步步推导,把要解决的问题打造成如下形式:

为了方便下面的说明,我们给这个问题起个代号吧,就叫“终极问题”和“终极约束”!

现在我们就用SMO序列最小优化算法来解决这个“终极问题”。

还记得梯度上下降法吗?算了还是不把事情搞复杂了,感兴趣的在公众号“数说工作室”(微信号shushuojun)中回复“得到”查看。

这里我们的解决思路,简单来说,就是固定a1以外的所有参数,然后在a1上求极值。

这样可以吗?不可以,因为我们这题多了一个

也就是说,当我固定a1以外的所有参数时,a1的值也就定下来了:

所以固定一个参数是不行的,我们要一次选取两个参数做优化。那么我们选取a1,a2,其他变量ai(i=3,4,…)是固定的。

好了,我们现在开始解,思路如下图:

好了,我们先化简“终极约束”

  • 化简“终极约束”

由于我们是固定除了a1,a2所有的参数,因此有:

这里D我们用一个常数表示,是被我们固定了的。我们就可以利用这个来表示a1:

其实,y的取值要么是1,要么是-1,所以上式等价于:

这是我们化简得到的第一个信息。别忘了我们还有,

以上是我们直接得到的两个信息,把这两个信息合并,我们还能进一步缩小参数a1,a2的取值范围:

1. 当y1和y2异号的时候,有

这个时候两个参数a1和a2怎么取值的呢?我们用下面这个图直观的看出来:

此时ai(i=1,2)的取值范围一定是正方形内的紫色线或红色线段。

(1)以a2为例,我们来看一下它的上限:

它的上限要么是点1的C,要么是点2的C-D。这个很明显吧,如果a2<a1,那么上限就是红色线段的点2的C-D,如果a2>a1,那么上限就是紫色线段的点1的C,整理一下(上限用H表示):

如果a2<a1,H=C-D=C+a2-a1;

如果a2>a1,H=C;

把这两个总和一下,用一个式子表示就是,H=min(C , C+a2-a1),想一想,是不是这样的?

(2)我们再来看一下a2的下限:

它的下限要么是点3的-D,要么是点4的0。如果a2<a1,那么下限就是红色线段的点4的0,如果a2>a1,那么下限就是紫色线段的点3的-D,整理一下(上限用L表示):

如果a2<a1,L=0;

如果a2>a1,L=-D=a2-a1;

把这两个总和一下怎么表示?这个时候我建议你把下面的答案盖着,自己写一下,你写出来的一定是——

L=max(0 , a2-a1)

总结起来,当y1和y2异号的时候,有

L=max(0, a2-a1) <= a2 <= H=min(C , C+a2-a1)

2. 当y1和y2同号的时候,有

同与(1)相同的方法,可以推出a2的取值范围是

L=max(0, a2+a1-C) <= a2 <= H=min(C , a1+a2)

这同时也是a1的取值范围,好了,这是我们化简“终极约束”后,得到的三个“究极约束”。

  • 化简“终极问题”

复习一下,终极问题是这样的:

现在我们来化简它,我们把a1,a2专门拿出来,给“终极进化”做一个等价变形:

这个式子,不建议推导,知道就好。

我们再接着化简,引用记号:

代入到上式中去,终极问题化简为

=究极问题J(a1,a2)

l “究极约束”代入到“究极问题”中去——解“究极问题”

我们首先将“究极约束”

代入到“究极问题”中去,有:

究极问题J(a2)=

对a2求导,使其为0,得

另外,

,(

,还记得吧,SVM的模型,可别忘了)代入进去,有:

好了,式子出来了,我们下面代入实际值进行迭代求解。

  • 迭代求值

迭代求值不用多说,给定一个初始值,然后进行迭代更新。

给定a2和a1的初始值aold2,aold1,有

D= aold2+ aold1

代入到最终解里去,得到

a2上面的unc是什么?别忘了a2还要满足L<= a2 <= H,我们暂且不考虑这个范围,故用unc表示,考虑了这个范围,再把这个小尾巴unc去掉。

,原式等价于

,迭代得到:

现在把小尾巴unc去掉,

本集完,下一集将介绍如何用软件实现SMO算法,训练出一个俊美的SVM模型。

原文发布于微信公众号 - 数说工作室(shushuojun)

原文发表时间:2015-04-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

绩效管理工具(二)——温度计风格图表!

今天跟大家分享另一种用作绩效管理的图表工具——温度计风格图表! ▽ 这种图表看起来简洁、直观。数据表达清晰、无冗余。今天主要介绍两种做法,都不是特别复杂,但是需...

2818
来自专栏人工智能LeadAI

用讲故事的办法帮你理解SMO算法

SVM通常用对偶问题来求解,这样的好处有两个:1、变量只有N个(N为训练集中的样本个数),原始问题中的变量数量与样本点的特征个数相同,当样本特征非常多时,求解难...

3657
来自专栏CDA数据分析师

提问 | 如何利用一批去年的数据,来预测未来三年的数据?

文 | 邹日佳 来自知乎 1、这批去年的数据是按月份的,本身肯定会有波动,但相对稳定。 2、预测未来三年的数据是需要具体到月份。恩 3、请问有什么统计方法可以做...

2039
来自专栏数据结构与算法

洛谷P4136 谁能赢呢?

题目描述 小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘,一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合,选手只能把石头向上,下,左,右四个方向移动...

2526
来自专栏iOSDevLog

决策树模型概述

1955
来自专栏数据小魔方

图表制作理念——最大化信息墨水比

昨天给大家简单介绍了排版四原则。 今天趁热打铁,跟大家聊一聊图表制作中那些如圣经般的金言。 著名的世界级视觉设计大师——爱德华·塔夫特曾在其经典著作《The V...

2607
来自专栏数据小魔方

那些培训师都不曾告诉你的关于Excel图表的秘密~

之前在Excel图表合集那篇文章了曾提了几点Excel与其他可视化工具以及编程类软件在可视化理念方面的粗浅理解,有小伙伴儿在后台回复说还是没有听明白。 可能是...

3448
来自专栏数据结构与算法

2853 方格游戏(三维棋盘)

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 菜菜看到了...

3336
来自专栏数据小魔方

PPT图文混排三大常用技能

今天跟大家聊一聊多图型PPT最常用的三大排版技巧 ——半透明遮罩、色块衬底、渐变过渡 图文混排技巧 ▽ 虽然PPT在图文排版方面与专业的修图软件PS比起来 要有...

2696
来自专栏一“技”之长

iOS开发CoreAnimation解读之一——初识CoreAnimation核心动画编程

        众所周知,绚丽动画效果是iOS系统的一大特点,通过UIView层封装的动画,基本已经可以满足我们应用开发的所有需求,但若需要更加自由的控制动画的...

843

扫码关注云+社区