(4)、仅含两个Langrange乘子解析解

为了描述方便定义如下符号：

于是目标函数就变成了：

注意第一个约束条件：，可以将看作常数，有(为常数，我们不关心它的值)，等式两边同时乘以，得到（为常数，其值为，我们不关心它，）。将用上式替换则得到一个只含有变量的求极值问题：

这下问题就简单了，对求偏导数得到：

将、带入上式有：

                    

带入、，用，表示误差项(可以想象，即使分类正确，的值也可能很大)、(是原始空间向特征空间的映射)，这里可以看成是一个度量两个样本相似性的距离，换句话说，一旦选择核函数则意味着你已经定义了输入空间中元素的相似性。

最后得到迭代式：

注意第二个约束条件——那个强大的盒子：，这意味着也必须落入这个盒子中，综合考虑两个约束条件，下图更直观：

和异号的情形

和同号的情形

可以看到两个乘子既要位于边长为C的盒子里又要在相应直线上，于是对于的界来说，有如下情况：

  

整理得下式：

又因为，，消去后得到：

(5)、启发式的选择方法

根据选择的停止条件可以确定怎么样选择点能对算法收敛贡献最大，例如使用监视可行间隙的方法，一个最直白的选择就是首先优化那些最违反KKT条件的点，所谓违反KKT条件是指：

由前面的停止条件3可知，对可行间隙贡献最大的点是那些

其中，

取值大的点，这些点导致可行间隙变大，因此应该首先优化它们，原因如下：

1、当满足KKT条件：即时，

当违背KKT条件：即时，，于是

可见，由于违背KKT条件导致可行间隙变大；

2、当满足KKT条件：即时，

当违背KKT条件：即时

若则且，其中

若则且，其中

可见，由于违背KKT条件依然导致可行间隙变大；

3、当满足KKT条件：即时，

当违背KKT条件：即时，且，其中

可见，由于违背KKT条件还是会导致可行间隙变大。

SMO的启发式选择有两个策略：

启发式选择1：

最外层循环，首先，在所有样本中选择违反KKT条件的一个乘子作为最外层循环，用“启发式选择2”选择另外一个乘子并进行这两个乘子的优化，接着，从所有非边界样本中选择违反KKT条件的一个乘子作为最外层循环，用“启发式选择2”选择另外一个乘子并进行这两个乘子的优化(之所以选择非边界样本是为了提高找到违反KKT条件的点的机会)，最后，如果上述非边界样本中没有违反KKT条件的样本，则再从整个样本中去找，直到所有样本中没有需要改变的乘子或者满足其它停止条件为止。

启发式选择2：

内层循环的选择标准可以从下式看出：

要加快第二个乘子的迭代速度，就要使最大，而在上没什么文章可做，于是只能使最大。

确定第二个乘子方法：

1、首先在非界乘子中寻找使得最大的样本； 
        2、如果1中没找到则从随机位置查找非界乘子样本； 
        3、如果2中也没找到，则从随机位置查找整个样本(包含界上和非界乘子)。

(6)、关于两乘子优化的说明

由式子

可知：

于是对于这个单变量二次函数而言,如果其二阶导数，则二次函数开口向下，可以用上述迭代的方法更新乘子，如果，则目标函数只能在边界上取得极值(此时二次函数开口向上)，换句话说，SMO要能处理取任何值的情况，于是在时有以下式子：

1、时：

2、时：

3、                   

分别将乘子带入得到两种情况下的目标函数值： 和。显然，哪种情况下目标函数值最大，则乘子就往哪儿移动，如果目标函数的差在某个指定精度范围内，说明优化没有进展。

另外发现，每一步迭代都需要计算输出进而得到，于是还要更新阈值，使得新的乘子、满足KKT条件，考虑、至少有一个在界内，则需要满足，于是的迭代可以这样得到：

1、设在界内，则：

又因为：

于是有：

等式两边同乘后移项得：

；

2、设在界内，则：

；

3、设、都在界内，则：情况1和情况2的值相等，任取一个；

4、设、都不在界内，则：取值为情况1和情况2之间的任意值。

(7)、提高SMO的速度

从实现上来说，对于标准的SMO能提高速度的地方有：

1、能用缓存的地方尽量用，例如，缓存核矩阵，减少重复计算，但是增加了空间复杂度；

2、如果SVM的核为线性核时候，可直接更新，毕竟每次计算的代价较高，于是可以利用旧的乘子信息来更新，具体如下：

，应用到这个性质的例子可以参见SVM学习——Coordinate Desent Method。

3、关注可以并行的点，用并行方法来改进，例如可以使用MPI，将样本分为若干份，在查找最大的乘子时可以现在各个节点先找到局部最大点，然后再从中找到全局最大点；又如停止条件是监视对偶间隙，那么可以考虑在每个节点上计算出局部可行间隙，最后在master节点上将局部可行间隙累加得到全局可行间隙。

对标准SMO的改进有很多文献，例如使用“Maximal Violating Pair ”去启发式的选择乘子是一种很有效的方法，还有使用“ Second Order Information”的方法，我觉得理想的算法应该是：算法本身的收敛速度能有较大提高，同时算法可并行程度也较高。

4. SMO更新的版本（Fan，2005）

前面提到过，SMO可以分为两部分：

（1）如何选择每次迭代时候的目标工作集，即选择哪两个拉格朗日乘子来迭代。

（2）如何对选择好的工作集（拉格朗日乘子）进行更新迭代。

而如何选择工作集，是SMO算法很重要的一个部分，因为不同的选择方式可以导致不同的训练速度。

Rong-En Fan等人在2005的paper《Working Set Selection Using Second Order Information for Training Support Vector Machines》介绍了每次迭代时几种不同的工作集选择方法。

首先还是放出SMO需要优化的目标函数：

（1）Algorithm 1 (SMO-type decomposition method)

（2）WSS 1 (Working set selection via the “maximal violating pair”)

这个working set selection是Keerthi等人在2001年提出的，在2001年发布的libSVM中有所应用。

该working set selection可以由（1）式的KKT条件得出：假设存在向量是（1）式的解，则必然存在实数和两个非负向量使得下式成立：

其中，是目标函数的梯度。

上面的条件可以被重写为：

进一步，有

令，

则目标函数存在最优解的条件是：

由上面这个关于“Violating pair”的定义可以看出，最大程度上违反（6）式条件的{i, j} pair 即是working set的最佳选择，因为我们需要对这些最违反（6）式的{i, j} pair做更新迭代，让它们符合（6）式的要求，便会逐步让目标函数得到最优值。具体的理论定理如下：

有趣的是，选择最大程度上违反KKT条件的{i, j} pair 与 “求目标函数的一阶近似”时候取得的{i, j} pair是一致的。即通过WSS 1获得的{i, j} pair满足：

通过定义，（8a）的目标函数即是对的一阶近似进行求最优解：

其中，是由于，而（8b）和（8c）是由于。由于（8a）是线性函数，则避免了目标函数取值无穷小。

第一眼看上去，（7）式似乎需要对所有的拉格朗日乘子遍历一遍才能够找出最优的{i，j} pair，然而，WSS 1可以在线性时间复杂度内找到最优值。证明如下：

Proof

（3）A New Working Set Selection

上面是使用了目标函数的一阶近似作为代替进行优化，于是乎，我们可以再进一步，使用目标函数的二阶近似作为代替进行优化：

（4）WSS 2 (Working set selection using second order information)

下面的理论证明按照WSS 2可以有效地解决（11）式中的最优值问题：

（5）Non-Positive Definite Kernel Matrices

前面的方法并没有涵盖的情况，对于这种情况，Chen等人在2006年给出了解决方法：

（6）WSS 3 (Working set selection using second order information: any symmetric K)

于是，使用WSS 3来对SMO-type 分解方法选择working set的步骤为：

（7）Algorithm 2 (An SMO-type decomposition method using WSS 3)