机器学习 学习笔记（10）序列最小最优化算法

序列最小最优化算法（Sequential minimal optimization）

SMO算法要解如下凸二次规划的对偶问题：

SMO算法是一种启发式算法，基本思路是：如果所有边的解都满足此优化问题的KKT条件，那么这个最优化问题的解就得到了，因为KKT条件就是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因此这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。

子问题的两个变量中只有一个是自由变量。

整个SMO算法包括两个部分，求解两个变量二次规划的解析方法和选择变量的启发式方法。

两个变量二次规划的求解方法

假设选择的两个变量是

，

，其他变量

是固定的。于是SMO最优化问题可以写成：

其中

只有两个变量，约束如下图：

​

​

假设初始的可行解为

，

，最优解为

，

，假设在沿着约束方向未经剪辑时

的最优解为

的取值范围需要满足

如果

，

，

如果

，

，

首先沿着约束方向未经剪辑即为考虑不等式约束时

的最优解

：

令

，

是函数g(2)对输入x的预测值与真实输出之差。

定理最优化问题沿着约束方向未经剪辑时的解释

，

其中

经过剪辑后

的解是：

由

求得

是：

变量的选择方法

SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。

第一个变量的选择，SMO称选择第一个变量的过程为外循环，外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第一个变量，具体地，检验训练样本点（

）是否满足KKT条件，即：

等价于

等价于

等价于

其中

该检验是在

范围内进行的。在检验过程中，外层循环首先遍历所有满足条件

的样本点，即在间隔边界上的支持向量点，检验他们是否满足KKT条件，如果这些样本点都满足KKT条件，那么遍历整个训练集，检验它们是否满足KKT条件。

第二个遍历的选择，SMO称选择第二个变量的过程为内循环。假设在外层循环中已经找到了第一个变量

，现在要在内层循环中找到第二个变量

。第二个遍历选择的标准是希望能使

有足够大的变化。

由

可知，

是依赖于

的，为了加快计算速度，一种简单的做法是选择

，使其对应的

最大。因为

已定，

也确定了。如果

是正的，那么选择最小的

作为

。如果

是负的，那么选择最大的

作为

。为了节省计算时间将所有的

值保存在一个列表中。

在特殊情况下，如果内层循环通过以上方法选择的

不能使目标函数有足够的下降，那么采用以下启发式方法继续选择

。遍历在间隔边界上的支持向量点，依次将其对应的变量作为

试用，直到目标函数有足够的下降。若找不到和是的

，那么遍历训练数据集，若仍然找不到合适的

，则放弃第一个

，在通过外层循环求另外的

计算阈值b和差值

，每次完成两个变量的优化后，都要重新计算阈值b，当

时，由KKT条件可知：

于是：

同理：

如果

都满足条件

，那么

。如果

是0或C，那么

和

以及它们之间的数都符合KKT条件的阈值，这时候选择它们的中点作为

。

还需要更新相应的

其中S是所有支持向量

的集合。

代码实现可以参见：https://cloud.tencent.com/developer/article/1326806

参考：

1. 《统计学习方法》