支持向量机原理(四)SMO算法原理

曾经终败给现在 2021-11-23 23:46 324阅读 0赞

[支持向量机原理(一) 线性支持向量机][Link 1]

[支持向量机原理(二) 线性支持向量机的软间隔最大化模型][Link 2]

[支持向量机原理(三)线性不可分支持向量机与核函数][Link 3]

[支持向量机原理(四)SMO算法原理][SMO]

[支持向量机原理(五)线性支持回归][Link 4]

在SVM的前三篇里，我们优化的目标函数最终都是一个关于\$\\alpha\$向量的函数。而怎么极小化这个函数，求出对应的\$\\alpha\$向量，进而求出分离超平面我们没有讲。本篇就对优化这个关于\$\\alpha\$向量的函数的SMO算法做一个总结。

# 一、回顾SVM优化目标函数 #

我们首先回顾下我们的优化目标函数：  
\\\[ \\underbrace\{ min \}\_\{\\alpha\}  \\frac\{1\}\{2\}\\sum\\limits\_\{i=1,j=1\}^\{m\}\\alpha\_i\\alpha\_jy\_iy\_jK(x\_i,x\_j) - \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_i \\\]

\\\[ s.t. \\; \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_i = 0 \\\]

\\\[ 0 \\leq \\alpha\_i \\leq C \\\]

我们的解要满足的KKT条件的对偶互补条件为：  
\\\[ \\alpha\_\{i\}^\{\*\}(y\_i(w^Tx\_i + b) - 1 + \\xi\_i^\{\*\}) = 0 \\\]

根据这个KKT条件的对偶互补条件，我们有：  
\\\[ \\alpha\_\{i\}^\{\*\} = 0 \\Rightarrow y\_i(w^\{\*\} \\bullet \\phi(x\_i) + b) \\geq 1 \\\]

\\\[ 0 <;\\alpha\_\{i\}^\{\*\} <; C  \\Rightarrow y\_i(w^\{\*\} \\bullet \\phi(x\_i) + b) = 1 \\\]

\\\[ \\alpha\_\{i\}^\{\*\}= C \\Rightarrow y\_i(w^\{\*\} \\bullet \\phi(x\_i) + b) \\leq 1 \\\]

由于\$w^\{\*\} = \\sum\\limits\_\{j=1\}^\{m\}\\alpha\_j^\{\*\}y\_j\\phi(x\_j)\$,我们令\$g(x) = w^\{\*\} \\bullet \\phi(x) + b =\\sum\\limits\_\{j=1\}^\{m\}\\alpha\_j^\{\*\}y\_jK(x, x\_j)+ b^\{\*\}\$，则有：  
\\\[ \\alpha\_\{i\}^\{\*\} = 0 \\Rightarrow y\_ig(x\_i) \\geq 1 \\\]

\\\[ 0 <; \\alpha\_\{i\}^\{\*\} <; C  \\Rightarrow y\_ig(x\_i)  = 1 \\\]

\\\[ \\alpha\_\{i\}^\{\*\}= C \\Rightarrow y\_ig(x\_i)  \\leq 1 \\\]

# 二、SMO算法的基本思想 #

上面这个优化式子比较复杂，里面有m个变量组成的向量\$\\alpha\$需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量，将其他的变量都视为常数。由于\$\\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_i = 0\$.假如将\$\\alpha\_3, \\alpha\_4, ..., \\alpha\_m\$　固定，那么\$\\alpha\_1, \\alpha\_2\$之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。

为了后面表示方便，我们定义\$K\_\{ij\} = \\phi(x\_i) \\bullet \\phi(x\_j)\$

由于\$\\alpha\_3, \\alpha\_4, ..., \\alpha\_m\$都成了常量，所有的常量我们都从目标函数去除，这样我们上一节的目标优化函数变成下式：  
\\\[ \\;\\underbrace\{ min \}\_\{\\alpha\_1, \\alpha\_1\} \\frac\{1\}\{2\}K\_\{11\}\\alpha\_1^2 + \\frac\{1\}\{2\}K\_\{22\}\\alpha\_2^2 +y\_1y\_2K\_\{12\}\\alpha\_1 \\alpha\_2 -(\\alpha\_1 + \\alpha\_2) +y\_1\\alpha\_1\\sum\\limits\_\{i=3\}^\{m\}y\_i\\alpha\_iK\_\{i1\} + y\_2\\alpha\_2\\sum\\limits\_\{i=3\}^\{m\}y\_i\\alpha\_iK\_\{i2\} \\\]

\\\[ s.t. \\;\\;\\alpha\_1y\_1 +  \\alpha\_2y\_2 = -\\sum\\limits\_\{i=3\}^\{m\}y\_i\\alpha\_i = \\varsigma  \\\]

\\\[ 0 \\leq \\alpha\_i \\leq C \\;\\; i =1,2 \\\]

# 三、SMO算法目标函数的优化 #

为了求解上面含有这两个变量的目标优化问题，我们首先分析约束条件，所有的\$\\alpha\_1, \\alpha\_2\$都要满足约束条件，然后在约束条件下求最小。

根据上面的约束条件\$\\alpha\_1y\_1 +  \\alpha\_2y\_2  = \\varsigma\\;\\;0 \\leq \\alpha\_i \\leq C \\;\\; i =1,2\$，又由于\$y\_1,y\_2\$均只能取值1或者-1, 这样\$\\alpha\_1, \\alpha\_2\$在\[0,C\]和\[0,C\]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说\$\\alpha\_1, \\alpha\_2\$的关系直线平行于\[0,C\]和\[0,C\]形成的盒子的对角线，如下图所示：

![watermark][]

由于\$\\alpha\_1, \\alpha\_2\$的关系被限制在盒子里的一条线段上，所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是\$\\alpha\_2\$的优化问题。由于我们采用的是启发式的迭代法，假设我们上一轮迭代得到的解是\$\\alpha\_1^\{old\}, \\alpha\_2^\{old\}\$，假设沿着约束方向\$\\alpha\_2\$未经剪辑的解是\$\\alpha\_2^\{new,unc\}\$.本轮迭代完成后的解为\$\\alpha\_1^\{new\}, \\alpha\_2^\{new\}\$

由于\$\\alpha\_2^\{new\}\$必须满足上图中的线段约束。假设L和H分别是上图中\$\\alpha\_2^\{new\}\$所在的线段的边界。那么很显然我们有：  
\\\[ L \\leq \\alpha\_2^\{new\} \\leq H \\\]

而对于L和H，我们也有限制条件如果是上面左图中的情况，则  
\\\[ L = max(0, \\alpha\_2^\{old\}-\\alpha\_1^\{old\}) \\;\\;\\;H = min(C, C+\\alpha\_2^\{old\}-\\alpha\_1^\{old\}) \\\]

如果是上面右图中的情况，我们有：  
\\\[ L = max(0, \\alpha\_2^\{old\}+\\alpha\_1^\{old\}-C) \\;\\;\\; H = min(C, \\alpha\_2^\{old\}+\\alpha\_1^\{old\}) \\\]

也就是说，假如我们通过求导得到的\$\\alpha\_2^\{new,unc\}\$，则最终的\$\\alpha\_2^\{new\}\$应该为：

\\\[ \\alpha\_2^\{new\}= \\begin\{cases\} H& \{ \\alpha\_2^\{new,unc\} >; H\}\\\\ \\alpha\_2^\{new,unc\}& \{L \\leq \\alpha\_2^\{new,unc\} \\leq H\}\\\\ L& \{\\alpha\_2^\{new,unc\} <; L\} \\end\{cases\} \\\]

那么如何求出\$\\alpha\_2^\{new,unc\}\$呢？很简单，我们只需要将目标函数对\$\\alpha\_2\$求偏导数即可。

首先我们整理下我们的目标函数。

为了简化叙述，我们令  
\\\[ E\_i = g(x\_i)-y\_i = \\sum\\limits\_\{j=1\}^\{m\}\\alpha\_j^\{\*\}y\_jK(x\_i, x\_j)+ b - y\_i \\\]  
，

其中\$g(x)\$就是我们在第一节里面的提到的  
\\\[ g(x) = w^\{\*\} \\bullet \\phi(x) + b =\\sum\\limits\_\{j=1\}^\{m\}\\alpha\_j^\{\*\}y\_jK(x, x\_j)+ b^\{\*\} \\\]

我们令  
\\\[ v\_i = \\sum\\limits\_\{j=3\}^\{m\}y\_j\\alpha\_jK(x\_i,x\_j) = g(x\_i) -  \\sum\\limits\_\{j=1\}^\{2\}y\_j\\alpha\_jK(x\_i,x\_j) -b   \\\]

这样我们的优化目标函数进一步简化为：  
\\\[ W(\\alpha\_1,\\alpha\_2) = \\frac\{1\}\{2\}K\_\{11\}\\alpha\_1^2 + \\frac\{1\}\{2\}K\_\{22\}\\alpha\_2^2 +y\_1y\_2K\_\{12\}\\alpha\_1 \\alpha\_2 -(\\alpha\_1 + \\alpha\_2) +y\_1\\alpha\_1v\_1 +  y\_2\\alpha\_2v\_2 \\\]

由于\$\\alpha\_1y\_1 +  \\alpha\_2y\_2 =  \\varsigma \$，并且\$y\_i^2 = 1\$，可以得到\$\\alpha\_1用 \\alpha\_2\$表达的式子为：  
\\\[ \\alpha\_1 = y\_1(\\varsigma  - \\alpha\_2y\_2) \\\]

将上式带入我们的目标优化函数，就可以消除\$\\alpha\_1\$,得到仅仅包含\$\\alpha\_2\$的式子。  
\\\[ W(\\alpha\_2) = \\frac\{1\}\{2\}K\_\{11\}(\\varsigma  - \\alpha\_2y\_2)^2 + \\frac\{1\}\{2\}K\_\{22\}\\alpha\_2^2 +y\_2K\_\{12\}(\\varsigma - \\alpha\_2y\_2) \\alpha\_2 - (\\varsigma  - \\alpha\_2y\_2)y\_1 -  \\alpha\_2 +(\\varsigma  - \\alpha\_2y\_2)v\_1 +  y\_2\\alpha\_2v\_2 \\\]

忙了半天，我们终于可以开始求\$\\alpha\_2^\{new,unc\}\$了，现在我们开始通过求偏导数来得到\$\\alpha\_2^\{new,unc\}\$。

\\\[ \\frac\{\\partial W\}\{\\partial \\alpha\_2\} = K\_\{11\}\\alpha\_2 +  K\_\{22\}\\alpha\_2 -2K\_\{12\}\\alpha\_2 -  K\_\{11\}\\varsigma y\_2 + K\_\{12\}\\varsigma y\_2 +y\_1y\_2 -1 -v\_1y\_2 +y\_2v\_2 = 0 \\\]

整理上式有：  
\\\[ (K\_\{11\} +K\_\{22\}-2K\_\{12\})\\alpha\_2 = y\_2(y\_2-y\_1 + \\varsigma  K\_\{11\} - \\varsigma  K\_\{12\} + v\_1 - v\_2) \\\]

\\\[ = y\_2(y\_2-y\_1 + \\varsigma  K\_\{11\} - \\varsigma  K\_\{12\} + (g(x\_1) -  \\sum\\limits\_\{j=1\}^\{2\}y\_j\\alpha\_jK\_\{1j\} -b ) -(g(x\_2) -  \\sum\\limits\_\{j=1\}^\{2\}y\_j\\alpha\_jK\_\{2j\} -b)) \\\]

将$ \\varsigma  = \\alpha\_1y\_1 +  \\alpha\_2y\_2 $带入上式，我们有：

\\\[ (K\_\{11\} +K\_\{22\}-2K\_\{12\})\\alpha\_2^\{new,unc\} = y\_2((K\_\{11\} +K\_\{22\}-2K\_\{12\})\\alpha\_2^\{old\}y\_2 +y\_2-y\_1 +g(x\_1) - g(x\_2)) \\\]

\\\[ \\;\\;\\;\\; = (K\_\{11\} +K\_\{22\}-2K\_\{12\}) \\alpha\_2^\{old\} + y\_2(E\_1-E\_2) \\\]

我们终于得到了\$\\alpha\_2^\{new,unc\}\$的表达式：  
\\\[ \\alpha\_2^\{new,unc\} = \\alpha\_2^\{old\} + \\frac\{y\_2(E\_1-E\_2)\}\{K\_\{11\} +K\_\{22\}-2K\_\{12\})\} \\\]

利用上面讲到的\$\\alpha\_2^\{new,unc\}\$和\$\\alpha\_2^\{new\}\$的关系式，我们就可以得到我们新的\$\\alpha\_2^\{new\}\$了。利用\$\\alpha\_2^\{new\}\$和\$\\alpha\_1^\{new\}\$的线性关系，我们也可以得到新的\$\\alpha\_1^\{new\}\$。

# 四、SMO算法两个变量的选择 #

SMO算法需要选择合适的两个变量做迭代，其余的变量做常量来进行优化，那么怎么选择这两个变量呢？

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

SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点，要满足的KKT条件我们在第一节已经讲到了：   
\\\[ \\alpha\_\{i\}^\{\*\} = 0 \\Rightarrow y\_ig(x\_i) \\geq 1 \\\]

\\\[ 0 <; \\alpha\_\{i\}^\{\*\} <; C  \\Rightarrow y\_ig(x\_i)  =1 \\\]

\\\[ \\alpha\_\{i\}^\{\*\}= C \\Rightarrow y\_ig(x\_i)  \\leq 1 \\\]

一般来说，我们首先选择违反$0 <; \\alpha\_\{i\}^\{ *\} <; C  \\Rightarrow y\_ig(x\_i)  =1 \$这个条件的点。如果这些支持向量都满足KKT条件，再选择违反\$\\alpha\_\{i\}^\{* \} = 0 \\Rightarrow y\_ig(x\_i) \\geq 1 $ 和 \$\\alpha\_\{i\}^\{\*\}= C \\Rightarrow y\_ig(x\_i)  \\leq 1\$的点。

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

SMO算法称选择第二一个变量为内层循环，假设我们在外层循环已经找到了\$\\alpha\_1\$, 第二个变量\$\\alpha\_2\$的选择标准是让\$|E1-E2|\$有足够大的变化。由于\$\\alpha\_1\$定了的时候,\$E\_1\$也确定了，所以要想\$|E1-E2|\$最大，只需要在\$E\_1\$为正时，选择最小的\$E\_i\$作为\$E\_2\$， 在\$E\_1\$为负时，选择最大的\$E\_i\$作为\$E\_2\$，可以将所有的\$E\_i\$保存下来加快迭代。

如果内存循环找到的点不能让目标函数有足够的下降， 可以采用遍历支持向量点来做\$\\alpha\_2\$,直到目标函数有足够的下降， 如果所有的支持向量做\$\\alpha\_2\$都不能让目标函数有足够的下降，可以跳出循环，重新选择\$\\alpha\_1\$

## 4.3 计算阈值b和差值\$E\_i\$　 ##

在每次完成两个变量的优化之后，需要重新计算阈值b。当\$0 <; \\alpha\_\{1\}^\{new\} <; C\$时，我们有  
\\\[ y\_1 - \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_iK\_\{i1\} -b\_1 = 0 \\\]

于是新的\$b\_1^\{new\}\$为：  
\\\[ b\_1^\{new\} = y\_1 - \\sum\\limits\_\{i=3\}^\{m\}\\alpha\_iy\_iK\_\{i1\} - \\alpha\_\{1\}^\{new\}y\_1K\_\{11\} - \\alpha\_\{2\}^\{new\}y\_2K\_\{21\}  \\\]

计算出\$E\_1\$为：  
\\\[ E\_1 = g(x\_1) - y\_1 = \\sum\\limits\_\{i=3\}^\{m\}\\alpha\_iy\_iK\_\{i1\} + \\alpha\_\{1\}^\{old\}y\_1K\_\{11\} + \\alpha\_\{2\}^\{old\}y\_2K\_\{21\} + b^\{old\} -y\_1 \\\]

可以看到上两式都有\$y\_1 - \\sum\\limits\_\{i=3\}^\{m\}\\alpha\_iy\_iK\_\{i1\}\$，因此可以将\$b\_1^\{new\}\$用\$E\_1\$表示为：  
\\\[ b\_1^\{new\} = -E\_1 -y\_1K\_\{11\}(\\alpha\_\{1\}^\{new\} - \\alpha\_\{1\}^\{old\}) -y\_2K\_\{21\}(\\alpha\_\{2\}^\{new\} - \\alpha\_\{2\}^\{old\}) + b^\{old\} \\\]

同样的，如果\$0 <; \\alpha\_\{2\}^\{new\} <; C\$, 那么有：  
\\\[ b\_2^\{new\} = -E\_2 -y\_1K\_\{12\}(\\alpha\_\{1\}^\{new\} - \\alpha\_\{1\}^\{old\}) -y\_2K\_\{22\}(\\alpha\_\{2\}^\{new\} - \\alpha\_\{2\}^\{old\}) + b^\{old\} \\\]

最终的\$b^\{new\}\$为：  
\\\[ b^\{new\} = \\frac\{b\_1^\{new\} + b\_2^\{new\}\}\{2\} \\\]

得到了\$b^\{new\}\$我们需要更新\$E\_i\$:  
\\\[ E\_i = \\sum\\limits\_\{S\}y\_j\\alpha\_jK(x\_i,x\_j) + b^\{new\} -y\_i  \\\]

其中，S是所有支持向量\$x\_j\$的集合。

好了，SMO算法基本讲完了，我们来归纳下SMO算法。

# 五、SMO算法总结 #

输入是m个样本\$\{(x\_1,y\_1), (x\_2,y\_2), ..., (x\_m,y\_m),\}\$,其中x为n维特征向量。y为二元输出，值为1，或者-1.精度e。

输出是近似解\$\\alpha\$

1)取初值\$\\alpha^\{0\} = 0, k =0\$

2)按照4.1节的方法选择\$\\alpha\_1^k\$,接着按照4.2节的方法选择\$\\alpha\_2^k\$，求出新的\$\\alpha\_2^\{new,unc\}\$。  
\\\[ \\alpha\_2^\{new,unc\} = \\alpha\_2^\{k\} + \\frac\{y\_2(E\_1-E\_2)\}\{K\_\{11\} +K\_\{22\}-2K\_\{12\})\} \\\]

3)按照下式求出\$\\alpha\_2^\{k+1\}\$

\\\[ \\alpha\_2^\{k+1\}= \\begin\{cases\} H& \{L \\leq \\alpha\_2^\{new,unc\} >; H\}\\\\ \\alpha\_2^\{new,unc\}& \{L \\leq \\alpha\_2^\{new,unc\} \\leq H\}\\\\ L& \{\\alpha\_2^\{new,unc\} <; L\} \\end\{cases\} \\\]

4)利用\$\\alpha\_2^\{k+1\}\$和\$\\alpha\_1^\{k+1\}\$的关系求出\$\\alpha\_1^\{k+1\}\$

5)按照4.3节的方法计算\$b^\{k+1\}\$和\$E\_i\$

6）在精度e范围内检查是否满足如下的终止条件：  
\\\[ \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_i = 0 \\\]

\\\[ 0 \\leq \\alpha\_i \\leq C, i =1,2...m \\\]

\\\[ \\alpha\_\{i\}^\{k+1\} = 0 \\Rightarrow y\_ig(x\_i) \\geq 1 \\\]

\\\[ 0 <;\\alpha\_\{i\}^\{k+1\} <; C  \\Rightarrow y\_ig(x\_i)  = 1 \\\]

\\\[ \\alpha\_\{i\}^\{k+1\}= C \\Rightarrow y\_ig(x\_i)  \\leq 1 \\\]

7)如果满足则结束，返回\$\\alpha^\{k+1\}\$,否则转到步骤2）。

SMO算法终于写完了，这块在以前学的时候是非常痛苦的，不过弄明白就豁然开朗了。希望大家也是一样。写完这一篇， SVM系列就只剩下支持向量回归了，胜利在望！

（欢迎转载，转载请注明出处。欢迎沟通交流： 微信：nickchen121）

转载于:https://www.cnblogs.com/nickchen121/p/11214776.html

[Link 1]: http://www.cnblogs.com/nickchen121/p/6097604.html
[Link 2]: http://www.cnblogs.com/nickchen121/p/6100722.html
[Link 3]: http://www.cnblogs.com/nickchen121/p/6103615.html
[SMO]: http://www.cnblogs.com/nickchen121/p/6111471.html
[Link 4]: http://www.cnblogs.com/nickchen121/p/6113120.html
[watermark]: http://www.chenyoude.com/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/1580490663.png?x-oss-process=style/watermark