手把手教你实现SVM算法（二）

一．SMO算法的原理

SMO算法和以往的一些SVM改进算法一样，是把整个二次规划问题分解为很多较易处理的小问题，所不同的是，只有SMO算法把问题分解到可能达到的最小规模：每次优化只处理两个样本的优化问题，并且用解析的方法进行处理。我们将会看到，这种与众不同的方法带来了一系列不可比拟的优势。

对SVM来说，一次至少要同时对两个样本进行优化（就是优化它们对应的Lagrange乘子），这是因为等式约束的存在使得我们不可能单独优化一个变量。

所谓“最小优化”的最大好处就是使得我们可以用解析的方法求解每一个最小规模的优化问题，从而完全避免了迭代算法。

当然，这样一次“最小优化”不可能保证其结果就是所优化的Lagrange乘子的最终结果，但会使目标函数向极小值迈进一步。我们再对其它Lagrange乘子做最小优化，直到所有乘子都符合KKT条件时，目标函数达到最小，算法结束。

这样，SMO算法要解决两个问题：一是怎样解决两个变量的优化问题，二是怎样决定先对哪些Lagrange乘子进行优化。

二．两个Lagrange乘子的优化问题（子程序takeStep）

我们在这里不妨设正在优化的两个Lagrange乘子对应的样本正是第一个和第二个，对两个Lagrange乘子α₁和α₂，在不改变其他乘子的情况下，它们的约束条件应表达为正方形内的一条线段。如图所示：

在这条线段上求一个函数的极值，相当于一个一维的极值问题。我们可以把α₁用α₂表示，对α₂求无条件极值，如果目标函数是严格上凹的，最小值就一定在这一极值点（极值点在区间内）或在区间端点（极值点在区间外）。α₂确定后，α₁也就确定下来了。因此我们先找到α₂优化区间的上下限制，再在这个区间中对α₂求最小值。

由图1我们容易得到α₂的上下限应为：

L=max(0,α₂－α₁)，H=min(C,C+α₂ –α₁) , 若y₁与y₂异号；

L=max(0,α₂ +α₁－C), H=min(C, α₂ +α₁) ,若y₁与y₂同号；

令s=y₁y₂标志这两个样本是否同类，则有

L=max(0, α₂+sα₁－ 1/2 (s+1)C), H=min(C, α₂ +sα₁ –1/2 (s－1)C)

而α₁和α₂在本次优化中所服从的等式约束为：

α₁＋sα₂=α⁰₁+sα⁰₂=d

下面我们推导求最小值点α₂的公式：由于只有α₁，α₂两个变量需要考虑，目标函数可以写成

Wolfe(α₁,α₂)=1/2 K₁₁α²₁+1/2 K₂₂α²₂+ sK₁₂α₁α₂ + y₁α₁v₁ +y₂α₂v₂ －α₁ －α₂+常数

其中K_ij=K(x_i,x_j) , v_i=y₃α⁰₃K_i3+…+y_lα⁰_lK_il = u_i+b⁰－ y₁α⁰₁K_1i – y₂α⁰₁K_2i

上标为0的量表示是本次优化之前Lagrange乘子的原值。

将α₂用α₁表示并代入目标函数：

Wolfe（α₂）=1/2 K₁₁(d-sα₂)²+1/2 K₂₂α²₂+sK₁₂(d-sα₂) α₂

+y₁(d-sα₂)v₁ – d+sα₂+y₂α₂v₂－α₂+常数

对α₂求导：

dWolfe(α₂)/dα₂

=－sK₁₁(d－sα₂)+K₂₂α₂－K₁₂α₂+sK₁₂(d－sα₂)－y₂v₂+s+y₂v₂－1 ＝0

如果Wolfe函数总是严格上凹的，即二阶导数K₁₁+K₂₂－2K₁₂>0, 那么驻点必为极小值点，无条件的极值点就为

α₂＝[s(K₁₁－K₁₂)d+y₂(v₁－v₂)＋1－s] / (K₁₁＋K₂₂－2K₁₂)

将d,v与α⁰,u之间关系代入，就得到用上一步的α⁰₂，u₁,u₂表示的α₂的无条件最优点：

α₂＝[α⁰₂(K₁₁＋K₂₂－2K₁₂) +y₂(u₁－u₂＋y₂－y₁)] / (K₁₁＋K₂₂－2K₁₂)

令η=K₁₁＋K₂₂－2K₁₂为目标函数的二阶导数，E_i=u_i－y_i为第i个训练样本的“误差”，这个式子又可以写为

α₂＝α⁰₂＋y₂(E₁－E₂)/η

除非核函数K不满足Mercer条件（也就是说不能作为核函数），η不会出现负值。但η=0是可以出现的情况。这时我们计算目标函数在线段两个端点上的取值，并将Lagrange乘子修正到目标函数较小的端点上：

f₁=y₁(E₁+b)－α₁K(x₁,x₁)­－sα₂K(x₁,x₁)

f₂=y₂(E₂+b)－sα₁K(x₁,x₂)­－α₂K(x₂,x₂)

L₁=α₁+s(α₂－L)

H₁=α₁+s(α₂－H)

WolfeL=L₁f₁+Lf₂+1/2 L²₁K(x₁,x₁)+1/2 L²K(x₂,x₂)+sLL₁K(x₁,x₂)

WolfeH=H₁f₁+Hf₂+1/2 H²₁K(x₁,x₁)+1/2 H²K(x₂,x₂)+sHH₁K(x₁,x₂)

当两个端点上取得相同的目标函数值时，目标函数在整条线段上的取值都会是一样的（因为它是上凹的），这时不必对α₁，α₂作出修正。

α₂的无条件极值确定后，再考虑上下限的限制，最终的α₂为

最后，由等式约束确定α₁：

α₁^*=α₁+s(α₂－α₂^*)

三．选择待优化Lagrange乘子的试探找点法

事实上即使我们不采用任何找点法，只是按顺序抽取α_i，α_j的所有组合进行优化，目标函数也会不断下降，直到任一对α_i，α_j都不能继续优化，目标函数就会收敛到极小值。我们采取某种找点方法只是为了使算法收敛得更快。

这种试探法先选择最有可能需要优化的α₂，再针对这样的α₂选择最有可能取得较大修正步长的α₁。这样，我们在程序中使用两个层次的循环：

内层循环（子程序examineExample）针对违反KKT条件的样本选择另一个样本与它配对优化（指优化它们的Lagrange乘子），选择的依据是尽量使这样一对样本能取得最大优化步长。对其中一个Lagrange乘子α₂来说优化步长为|(E₁－E₂)/η|,但由于核函数估算耗时较大，我们只用|E₁－E₂|来大致估计有可能取得的步长大小。也就是说，选出使得|E₁－E₂|最大的样本作为第二个样本。需要注意的是，这样的步长估计是比较粗略的，选择出来的一对样本有时非但不能“一劳永逸”地“一步到位”，反而不能作出进一步调整，（例如η=0的情况，最小优化问题的二次型只是半正定的）。这时我们遍历所有非边界样本（非边界样本就是Lagrange乘子不在边界0或C上的样本），继续寻找能与α₂配对优化的α₁，如果这样的样本在非边界样本中找不到，再遍历所有样本。这两次遍历都是从随机位置开始的，以免算法总是在一开始遍历就向固定的方向偏差。在极端退化的情形，找不到与α₂配对能作出进一步调整的α₁，这时我们放弃第一个样本。

外层循环（主程序smo）遍历非边界样本或所有样本：优先选择遍历非边界样本，因为非边界样本更有可能需要调整，而边界样本常常不能得到进一步调整而留在边界上（可以想象大部分样本都很明显不可能是支持向量，它们的Lagrange乘子一旦取得零值就无需再调整）。循环遍历非边界样本并选出它们当中违反KKT条件的样本进行调整，直到非边界样本全部满足KKT条件为止。当某一次遍历发现没有非边界样本得到调整时，就遍历所有样本，以检验是否整个集合也都满足KKT条件。如果在整个集合的检验中又有样本被进一步优化，就有必要再遍历非边界样本。这样，外层循环不停地在“遍历所有样本”和“遍历非边界样本”之间切换，直到整个训练集都满足KKT条件为止。

以上用KKT条件对样本所作检验都是达到一定精度就可以了，例如正侧的非边界样本的输出u_i可以在1的一定公差范围之内，通常这一公差（tolerance）取0.001，如果要求十分精确的输出算法就不能很快收敛。

四．每次最小优化后的重置工作

每做完一次最小优化，必须更新每个样本的误差（Error Cache），以便用修正过的分类面对其它样本再做KKT检验，以及选择第二个配对优化样本时估计步长之用。

更新Error Cache首先要重置阈值b 。我们可直接利用刚刚被优化的两个样本的信息在原阈值b₀基础上作简单修正，而不需要调用所有支持向量重新计算b 。最小优化后的α₁^*如果不在边界上，b的计算公式为：

b₁=E₁+y₁(α₁^*－α₁⁰)K(x₁,x₁)+y₂(α₂^*－α₂⁰)K(x₁,x₂)+b₀

最小优化后的α₂^*如果不在边界上，b的计算公式为：

b₂=E₂+y₁(α₁^*－α₁⁰)K(x₁,x₂)+y₂(α₂^*－α₂⁰)K(x₂,x₂)+b₀

α₁^*，α₂^*都不在边界上时，b₁和b₂是相等的。两个Lagrange乘子都在边界上时，b₁和b₂以及它们之间的数都可作为符合KKT条件的阈值。这时SMO算法选择最安全的b₁ ，b₂之中点作为阈值。

非线性的情况，误差的计算要用到所有已找到的支持向量及它们的Lagrange乘子：

线性的情况则是先重置分类超平面的法向量w，再根据u_j=w’x_j-b计算输出u_j和误差E_j=u_j－y_j 。同阈值的重置一样，法向量的重置也不需要调用所有的支持向量，只需在原来的法向量基础上作改动：

w^*=w+y₁(α₁^*－α₁)x₁+y₂(α₂^*－α₂)x₂

大部分重置工作都是以简单的非循环计算来完成的，这使得需要做很多次最小优化的SMO算法不必在每次优化后的重置中花费太多时间。但是我们也看到，非线性的情况误差的重置必须与所有支持向量逐个计算核函数，而且核函数的计算本身就比点积复杂，于是非线性的情况误差的重置将成为算法速度的瓶颈。

四、算法的流程图

五、Platt大神的逻辑代码

六、源代码的实现

未完，待续……