概述

是由 在 1998 年提出的、针对软间隔最大化 对偶问题求解的一个算法，其基本思想很简单：如果所有变量的解都满足此优化问题的 KKT 条件，则这个优化问题的解就得到了；否则在每一步优化中，挑选出诸多参数 中的两个参数 作为变量，其余参数都视为常数，问题就变成了类似于二次方程求最大值的问题，从而我们就能求出解析解，这两个变量中，一个是违反 KKT 条件最严重的那一个，另一个由约束条件自动确定一个。

选择变量的启发式方法

先来回顾一下 中的优化目标函数：

由于要满足约束 ，所以每次需要选取两个 做为变量，这一点与坐标上升法不同。

要使优化目标函数有解，我们需要使其满足 条件中的互补松弛：

根据上面的条件我们可以得出：

由于 ，我们令

则可以推出以下三个条件：

选择第一个变量

在 中，我们称第一个变量为外循环。外循环取的是样本中违反 条件最严重的点。

我们可以借助上面推出的条件来度量一个点违反 条件的程度，具体来说，我们定义三份“差异向量”

其中第 个向量对应着第 个条件。对于不同的条件，我们按不同方式将对应向量的某些位置置为 0。

• 第一个条件： 若满足：

  • 且
  • 且

• 第二个条件： 若满足：

  • 或 且
  • 且

• 第三个条件：

  • 且
  • 且

最后只需要将这三个差异向量的平方相加作为“损失”，从而直接选出损失最大的 作为外循环即可。

选择第二个变量

第二个变量成为内循环，只需要简单的随机选取一个即可。

取出这两个变量之后，把其它变量看做常数，这样优化目标函数就变成了带约束的二次规划问题。

目标函数的优化

假设选择的两个变量是 ，把其它的 都看作常数。定义 那么原先的优化目标函数就成了：

无约束求极值

我们先暂时不管约束条件 ，通过 可以将目标函数替换成单变量形式：

我们设更新前的值为 , 更新后的值为 ，对目标函数进行一个偏导的求：

因为 SVM 中数据点的预测值为： 因此有：

另有：

将上面三个式子带入偏导中并化简得：

设 ，则有：

这样我们就求出了这两个变量在无约束情况下的解析解。

加入约束

当 时，线性限制条件可以写成：，根据 的正负可以得到不同的上下界，可以统一表示为：

• 下界：
• 上界：

当 时，限制条件可以写成：，此时上下界可以统一为：

• 下界：
• 上界：

由此可知，此约束为方形约束，下图为它的限制区域。

根据得到的上下界，我们可知加入约束后的 为：

这样就实现了对 的更新。

更新阈值 b

每次更新完一对 之后都需要重新计算阈值 ，因为它关系到 的计算和优化时误差 的计算。

当 ，根据 条件可知相应的数据点为支持向量，满足 ，两边同时乘 得：，因此 的值为：

其中，

当 时：

当 都有效时他们是相等的，即
当 都在边界上，且 时，选择它们的中点作为新的阈值：

同步更新于：SP-FA 的博客