您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2019-11-04 13:25:26  来源:  作者:

SVM通常用对偶问题来求解,这样的好处有两个:1、变量只有N个(N为训练集中的样本个数),原始问题中的变量数量与样本点的特征个数相同,当样本特征非常多时,求解难度较大。2、可以方便地引入核函数,求解非线性SVM。求解对偶问题,常用的算法是SMO,彻底地理解这个算法对初学者有一定难度,本文尝试模拟算法作者发明该算法的思考过程,让大家轻轻松松理解SMO算法。文中的“我”拟指发明算法的大神。

001、初生牛犊不怕虎

最近,不少哥们儿向我反映,SVM对偶问题的求解算法太低效,训练集很大时,算法还没有蜗牛爬得快,很多世界著名的学者都在研究新的算法呢。听闻此言,我心头一喜:“兄弟我扬名立万的机会来了!”

我打开书,找出问题,看到是这个样子的:

 

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

2.PNG

这明显就是一个凸二次规划问题嘛,还不好解?等等,哥们说现有算法比较慢,所以我绝对不能按照常规思路去思考,要另辟蹊径。

蹊径啊蹊径,你在哪里呢?

我冥思苦想好几天,都没有什么好办法,哎!看来扬名立万的事儿要泡汤了。放下书,我决定去湖边(注:是瓦尔登湖不?)散散心,我已经在小黑屋关得太久了。

010、得来全不费工夫

正午时分,一丝风也没有,湖边零零散散的小情侣在呢喃私语,只有苦逼的我单身一个,我坐在湖边的一块大石上,平静的湖面映出我胡子拉碴憔悴的脸,我心里苦笑:“湖想必是可怜我,映出个对影陪我。”“对影???!!!”我心头一道亮光闪过,犹如干裂的土地听到第一声惊雷!我突然有了新的思路!

我疯狂地跑回屋里,身后是一对对受惊的小情侣怨恨的眼神。

我开始整理自己的思绪:

这个问题如果作为单纯的凸二次规划问题来看,很难有什么新的办法,毕竟凸二次规划已经被研究得透透了。但它的特殊之处在于:它是另一个问题的对偶问题,还满足KKT条件,怎么充分利用这个特殊性呢?

我随机找一个α=(α1,α2,...,αN)。假设它就是最优解,就可以用KKT条件来计算出原问题的最优解(w,b),就是这个样子:

 

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

w.PNG

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

b.PNG

进而可以得到分离超平面:

 

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

CodeCogsEqn.gif

按照SVM的理论,如果这个g(x)是最优的分离超平面,就有:

 

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

kkt.PNG

姑且称这个叫 g(x)目标条件 吧。

根据已有的理论,上面的推导过程是可逆的。也就是说,只要我能找到一个α,它除了满足对偶问题的两个 初始限制条件 :

 

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

3.PNG

由它求出的分离超平面g(x)还能满足 g(x)目标条件 ,那么这个α就是对偶问题的最优解!!!

至此,我的思路已经确定了:首先,初始化一个α,让它满足对偶问题的两个 初始限制条件,然后不断优化它,使得由它确定的分离超平面满足 g(x)目标条件 ,在优化的过程中始终确保它满足 初始限制条件 ,这样就可以找到最优解。

我不禁感到洋洋得意了,哥们我没有按照传统思路,想着怎么去让目标函数达到最小,而是想着怎么让α满足 g(x)目标条件 ,牛X!我真他妈牛X!哈哈!!

011、中流击水停不住

具体怎么优化α呢?经过思考,我发现必须遵循如下两个基本原则:

  • 每次优化时,必须同时优化α的两个分量,因为只优化一个分量的话,新的α就不再满足 初始限制条件 中的 等式条件 了。
  • 每次优化的两个分量应当是违反 g(x)目标条件 比较多的。就是说,本来应当是大于等于1的,越是小于1违反 g(x)目标条件 就越多,这样一来,选择优化的两个分量时,就有了基本的标准。

好,我先选择第一个分量吧,α的分量中有等于0的,有等于C的,还有大于0小于C的,直觉告诉我,先从大于0小于C的分量中选择是明智的,如果没有找到可优化的分量时,再从其他两类分量中挑选。

现在,我选了一个分量,就叫它α1吧,这里的1表示它是我选择的第一个要优化的分量,可不是α的第1个分量。

为啥我不直接选两个分量呢?

我当时是这么想的,选择的两个分量除了要满足违反 g(x)目标条件 比较多外,还有一个重要的考量,就是经过一次优化后,两个分量要有尽可能多的改变,这样才能用尽可能少的迭代优化次数让它们达到 g(x)目标条件 ,既然α1是按照违反 g(x)目标条件 比较多来挑选的,我希望选择α2时,能够按照 优化后让α1、α2有尽可能多的改变 来选。

你可能会想,说的怪好听的,倒要看你怎么选α2?

经过我一番潜心思考,我还真找到一个选α2的标准!!

我为每一个分量算出一个指标E,它是这样的:

 

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

E.PNG

我发现,当|E1-E2|越大时,优化后的α1、α2改变越大。所以,如果E1是正的,那么E2越负越好,如果E1是负的,那么E2越正越好。这样,我就能选到我的α2啦。

啥,你问这是为什么?

这个回头再说,现在要开始优化我的α1、α2啦。

100、 无限风光在险峰

怎么优化α1、α2可以确保优化后,它们对应的样本能够满足 g(x)目标条件 或者违反 g(x)目标条件 的程度变轻呢?我这人不贪心,只要优化后是在朝着好的方向发展就可以。

本以为峰回路转,谁知道峰回之后是他妈一座更陡峭的山峰!我心一横,你就是90度的山峰,哥们我也要登它一登!!

在沉思中,我的眼睛不经意地瞟见了对偶问题:

 

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

2.PNG

灵光一闪,计上心来!

虽然我不知道怎样优化α1、α2,让它们对应的样本违反 g(x)目标条件 变轻,但是我可以让它们优化后目标函数的值变小啊!使目标函数变小,肯定是朝着正确的方向优化!也就肯定是朝着使违反 g(x)目标条件 变轻的方向优化,二者是一致的啊!!

我真是太聪明了!

此时,将α1、α2看做变量,其他分量看做常数,对偶问题就是一个超级简单的二次函数优化问题:

 

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

10.png

其中:

 

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

11.png

 

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

12.png

至此,这个问题已经变得超级简单了!

举例来说明一下,假设y1和y2都等于1,那么第一个限制条件就变成了

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

13.png

首先,将α1=K-α2代入目标函数,这时目标函数变成了关于α2的一元函数,对α2求导并令导数为0可以求出α2_new。

然后,观察限制条件,第一个条件α1=K-α2相当于

0≦K-α2≦C

进而求得:

K-C≦α2≦K,再加上原有的限制

0≦α2≦C,可得

max(K-C,0)≦α2≦min(K,C)

如果α2_new就在这个限制范围内,OK!求出α1_new,完成一轮迭代。如果α2_new不在这个限制范围内,进行截断,得到新的α2_new_new,据此求得α1_new_new,此轮迭代照样结束!!



Tags:SMO 算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关推荐
SVM通常用对偶问题来求解,这样的好处有两个:1、变量只有N个(N为训练集中的样本个数),原始问题中的变量数量与样本点的特征个数相同,当样本特征非常多时,求解难度较大。2、可以方便...【详细内容】
2019-11-04  Tags: SMO 算法  点击:(49)  评论:(0)  加入收藏
▌简易百科推荐
架构头条 作者 | theinsaneapp.com译者 | 张健欣策划 | 万佳今天,我们会讨论一些不同的东西,例如 Spotify、YouTube、Signal Messenger、Amazon 等科技巨头的推荐算法,以及像 U...【详细内容】
2021-07-15  技术联盟总坛    Tags:推荐算法   点击:(2)  评论:(0)  加入收藏
说起区块链,似乎大家都懂一点,再往细里一问,似乎又都不懂了。比如,你问一个人:为什么要挖矿,挖的到底是啥。怕是没几个明白人。本文就是要给你讲明白!前言人们一说起区块链,就常常说...【详细内容】
2021-07-13  暖男在奋斗的路上    Tags:加密算法   点击:(6)  评论:(0)  加入收藏
2021年5月26日,极狐阿尔法S 华为HI版正式下线,标志着华为进军自动驾驶迈出关键一步,实现了量产。...【详细内容】
2021-07-08  佐思汽车研究    Tags:自动驾驶算法   点击:(9)  评论:(0)  加入收藏
今天讲的是最有深度的抖音算法机制的剖析,解密平台核心算法机制。主要深度讲下抖音是算法机制到底是怎么工作的,我们的帐号标签原型到底是怎么建立起来的,字节跳动的人工智能AI...【详细内容】
2021-07-05  国阜电商    Tags:抖音平台算法   点击:(11)  评论:(0)  加入收藏
RSA非对称加密RSA是一种常用的非对称加密算法,加密和加密使用不同的密钥,常用于要求安全性较高的加密场景,比如接口的验签和接口数据的加密与解密。与非对称加密算法对比,其安全...【详细内容】
2021-07-04  Java架构学习指南  简书  Tags:接口   点击:(12)  评论:(0)  加入收藏
导读:用户标签是个性化推荐、计算广告、金融征信等众多大数据业务应用的基础,它是原始的用户行为数据和大数据应用之间的桥梁,本文会介绍用户标签的构建方法,也就是用户画像技术...【详细内容】
2021-07-02  华章科技    Tags:用户画像   点击:(16)  评论:(0)  加入收藏
随机红包算法,每个人都有自己的实现思路。package com.jmmq.load.jim.algorithm;import java.math.BigDecimal;import java.util.Arrays;import java.util.List;import java....【详细内容】
2021-07-02  非鸽传书  今日头条  Tags:算法   点击:(10)  评论:(0)  加入收藏
在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念哈希...【详细内容】
2021-06-25  C语言编程    Tags:哈希算法   点击:(26)  评论:(0)  加入收藏
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Linux天神    Tags:红黑树   点击:(19)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n≥0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  数据人plus  今日头条  Tags:数据结构   点击:(37)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条