任何关于算法、编程、AI行业知识或博客内容的问题，可以随时扫码关注公众号「图灵的猫」，加入”学习小组“，沙雕博主在线答疑~此外，公众号内还有更多AI、算法、编程和大数据知识分享，以及免费的SSR节点和学习资料。其他平台（知乎/B站）也是同名「图灵的猫」，不要迷路哦~

SMO算法最通俗易懂的解释

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

001、初生牛犊不怕虎

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

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

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

蹊径啊蹊径，你在哪里呢？

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

010、得来全不费工夫

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

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

我开始整理自己的思绪：

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

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

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

CodeCogsEqn.gif

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

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

由它求出的分离超平面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，它是这样的：