上节中我们得出了原问题的对偶问题为：
公式（4.1）
那如何求解公式4.1呢？即解出,求出w和b即可得到原型：（公式4.2）
显然，公式4.1是二次规划（QP）问题，可使用二次规划算法进行求解。然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避免这个障碍，人们利用问题本身的特性，研究出很多高效的算法，其中SMO算法就是一个典型的代表。
讲解SMO算法之前，就必须先了解什么是KTT条件？
一般有等式约束条件时，常常使用拉格朗日乘子法，即把等式约束函数用一个系数与目标函数写为一个式子，称为拉格朗日函数，通过对拉格朗日函数对各变量求导，令其为零，得到候选值集合，然后验证求得最优值。
一般有不等式约束条件时，常常使用的就是KTT条件。同样地，把所有等式、不等式约束与目标函数写成一个式子，也叫拉格朗日函数，通过一些条件，可以求出最优值的必要条件，这个条件称为KTT条件。假设不等式约束的优化问题，可以写为：
那么，拉格朗日函数为
KTT条件是说最优值必须满足以下条件：
1. L(a,b,x)对x求导等于零；
2.a*g(x)=0
3. g(x) ≤0
4. ai≥0,b≥0
5. h(x)=0
到此为止，我们就能得出公式4.1的KTT条件为：
那么，对任意训练样本,总有或对。若，则该样本将不会出现在公式4.2求和公式中，所以也不会对f(x)有任何影响。若,则必有，所对应的样本点位于最大间隔边界上，是一个支持向量。
这总结出支持向量机一个重要的性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
回到正题，求解公式4.1用到的SMO算法是什么？
SMO基本思路是先固定之外的所有参数，然后求上的极值。由于存在约束，若固定之外的其它变量，则可由其它变量导出。于是SMO算法每次选择两个变量和并固定其它参数。这样，在参数初始化后，SMO不断进行如上操作即可。
由上面的KTT条件注意到，满足KTT的和就是在最大间隔上，如果不满足KTT条件，就会使得目标函数在迭代后减小。即：KTT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。于是，SMO会选取违背KTT条件程度最大的变量，第二个变量选择使一个目标函数值减小最快的变量，但由于其计算过程的复杂程度过高，因此，SMO采用一个启发式：使选取的两变量对应样本之间的间隔最大。
具体来说，仅考虑和时，公式4.1的约束可重写为：
,其中是使成立的常数。
用去消除公式4.1中的变量,则得到一个关于的单变量二次规划问题，仅有的约束就是,这样的很容易就能求解出和
那如何求出公式4.2中的参数b呢？
注意到对任意支持向量（xs,ys），都有ysf(s)=1,即
为所有支持向量的下标集。
理论上，可选取任意支持向量并通过求解上述式子得到b。
但在现实任务中，常采用一种更鲁棒的做法：使用所有支持向量求解的平均值，即：
下节讲解核函数。
如果觉得《机器学习算法——支持向量机SVM4(SMO算法及KTT条件)》对你有帮助，请点赞、收藏，并留下你的观点哦！
