SVM求解SMO算法理论详解

Posted by mudux on February 25, 2020

1. 介绍

  前面介绍了支持向量机SVM的理论知识。SVM的学习问题可以形式化为求解凸二次规划问题,这样的凸二次规划问题具有全局最优解,并且有许多最优化算法可以用于这一个问题的求解。当训练样本容量很大是,这些算法往往变得非常低效,如何高效的实现支持向量机学习成为一个重要的问题。本次讲述其中的序列最小最优化(sequential minimal optimization, SMO)算法,这种算法1998年由Platt提出。

2. SMO步骤

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

  其中,变量是拉格朗日乘子,一个变量$\alpha_i$对应于一个样本点$(x_i,y_i)$;变量的总数等于训练样本容量$m$。

  解满足KKT条件:

  SMO算法是一种启发式算法,其基本思想是:如果所有变量的解都满足此最优化问题的KKT条件,那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则,选择两个变量,固定其它变量,针对这两个变量构建一个二次规划问题,这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解,因为这会使得原始二次规划问题的目标函数变得更小。重要的是,这时子问题可以通过解析方法求解,这样就可以大大提高整个算法的计算速度。子问题有两个变量:一个是违反KKT条件最严重的那一个,另一个由约束条件自动确定。如此,SMO算法将原问题不断分解为子问题并对子问题求解,进而达到求解原问题的目的。
  注意,子问题的两个变量中只有一个是自由变量,假设$\alpha_1,\alpha_2$为两个变量,$\alpha_3,\alpha_4,\cdots,\alpha_m$固定,那么由(2.1)中等式约束可知:

  如果$\alpha_2$确定,那么$\alpha_1$也随之确定,所以子问题同时更新两个变量。
  整个SMO算法包括两个部分:求解两个变量二次规划的解析方法和选择变量的启发式方法。

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

  假设选择的两个变量是$\alpha_1,\alpha_2$,其它变量$\alpha_i(i=3,4,\cdots,m)$是固定的。于是SMO的最优化问题(2.1)可以写成:

  其中,$K_{i,j}=K(x_i,x_j),i,j=1,2,\cdots,m,\ \varsigma$是常数,目标函数式省略了不含$\alpha_1,\alpha_2$的常数项。
  为了求解两个变量的二次规划问题(3.1),首先分析约束条件,然后在此约束条件下求极小。
  根据上面的约束条件,且$y_1,y_2$均只能取值1或者-1,这样$\alpha_1,\alpha_2$在$\left[0,C\right]$和$\left[0,C\right]$的区域内,并且两者的关系直线的斜率只能为1或者-1,也就是说$\alpha_1,\alpha_2$的关系直线平行于$\left[0,C\right]$和$\left[0,C\right]$形成的盒子的对角线。如下图所示: 3.1

  所以两变量的优化问题实际上仅仅是一个变量的优化问题。假设最终是$\alpha_2$的优化问题。由于采用的是启发式的迭代法,假设上一轮迭代得到的解是$\alpha_1^{old}, \alpha_2^{old}$,假设沿着约束方向$\alpha_2$未经剪辑的解是$\alpha_2^{new,unc}$。本轮迭代完成后的解为$\alpha_1^{new},\alpha_2^{new}$。
  由于$\alpha_2^{new}$需要满足(3.1)中不等式约束,所以最优值$\alpha_2^{new}$的取值范围必须满足:

  其中,$L$与$H$是$\alpha_2^{new}$所在的对角线段端点的界。
  如果$y_1 \ne y_2$(见上面左图),则:

  如果$y_1=y_2$(见上面右图),则:

  下面,首先求沿着约束方向未经剪辑即未考虑(3.1)中不等式约束时$\alpha_2$的最优解$\alpha_2^{new, unc}$;然后再求剪辑后$\alpha_2$的解$\alpha_2^{new}$。记

  令

  当$i=1,2$时,$E_i$为函数$g(x)$对输入$x_i$的预测值与真实输出$y_i$之差。

  定理3.1: 最优化问题(3.1)沿着约束方向未经剪辑时的解是

  其中,

  $\Phi(x)$是输入空间到特征空间的映射,$E_i,\ i=1,2$由式(3.3)表示。
  经剪辑后$\alpha_2$的解是

  由$\alpha_2^{new}$求得$\alpha_1^{new}$是

  接下来证明定理3.1
  记

  目标函数可写成

  由$\alpha_1y_1=\varsigma -\alpha_2y_2$及$y_i^2=1$,可将$\alpha_1$表示为:

  代入式(3.9),得到只有$\alpha_2$的目标函数:

  上式对$\alpha_2$求导数:

  令其为0,得到

  将$\varsigma=\alpha_1^{old}y_1 + \alpha_2^{old}y_2$代入,得到

  将$\eta = K_{11}+K_{22}-2K_{12}$代入,于是得到

  要使其满足不等式约束必须限制在区间$\left[L,H\right]$内,从而得到$\alpha_2^{new}$的表达式(3.6)。由(3.1)中等式约束,得到$\alpha_1^{new}$的表达式(3.7)。

4. 变量的选择方法

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

4.1 第1个变量的选择

  SMO称选择第1个变量的过程称为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点,并将其对应的变量作为第1个变量。具体来说,检验样本点$(x_i,y_i)$是否满足KKT条件,即

  其中,$g(x_i)=\sum\limits_{j=1}^m \alpha_j y_j K(x_i,x_j) + b$

  该检验是在$\epsilon$范围内进行的。在检验过程中,外层循环首先遍历所有满足条件$0 \lt \alpha_i \lt C$的样本点,即在间隔边界上的支持向量点,检验它们是否满足KKT条件。如果这些样本点都满足KKT条件,那么遍历整个训练集,检验它们是否满足KKT条件。

4.2 第2个变量的选择

  SMO称选择的第二个变量的过程为内层循环。假设在外层循环中已经找到第1个变量$\alpha_1$,现在要在内层循环中找第2个变量$\alpha_2$。第2个变量选择的标准是希望能使$\alpha_2$有足够大的变化。
  由式(3.4)可知,$\alpha_2^{new}$是依赖于$|E_1-E_2|$的,为了加快计算速度,一种简单的做法是选择$\alpha_2$,使其对应的$|E_1-E_2|$最大。因为$\alpha_1$已定,$E_1$也确定了。如果$E_1$是正的,那么选择最小的$E_i$作为$E_2$;如果$E_1$是负的,那么选择最大的$E_i$作为$E_2$。为了节省时间,将所有的$E_i$值保存在一个列表中。
  在特殊情况下,如果内层循环通过以上方法选择的$\alpha_2$不能使目标函数由足够的下降,那么采用以下启发式规则继续选择$\alpha_2$。遍历在间隔边界上的支持向量点,依次将其对应的变量作为$\alpha_2$试用,直到目标函数有足够的下降。若找不到合适的$\alpha_2$,那么遍历训练数据集;若仍找不到合适的$\alpha_2$,则放弃第一个$\alpha_1$,再通过外层循环求另外的$\alpha_1$。

4.3 计算阈值$b$和差值$E_i$

  在每次完成两个变量的优化后,需要重新计算阈值$b$。当$0 \lt \alpha_1^{new} \lt C$时,由KKT条件可知:

  于是,

  由$E_1$的定义式:

  式(4.4)的前两项可以写成:

  代入式(4.4),可得:

  同样,如果$0 \lt \alpha_2^{new} \lt C$,那么:

  如果$\alpha_1^{new}, \alpha_2^{new}$同时满足条件$0 \lt \alpha_i^{new} \lt C,\ i =1,2$,那么$b_1^{new} = b_2^{new}$。如果$\alpha_1^{new},\alpha_2^{new}$是0或者$C$,那么$b_1^{new}$和$b_2^{new}$以及它们之前的数都是符合KKT条件的阈值,这时选择它们的中点作为$b^{new}$。
  在每次完成两个变量的优化之后,还必须更新对应的$E_i$值,并将它们保存在列表中,$E_i$值的更新要用到$b^{new}$值,以及所有支持向量对应的$\alpha_j$:

  其中,$S$是所有支持向量$x_j$的集合。

5. SMO算法

  算法5.1 (SMO算法)
  输入:训练数据集,其中,精度$\varepsilon$;
  输出: 近似解$\widehat \alpha$。

  1. 取初值$\alpha^{(0)}=0$, 令$k=0$;
  2. 选取优化变量$\alpha_1^{(k)}, \alpha_2^{(k)}$,解析求解两个变量的最优化问题(3.1),求解最优解$\alpha_1^{(k+1)}, \alpha_2^{(k+1)}$,更新$\alpha$为$\alpha^{(k+1)}$;
  3. 若在精度$\varepsilon$范围内满足停机条件

    其中,

    则转4;否则令$k=k+1$,转2;

  4. 取$\widehat \alpha=\alpha^{(k+1)}$.