SVM系列理论（十一）SMO序列最优化算法

约定不等于承诺〃 2022-05-17 09:42 327阅读 0赞

*   *   *  1. SMO 序列最小化算法的基本思想
         *  2. 选择两个变量的方法
            
             *  2.1 第一个变量的选择
             *  2.2 第二个变量的选择
         *  3. SMO序列最小化算法的基本步骤

支持向量机的的学习问题可以形式化为求解凸二次规划问题。求解凸二次规划问题可以借用一些凸二次规划求解工具，但这需要强大的计算能力支持。**Platt提出SMO序列最小优化算法，可以高效地计算出对偶问题中最佳的拉格朗日乘子** **α∗  α ∗** .

### 1. SMO 序列最小化算法的基本思想 ###

SVM的对偶问题可以表示为：

minα12∑Nj=1αiαjyiyjK(xi⋅xj)−∑Ni=1αi  m i n α 1 2 ∑ j = 1 N α i α j y i y j K ( x i ⋅ x j ) − ∑ i = 1 N α i

s.t.∑Ni=1αiyi=0  s . t . ∑ i = 1 N α i y i = 0

0≤αi≤C,i=1,2,...,N(1)  0 ≤ α i ≤ C , i = 1 , 2 , . . . , N ( 1 )

--------------------

对应的KKT条件为：

αi=0⇒yig(xi)≥1  α i = 0 ⇒ y i g ( x i ) ≥ 1

0<αi<C⇒yig(xi)=1  0 < α i < C ⇒ y i g ( x i ) = 1

αi=C⇒yig(xi)≤1  α i = C ⇒ y i g ( x i ) ≤ 1

--------------------

SMO算法是一种快速学习的算法，**其思想是**：

不断地选择两个两个变量α1,α2  α 1 , α 2 ，将上面（1）这个二次规划问题**分解**成一个只有**两个变量**的二次规划子问题，然后对二变量子问题进行**解析求解**，直到所有变量都**满足KKT条件为止**。由于每个子问题都有解析解，计算很快，所以很高效。

*重要定理*：**KKT条件是最优化问题的充分必要条件**。

--------------------

### 2. 选择两个变量的方法 ###

上面说到SMO算法的思想，那么第一步应该明确怎么选择两个变量α1,α2  α 1 , α 2 。

#### 2.1 第一个变量的选择 ####

选择第一个变量需要选择在训练集中**违反KKT条件最严重的样本点**。 这很容易理解，因为我们最终的目标是让所有的变量α  α 满足KKT条件，选择违反KKT最大的作为优化对象。

*  一般来说，我们首先选择违反 0<αi<C⇒yig(xi)=1  0 < α i < C ⇒ y i g ( x i ) = 1 这个条件的α  α 。
 *  如果这些支持向量都满足KKT条件，再选择违反αi=C⇒yig(xi)≤1  α i = C ⇒ y i g ( x i ) ≤ 1  和 αi=0⇒yig(xi)≥1  α i = 0 ⇒ y i g ( x i ) ≥ 1 的点。

#### 2.2 第二个变量的选择 ####

为了选择第二个变量，首先定义函数g(xi)=∑Nj=1αjyjK(xj,xi)\+b  g ( x i ) = ∑ j = 1 N α j y j K ( x j , x i ) + b

并把预测值g(xi)  g ( x i )  与真实值yi  y i 之差记为Ei  E i ，则

Ei=gi(x)−yi=(∑Nj=1αjyjK(xj,xi)\+b)−yi;i=1,2  E i = g i ( x ) − y i = ( ∑ j = 1 N α j y j K ( x j , x i ) + b ) − y i ; i = 1 , 2

**第二个变量α2  α 2 的选择标准就是是让|E1−E2|  | E 1 − E 2 | 有足够大的变化。**

*  假设已经找到了α1  α 1 ,由于α1  α 1 定了,所以E1  E 1 也确定了。所以要想|E1−E2|  | E 1 − E 2 | 最大，只需要
    
     *  在E1  E 1 为正时，选择最小的Ei  E i 作为E2  E 2 ，
     *  在E1  E 1 为负时，选择最大的Ei  E i 作为E2  E 2 ，因此可以将所有的Ei  E i 保存下来加快迭代。
 *  如果上面找到的α2  α 2 **不能让目标函数有足够的下降**， 可以遍历支持向量,直到目标函数有足够的足够的下降.
 *  如果所有的支持向量做α2都不能让目标函数有足够的下降，可以跳出循环，重新选择α1

### 3. SMO序列最小化算法的基本步骤 ###

现在我们知道了选择变量的方法，那么就要把原来（1）中的凸二次优化问题转化为两个变量的二次规划子问题，然后对二变量子问题进行**解析求解**。

**第一步, 使用2中方法选取两个变量α1,α2  α 1 , α 2 (选取的量应该是违反KKT比较大的变量，这样优化效果好)**, **其他的 αi  α i  视为常量. 求解新的未经剪辑时αnew,uncut2  α 2 n e w , u n c u t** .

最优化问题可以写为：

minαW(α1,α2)=12K11α21\+12K22α22\+y1y2K12α1α2−(α1\+α2)\+y1α1∑Nj=3αiyiKi1\+y2α2∑Nj=3αiyiKi2(2)  m i n α W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 ∑ j = 3 N α i y i K i 1 + y 2 α 2 ∑ j = 3 N α i y i K i 2 ( 2 )

s.t.α1y1\+α2y2=−∑Ni=3αiyi=ξ(3)  s . t . α 1 y 1 + α 2 y 2 = − ∑ i = 3 N α i y i = ξ ( 3 )

0≤αi≤C,i=1,2(4)  0 ≤ α i ≤ C , i = 1 , 2 ( 4 )

**如果不考虑0≤αi≤C,i=1,2  0 ≤ α i ≤ C , i = 1 , 2 的约束条件下**，利用（3）代入（2），得到 **α2  α 2 的单变量问题**。

再对 W 求导并令其为 0，可以求到一个α2  α 2 解。我们称这个解是**未经剪辑时的新解**αnew,uncut2  α 2 n e w , u n c u t ：

αnew,uncut2=αold2\+y2(E1−E2)η(5)  α 2 n e w , u n c u t = α 2 o l d + y 2 ( E 1 − E 2 ) η ( 5 )

--------------------

注：

g(xi)=∑Nj=1αjyjK(xj,xi)\+b(6)  g ( x i ) = ∑ j = 1 N α j y j K ( x j , x i ) + b ( 6 )

η=K11\+K22−2K12=||ϕ(x1)−ϕ(x2)||2(7)  η = K 11 + K 22 − 2 K 12 = | | ϕ ( x 1 ) − ϕ ( x 2 ) | | 2 ( 7 )

Ei=g(xi)−yi=(∑Nj=1αjyjK(xj,xi)\+b)−yi;i=1,2(8)  E i = g ( x i ) − y i = ( ∑ j = 1 N α j y j K ( x j , x i ) + b ) − y i ; i = 1 , 2 ( 8 )

--------------------

**第二步，按照下式求出剪辑后的 αnew2  α 2 n e w ,进而由求出αnew1  α 1 n e w**

实际上，我们还必须考虑约束条件0≤αi≤C,i=1,2  0 ≤ α i ≤ C , i = 1 , 2 ，因此考虑后得到：

αnew2=⎧⎩⎨⎪⎪Hαnew,unc2LL≤αnew,unc2>HL≤αnew,unc2≤Hαnew,unc2<L(9)  α 2 n e w = \{ H L ≤ α 2 n e w , u n c > H α 2 n e w , u n c L ≤ α 2 n e w , u n c ≤ H L α 2 n e w , u n c < L ( 9 )

αnew1=αold1\+y1y2(αold2−αnew2)(10)  α 1 n e w = α 1 o l d + y 1 y 2 ( α 2 o l d − α 2 n e w ) ( 10 )

注：

具体推导参考 李航《统计学习方法》或 [戳][Link 1]

--------------------

经历了前两步，我们已经或得了新的α1,α2  α 1 , α 2 的值，那么什么时候终止呢？这需要在设定的一个精度e下检验终止条件。

**第三步，计算bnew  b n e w 和Enewi  E i n e w ，方便下次选择变量.**

在每次完成两个变量的优化之后，需要重新计算阈值bnew  b n e w 和差值Enewi  E i n e w

bnew1=−E1−y1K11(αnew1−αold1)−y2K21(αnew2−αold2)\+bold(11)  b 1 n e w = − E 1 − y 1 K 11 ( α 1 n e w − α 1 o l d ) − y 2 K 21 ( α 2 n e w − α 2 o l d ) + b o l d ( 11 )

bnew2=−E2−y1K12(αnew1−αold1)−y2K22(αnew2−αold2)\+bold(12)  b 2 n e w = − E 2 − y 1 K 12 ( α 1 n e w − α 1 o l d ) − y 2 K 22 ( α 2 n e w − α 2 o l d ) + b o l d ( 12 )

bnew=bnew1\+bnew22(13)  b n e w = b 1 n e w + b 2 n e w 2 ( 13 )

Enewi=∑SyjαjK(xi,xj)\+bnew−yi(14)  E i n e w = ∑ S y j α j K ( x i , x j ) + b n e w − y i ( 14 )

S指所有的支持向量集合。  
注：

具体推导参考 李航《统计学习方法》或 [戳][Link 1]

--------------------

**第四步，在精度e  e 范围内检查是否满足如下的终止条件,如果满足则结束，返回最佳解αnew1,αnew1 α 1n e w,α 1n e w,否则转到第二步**

∑i=1Nαiyi=0(15)  ∑ i = 1 N α i y i = 0 ( 15 )

0≤αi≤C,i=1,2...N(16)  0 ≤ α i ≤ C , i = 1 , 2... N ( 16 )

αnewi=0⇒yig(xi)≥1(17)  α i n e w = 0 ⇒ y i g ( x i ) ≥ 1 ( 17 )

0<αnewi<C⇒yig(xi)=1(18)  0 < α i n e w < C ⇒ y i g ( x i ) = 1 ( 18 )

αnewi=C⇒yig(xi)≤1(19)  α i n e w = C ⇒ y i g ( x i ) ≤ 1 ( 19 )

[Link 1]: https://www.cnblogs.com/pinard/p/6111471.html