SVM-SMO算法

SMO算法思想

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

为什么是变量化两个不是变量化一个?

因为要是变量化一个,剩余N-1个确定,相当于没有变量化,确定了N-1个另一个也确定了,所以需要两个

把软间隔当例子来求这个问题

$$\underset{\alpha }{\underbrace{min}}\frac{1}{2}\sum _{i=1,j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^m{\alpha }_i$$

$$s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0$$

$$0\le {\alpha }_i\le C$$

满足KKT对偶的互补条件为:

$${\alpha }_i^{\ast }(y_i(w^T{x}_i+b)-1+{\xi }_i^{\ast })=0$$

原始式子为

$$max\gamma =\frac{y(w^{T}x+b)}{||w|{|}_2}s.t{y}_i(w^T{x}_i+b)={\gamma }^{{}^{\prime }(i)}\ge {\gamma }^{{}^{\prime }}(i=1,2,...m)$$

求max所以为g(X)>=C.看KKT条件那篇文章

变形式子为

$$min\frac{1}{2}||w|{|}_2^2+C\sum _{i=1}^m{\xi }_i$$

$$s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i(i=1,2,...m)$$

$${\xi }_i\ge 0(i=1,2,...m)$$

我们有

$${\alpha }_i^{\ast }=0\Rightarrow y_i(w^{\ast }\bullet \varphi (x_i)+b)\ge 1$$

代表条件1满足,条件2不满足或者变成线性,其他点间隔大于1(这个1的来历看SVM支持向量机那篇文章)

$$0<{\alpha }_i^{\ast }<C\Rightarrow y_i(w^{\ast }\bullet \varphi (x_i)+b)=1$$

两个拉格朗日乘子的条件都成立(变等式条件),设置的乘子都>0,$s.t.y_i(w^T{x}_i+b)=1(i=1,2,...m)$,${\xi }_i=0(i=1,2,...m)$

$${\alpha }_i^{\ast }=C\Rightarrow y_i(w^{\ast }\bullet \varphi (x_i)+b)\le 1$$

相当于条件1不满足或者变成线性,条件2满足(所以为0)

由于$w^{\ast }=\sum _{j=1}^m{\alpha }_j^{\ast }{y}_j\varphi (x_j)$,我们令$g(x)=w^{\ast }\bullet \varphi (x)+b=\sum _{j=1}^m{\alpha }_j^{\ast }{y}_{j}K(x,x_j)+b^{\ast }$,则有:

$${\alpha }_i^{\ast }=0\Rightarrow y_{i}g(x_i)\ge 1$$

$$0<{\alpha }_i^{\ast }<C\Rightarrow y_{i}g(x_i)=1$$

$${\alpha }_i^{\ast }=C\Rightarrow y_{i}g(x_i)\le 1$$

为了后面表示方便，我们定义$K_{ij}=\varphi (x_i)\bullet \varphi (x_j)$

然后搞两个为变量,固定N-2

补充上条件:

$$s.t.{\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^m{y}_i{\alpha }_i=\varsigma$$

$$0\le {\alpha }_i\le Ci=1,2$$

SMO算法的优化

上图4

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

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

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

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

$L\le {\alpha }_2^{new}\le 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{array}{ll}H& {\alpha }_2^{new,unc}>H\\ {\alpha }_2^{new,unc}& L\le {\alpha }_2^{new,unc}\le H\\ L& {\alpha }_2^{new,unc}<L\end{array}$$

超过就取边界

求${\alpha }_2^{new,unc}$我们采用图三中的方法,对${\alpha }_2$求导

我们下面要对图二图三的公式详细展开

$$g(x)=w^{\ast }\bullet \varphi (x)+b=\sum _{j=1}^m{\alpha }_j^{\ast }{y}_{j}K(x,x_j)+b^{\ast }$$

我们令

$$v_i=\sum _{j=3}^m{y}_j{\alpha }_{j}K(x_i,x_j)=g(x_i)-\sum _{j=1}^2{y}_j{\alpha }_{j}K(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_1{y}_2{K}_{12}{\alpha }_1{\alpha }_2-({\alpha }_1+{\alpha }_2)+y_1{\alpha }_1{v}_1+y_2{\alpha }_2{v}_2$$

由于${\alpha }_1{y}_1+{\alpha }_2{y}_2=\varsigma$,并且$y_i^2=1$,得到

$${\alpha }_1=y_1(\varsigma -{\alpha }_2{y}_2)$$

优化了深度之眼那个式子,没有必要写成除法,加大求偏导难度

代入得:

$$W({\alpha }_2)=\frac{1}{2}{K}_{11}(\varsigma -{\alpha }_2{y}_2{)}^2+\frac{1}{2}{K}_{22}{\alpha }_2^2+y_2{K}_{12}(\varsigma -{\alpha }_2{y}_2){\alpha }_2-(\varsigma -{\alpha }_2{y}_2)y_1-{\alpha }_2+(\varsigma -{\alpha }_2{y}_2)v_1+y_2{\alpha }_2{v}_2$$

开始求${\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_1{y}_2-1-v_1{y}_2+y_2{v}_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 _{j=1}^2{y}_j{\alpha }_j{K}_{1j}-b)-(g(x_2)-\sum _{j=1}^2{y}_j{\alpha }_j{K}_{2j}-b))$$

将$\varsigma ={\alpha }_1{y}_1+{\alpha }_2{y}_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^{old}+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12})}$$

利用公式

$${\alpha }_2^{new}=\{\begin{array}{ll}H& {\alpha }_2^{new,unc}>H\\ {\alpha }_2^{new,unc}& L\le {\alpha }_2^{new,unc}\le H\\ L& {\alpha }_2^{new,unc}<L\end{array}$$

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

SMO两个变量的选择

反正不是顺序选,要挑着选

选第一个变量

SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点，要满足的KKT条件我们在第一节已经讲到了：

$${\alpha }_i^{\ast }=0\Rightarrow y_{i}g(x_i)\ge 1$$

$$0<{\alpha }_i^{\ast }<C\Rightarrow y_{i}g(x_i)=1$$

$${\alpha }_i^{\ast }=C\Rightarrow y_{i}g(x_i)\le 1$$

一般来说，我们首先选择违反$0<{\alpha }_i^{\ast }<C\Rightarrow y_{i}g(x_i)=1$个条件的点。如果这些支持向量都满足KKT条件，再选择违反${\alpha }_i^{\ast }=0\Rightarrow y_{i}g(x_i)\ge 1$和${\alpha }_i^{\ast }=C\Rightarrow y_{i}g(x_i)\le 1$的点

选第二个变量

SMO算法称选择第二个变量为内层循环

我们定义

$$E_i=g(x_i)-y_i=\sum _{j=1}^m{\alpha }_j^{\ast }{y}_{j}K(x_i,x_j)+b-y_i$$

假设我们在外层循环已经找到了α1𝛼1, 第二个变量𝛼2的选择标准是让$|E1-E2|$有足够大的变化。由于𝛼1定了的时候,𝐸1也确定了，所以要想$|E1-E2|$最大，只需要在𝐸1为正时，选择最小的𝐸𝑖作为𝐸2， 在𝐸1为负时，选择最大的𝐸𝑖作为𝐸2，可以将所有的𝐸𝑖保存下来加快迭代。

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

计算阈值b和差值$E_i$

在每次完成两个变量的优化之后，需要重新计算阈值b。当$0<{\alpha }_1^{new}<C$时，我们有

$$y_1-\sum _{i=1}^m{\alpha }_i{y}_i{K}_{i1}-b_1=0$$

于是新的$b_1^{new}$为:

$$b_1^{new}=y_1-\sum _{i=3}^m{\alpha }_i{y}_i{K}_{i1}-{\alpha }_1^{new}{y}_1{K}_{11}-{\alpha }_2^{new}{y}_2{K}_{21}$$

计算出𝐸1为：

$$E_1=g(x_1)-y_1=\sum _{i=3}^m{\alpha }_i{y}_i{K}_{i1}+{\alpha }_1^{old}{y}_1{K}_{11}+{\alpha }_2^{old}{y}_2{K}_{21}+b^{old}-y_1$$

可以看到上两式都有$y_1-\sum _{i=3}^m{\alpha }_i{y}_i{K}_{i1}$，因此可以将$b_1^{new}$用𝐸1表示为：

$$b_1^{new}=-E_1-y_1{K}_{11}({\alpha }_1^{new}-{\alpha }_1^{old})-y_2{K}_{21}({\alpha }_2^{new}-{\alpha }_2^{old})+b^{old}$$

同样的，如果$0<{\alpha }_2^{new}<C$, 那么有：

$$b_2^{new}=-E_2-y_1{K}_{12}({\alpha }_1^{new}-{\alpha }_1^{old})-y_2{K}_{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 _S{y}_j{\alpha }_{j}K(x_i,x_j)+b^{new}-y_i$$

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

SMO算法总结

输入是m个样本$(x_1,y_1),(x_2,y_2),...,(x_m,y_m),$其中x为n维特征向量。y为二元输出，值为1，或者-1.精度e。

输出是近似解α

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

2)按照选第一个变量的方法选择${\alpha }_1^k$,接着按照选第二个变量的方法选择${\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{array}{ll}H& {\alpha }_2^{new,unc}>H\\ {\alpha }_2^{new,unc}& L\le {\alpha }_2^{new,unc}\le H\\ L& {\alpha }_2^{new,unc}<L\end{array}$$

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

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

6）在精度e范围内检查是否满足如下的终止条件：

$$\sum _{i=1}^m{\alpha }_i{y}_i=0$$

$$0\le {\alpha }_i\le C,i=1,\mathrm{2...}m$$

$${\alpha }_i^{k+1}=0\Rightarrow y_{i}g(x_i)\ge 1$$

$$0<{\alpha }_i^{k+1}<C\Rightarrow y_{i}g(x_i)=1$$

$${\alpha }_i^{k+1}=C\Rightarrow y_{i}g(x_i)\le 1$$

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