【干货】支持向量机原理(四)SMO算法原理

公众号后台回复“python“,立刻领取100本机器学习必备Python电子书

在SVM的前三篇里,我们优化的目标函数最终都是一个关于向量的函数。而怎么极小化这个函数,求出对应的向量,进而求出分离超平面我们没有讲。本篇就对优化这个关于向量的函数的SMO算法做一个总结。

1. 回顾SVM优化目标函数

我们首先回顾下我们的优化目标函数:$

我们的解要满足的KKT条件的对偶互补条件为:$

根据这个KKT条件的对偶互补条件,我们有:

由于,我们令,则有:

2. SMO算法的基本思想

上面这个优化式子比较复杂,里面有m个变量组成的向量需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量,将其他的变量都视为常数。由于.假如将 固定,那么之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。

为了后面表示方便,我们定义

由于都成了常量,所有的常量我们都从目标函数去除,这样我们上一节的目标优化函数变成下式:

3. SMO算法目标函数的优化

为了求解上面含有这两个变量的目标优化问题,我们首先分析约束条件,所有的都要满足约束条件,然后在约束条件下求最小。

根据上面的约束条件,又由于均只能取值1或者-1, 这样在[0,C]和[0,C]形成的盒子里面,并且两者的关系直线的斜率只能为1或者-1,也就是说的关系直线平行于[0,C]和[0,C]形成的盒子的对角线,如下图所示:

由于的关系被限制在盒子里的一条线段上,所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是的优化问题。由于我们采用的是启发式的迭代法,假设我们上一轮迭代得到的解是,假设沿着约束方向未经剪辑的解是.本轮迭代完成后的解为

由于必须满足上图中的线段约束。假设L和H分别是上图中所在的线段的边界。那么很显然我们有:

而对于L和H,我们也有限制条件如果是上面左图中的情况,则

如果是上面右图中的情况,我们有:

也就是说,假如我们通过求导得到的,则最终的应该为:

那么如何求出呢?很简单,我们只需要将目标函数对求偏导数即可。

首先我们整理下我们的目标函数。

为了简化叙述,我们令

其中就是我们在第一节里面的提到的$

我们令

这样我们的优化目标函数进一步简化为:

由于,并且,可以得到用表达的式子为:

将上式带入我们的目标优化函数,就可以消除,得到仅仅包含的式子。

忙了半天,我们终于可以开始求了,现在我们开始通过求偏导数来得到。

整理上式有:

将带入上式,我们有:

我们终于得到了的表达式:

利用上面讲到的和的关系式,我们就可以得到我们新的了。利用和的线性关系,我们也可以得到新的。

4. SMO算法两个变量的选择

SMO算法需要选择合适的两个变量做迭代,其余的变量做常量来进行优化,那么怎么选择这两个变量呢?

4.1 第一个变量的选择

SMO算法称选择第一个变量为外层循环,这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点,要满足的KKT条件我们在第一节已经讲到了:

一般来说,我们首先选择违反这个条件的点。如果这些支持向量都满足KKT条件,再选择违反 和 的点。

4.2 第二个变量的选择

SMO算法称选择第二一个变量为内层循环,假设我们在外层循环已经找到了, 第二个变量的选择标准是让有足够大的变化。由于定了的时候,也确定了,所以要想最大,只需要在为正时,选择最小的作为, 在为负时,选择最大的作为,可以将所有的保存下来加快迭代。

如果内存循环找到的点不能让目标函数有足够的下降, 可以采用遍历支持向量点来做,直到目标函数有足够的下降, 如果所有的支持向量做都不能让目标函数有足够的下降,可以跳出循环,重新选择

4.3 计算阈值b和差值

在每次完成两个变量的优化之后,需要重新计算阈值b。当时,我们有

于是新的为:

计算出为:

可以看到上两式都有,因此可以将用表示为:

同样的,如果, 那么有:

最终的为:

得到了我们需要更新:

其中,S是所有支持向量的集合。

好了,SMO算法基本讲完了,我们来归纳下SMO算法。

5. SMO算法总结

输入是m个样本,其中x为n维特征向量。y为二元输出,值为1,或者-1.精度e。

输出是近似解

1)取初值

2)按照4.1节的方法选择,接着按照4.2节的方法选择,求出新的。

3)按照下式求出

4)利用和的关系求出

5)按照4.3节的方法计算和

6)在精度e范围内检查是否满足如下的终止条件:

7)如果满足则结束,返回,否则转到步骤2)。

SMO算法终于写完了,这块在以前学的时候是非常痛苦的,不过弄明白就豁然开朗了。希望大家也是一样。写完这一篇, SVM系列就只剩下支持向量回归了,胜利在望!

‍‍‍‍‍‍‍‍

1.机器学习原来这么有趣!【第一章】

2.机器学习原来这么有趣!【第二章】:用机器学习制作超级马里奥的关卡

3.机器学习从零开始系列连载(1)——基本概念

4.机器学习从零开始系列连载(2)——线性回归

5.机器学习从零开始系列连载(3)——支持向量机

6.机器学习从零开始系列连载(4)——逻辑回归

7.机器学习从零开始系列连载(5)——Bagging and Boosting框架

8.机器学习从零开始系列连载(6)—— Additive Tree 模型

记得把公号加星标,会第一时间收到通知。

创作不易,如果觉得有点用,希望可以随手转发或者”在看“,拜谢各位老铁

(0)

相关推荐

  • 吴恩达《Machine Learning》精炼笔记 7:支持向量机 SVM

    今天带来第七周课程的笔记:关于支持向量机SVM的相关知识点.内容包含: 硬间隔 支持向量 软间隔 对偶问题 优化目标Optimization Objectives 主要是讲解如何从逻辑回归慢慢的推导出 ...

  • 支持向量机(SVM)的约束和无约束优化、理论和实现

    优化是机器学习领域最有趣的主题之一.我们日常生活中遇到的大多数问题都是通过数值优化方法解决的.在这篇文章中,让我们研究一些基本的数值优化算法,以找到任意给定函数(这对于凸函数最有效)的局部最优解.让我 ...

  • 深入解析机器学习算法有哪些?

    机器人学是一个多领域的交叉学科,包含了许多学科:包括概率论.统计学.逼近论.凸分析.算法复杂性理论等.专攻计算机如何模拟或实现人的学习行为,以获得新的知识或技能,重组已有的知识结构,使其持续地提高其表 ...

  • 从传感器到算法原理,机器人、视觉避障都在这里了

    避障是指移动机器人在行走过程中,通过传感器感知到在其规划路线上存在静态或动态障碍物时,按照 一定的算法实时更新路径,绕过障碍物,最后达到目标点. 不管是要进行导航规划还是避障,感知周边环境信息是第一步 ...

  • 干货|终于明白集成电路的工作原理了!

    什么是集成电路 集成电路,英文为IntegratedCircuit,缩写为IC:顾名思义,就是把一定数量的常用电子元件,如电阻.电容.晶体管等,以及这些元件之间的连线,通过半导体工艺集成在一起的具有特 ...

  • ​英国摄影大师总结四条构图原理,超级易懂

    构图本质上就是组织, 使画框里的所有图像元素有序化. 为什么某些照片能给人留下深刻印象, 为什么某些影像组织方式 会有某种可预计的效果. 两种最基本的原理是对比和平衡. 对比强调的是照片中图像元素之间 ...

  • 自动驾驶技术的算法原理、技术大图,以及未来发展

    导读:车在给人们生活带来便利的同时,也导致了交通拥堵.环境污染.交通事故等诸多问题.交通事故不仅带来巨大的经济损失,对生命健康的危害更加严重.实现安全.智能化的自动驾驶技术成为了人们的愿望.阿里巴巴布 ...

  • 干货分享 — D类功放工作原理

    D类功放又叫数字功放,应用领域有:手机.笔记本电脑.平板电视.家用功放.舞台功放,公共广播等. 优点:体积小.重量轻.效率高.  D类功放按组成结构可以分为信号调制器.PWM驱动信号.开关放大电路和解 ...

  • 论文|Sentence2Vec & GloVe 算法原理、推导与实​现

    Sentence2vec Sentence2vec 是2017年发表于ICLR(国际学习展示回忆)的一篇论文,其全称为:A Simple but tough-to-beat baseline for ...

  • 干货 | 开关柜带电局放检测原理及案例介绍

    电气设备带电局放检测技术是发现设备潜伏性运行隐患的有效手段.传统常规的试验方法可以检查出贯穿性绝缘缺陷及明显的绝缘缺陷,但需要在停电情况下进行. 带电局放检测可以在电气设备正常运行状态下进行检测,不需 ...

  • 高考化学选修四之化学反应原理重难点知识整理!

    历 高中化学学霸笔记,全是考试重点! 史 超级全的高中化学知识点总结!还不收藏! 文 高中所有的化学方程式集合,建议高中同学收藏 章 语数外.物化生.政史地9科考点大汇总‼️全面掌握高中3年知识点!( ...

  • 深入理解 CAS 算法原理

    深入理解 CAS 算法原理