SMO 算法概述
SMO 是由 Platt 在 1998 年提出的、针对软间隔最大化 SVM 对偶问题求解的一个算法，其基本思想很简单：在每一步优化中，挑选出诸多参数（
）中的两个参数（ai、aj）作为“真正的参数”，其余参数都视为常数，从而问题就变成了类似于二次方程求最大值的问题，从而我们就能求出解析解
具体而言，SMO 要解决的是如下对偶问题：
使得对
都有
其大致求解步骤则可以概括如下：
KKT 条件
先来看如何选取参数。在 SMO 算法中，我们是依次选取参数的：
选出违反 KKT 条件最严重的样本点、以其对应的参数作为第一个参数
第二个参数的选取有一种比较繁复且高效的方法，但对于一个朴素的实现而言、第二个参数即使随机选取也无不可
这里就有了一个叫 KKT 条件的东西，其详细的陈列会放在文末，这里就仅简要的说明一下。具体而言，对于已有的模型f=wx+b来说，ai及其对应样本(xi,yi)的 KKT 条件为：
（画得有点乱，见谅……）
图中外面有个黑圆圈的其实就是传说中的“支持向量”，其定义会在文末给出
那么我们到底应该如何刻画“违反 KKT 条件”这么个东西呢？从直观上来说，我们可以有这么一种简单有效的定义：
最后则可以简单的将三份差异向量的平方相加来作为“损失”，从而直接选出使该损失最大的作为 SMO 的第一个参数即可。具体而言：
得益于 Numpy 强大的 Fancy Indexing，上述置 0 的实现非常好写（？？？）：
# 得到 alpha > 0 和 alpha < C 的 mask
con1 = alpha > 0
con2 = alpha < C
# 算出“差异向量”并拷贝成三份
err1 = y * y_pred - 1
err2 = err1.copy()
err3 = err1.copy()
# 依次根据三个 KKT 条件，将差异向量的某些位置设为 0
# 不难看出为了直观、我做了不少重复的运算，所以这一步是可以优化的
err1[(con1 & (err1 <= 0)) | (~con1 & (err1 > 0))] = 0
err2[((~con1 | ~con2) & (err2 != 0)) | ((con1 & con2) & (err2 == 0))] = 0
err3[(con2 & (err3 >= 0)) | (~con2 & (err3 < 0))] = 0
# 算出平方和并取出使得“损失”最大的 idx
err = err1 ** 2 + err2 ** 2 + err3 ** 2
idx = np.argmax(err)
第二个参数则可以简单地随机选取，虽然这不是特别好，但效果已然不错，而且不仅实现起来更简便、运行起来也更快（其实就是我太懒）（喂）。具体代码如下：
idx = np.random.randint(len(self._y))
# 这里的 idx1 是第一个参数对应的 idx
while idx == idx1:
idx = np.random.randint(len(self._y))
return idx
至于 SMO 算法的第二步，正如前文所说，它的本质就是一个带约束的二次规划，虽然求解过程可能会比较折腾，但其实难度不大。具体步骤会放在文末，这里就暂时按下
SMO 的效果
仍是先看看螺旋线数据集上的训练过程：
略显纠结，不过还是不错的
接下来看看蘑菇数据集上的表现；单就这个数据集而言，我们实现的朴素 SVM 和 sklearn 中的 SVM 表现几乎是一致的（在使用 RBF 核时），比较具有代表性的训练曲线则如下图所示：
也算是符合 SMO 这种每次只取两个参数进行更新的训练方法的直观
相关数学理论
1）KKT 条件的详细陈列
注意到原始问题为
2）何谓“支持向量”
为方便说明，这里再次放出上文给出过的图：
图中带黑圈的样本点即是支持向量，数学上来说的话，就是对应的样本点即是支持向量。从图中不难看出，支持向量从直观上来说，就是比较难分的样本点
此外，支持向量之所以称之为“支持”向量，是因为在理想情况下，仅利用支持向量训练出来的模型和利用所有样本训练出来的模型是一致的。这从直观上是好理解的，粗略的证明则可以利用其定义来完成：非支持向量的样本对应着ai=0，亦即它对最终模型——
没有丝毫贡献，所以可以直接扔掉
3）带约束的二次规划求解方法
不妨设我们选取出来的两个参数就是和，那么问题的关键就在于如何把和相关的东西抽取出来并把其它东西扔掉
注意到我们的对偶问题为
而带约束的二次规划求解过程也算简单：只需先求出无约束下的最优解，然后根据约束“裁剪”该最优解即可
综上所述，我们就完成了一次参数的更新，之后就不断地更新直至满足停机条件即可。
