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

【用讲故事的办法帮你理解 SMO 算法】SVM通常用对偶问题来求解，这样的好处有两个：1、变量只有N个（N为训练集中的样本个数），原始问题中的变量数量与样本点的特征个数相同，当样本特征非常多时，求解难度较大。2、可以方便地引入核函数，求解非线性SVM 。求解对偶问题，常用的算法是SMO，彻底地理解这个算法对初学者有一定难度，本文尝试模拟算法作者发明该算法的思考过程，让大家轻轻松松理解SMO算法。文中的“我”拟指发明算法的大神。
001、初生牛犊不怕虎
最近，不少哥们儿向我反映，SVM对偶问题的求解算法太低效，训练集很大时，算法还没有蜗牛爬得快，很多世界著名的学者都在研究新的算法呢。听闻此言，我心头一喜：“兄弟我扬名立万的机会来了！”
我打开书，找出问题，看到是这个样子的：

文章插图
2.PNG
这明显就是一个凸二次规划问题嘛，还不好解？等等，哥们说现有算法比较慢，所以我绝对不能按照常规思路去思考，要另辟蹊径。
蹊径啊蹊径，你在哪里呢？
我冥思苦想好几天，都没有什么好办法，哎！看来扬名立万的事儿要泡汤了。放下书，我决定去湖边（注：是瓦尔登湖不？）散散心，我已经在小黑屋关得太久了。
010、得来全不费工夫
正午时分，一丝风也没有，湖边零零散散的小情侣在呢喃私语，只有苦逼的我单身一个，我坐在湖边的一块大石上，平静的湖面映出我胡子拉碴憔悴的脸，我心里苦笑：“湖想必是可怜我，映出个对影陪我。”“对影？？？！！！”我心头一道亮光闪过，犹如干裂的土地听到第一声惊雷！我突然有了新的思路！
我疯狂地跑回屋里，身后是一对对受惊的小情侣怨恨的眼神。
我开始整理自己的思绪：
这个问题如果作为单纯的凸二次规划问题来看，很难有什么新的办法，毕竟凸二次规划已经被研究得透透了。但它的特殊之处在于：它是另一个问题的对偶问题，还满足KKT条件，怎么充分利用这个特殊性呢？
我随机找一个α=（α1，α2，...，αN）。假设它就是最优解，就可以用KKT条件来计算出原问题的最优解（w,b），就是这个样子：

文章插图
w.PNG

文章插图
b.PNG
进而可以得到分离超平面：

文章插图
CodeCogsEqn.gif
按照SVM的理论，如果这个g(x)是最优的分离超平面，就有：

文章插图
kkt.PNG
姑且称这个叫 g(x)目标条件吧。
根据已有的理论，上面的推导过程是可逆的。也就是说，只要我能找到一个α，它除了满足对偶问题的两个初始限制条件：

文章插图
3.PNG
由它求出的分离超平面g(x)还能满足 g(x)目标条件，那么这个α就是对偶问题的最优解！！！
至此，我的思路已经确定了：首先，初始化一个α，让它满足对偶问题的两个初始限制条件，然后不断优化它，使得由它确定的分离超平面满足 g(x)目标条件，在优化的过程中始终确保它满足初始限制条件，这样就可以找到最优解。
我不禁感到洋洋得意了，哥们我没有按照传统思路，想着怎么去让目标函数达到最小，而是想着怎么让α满足 g(x)目标条件，牛X！我真他妈牛X！哈哈！！
011、中流击水停不住
具体怎么优化α呢？经过思考，我发现必须遵循如下两个基本原则：