支持向量机1——间隔和支持向量

支持向量机2——对偶问题

支持向量机3——引入松弛因子

支持向量机4——SMO算法

支持向量机4——SMO算法

根据上一篇的对偶问题的结论，我们现在的目的是计算下式子，也就是找到一系列α$\alpha$使得(4.1)$(4.1)$公式达到最大值。

换一种表达方式那么就是让找到一系列α$\alpha$使得(4.2)$(4.2)$公式达到最小值。

那么现在问题就是如何解(4.2)$(4.2)$公式。不难发现，这是一个二次规划的问题。可使用通用的二次规化算法来求解。然而，该问题的规模正比于训练样本数，这会在实际中造成很大的开销。SMO（Sequential Minimal Optimization）可以更高效的解决上述SVM问题。

它的基本思路是先固定αi${\alpha }_i$之外的所有参数，然后求αi${\alpha }_i$上的极值，由于存在约束∑mi=1αiyi=0$\sum _{i=1}^m{\alpha }_i{y}_i=0$，若固定αi${\alpha }_i$之外的其它变量，则αi${\alpha }_i$可由其它变量导出。于是，SMO每次选择两个变量αi,αj${\alpha }_i,{\alpha }_j$，并固定其它参数。

假设选择优化的参数是 α1,α2 ${\alpha }_1,{\alpha }_2$，那么需要固定其它 m−2 $m-2$个参数。可以将(4.2)$(4.2)$式简化为只关于 α1,α2 ${\alpha }_1,{\alpha }_2$的式子。

其中Constant$Constant$代表和α1,α2${\alpha }_1,{\alpha }_2$无关的常数项。由于yi∗yi ==1 $y_i\ast y_i==1$，故上式可变为(4.4)$(4.4)$

由于约束条件∑mi=1αiyi=0αi≥0$\sum _{i=1}^m{\alpha }_i{y}_i=0{\alpha }_i\ge 0$，那么：

可见ζ$\zeta$为定值，则在等式两端同时乘以y1$y_1$，y21=1$y_1^2=1$，得到：

将(4.6)$(4.6)$带入(4.4)$(4.4)$中：

对(4.7)$(4.7)$的α2${\alpha }_2$求导，并令求导后的式子为0，以便于求得极值。令(4.7)$(4.7)$式子为ψ(α2)$\psi ({\alpha }_2)$:

1. 由上式子假设求得了α2${\alpha }_2$的值，带入(4.6)$(4.6)$即可求得α1${\alpha }_1$，分为标记为αnew1,αnew2${\alpha }_1^{new},{\alpha }_2^{new}$，优化之前的记录为αold1,αold2${\alpha }_1^{old},{\alpha }_2^{old}$。由于(4.5)$(4.5)$式，可知
   
   ζ=αold1y1+αold2y2=αnew1y1+αnew2y2(4.9)$$\begin{array}{}\text{(4.9)}& \zeta ={\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2={\alpha }_1^{new}{y}_1+{\alpha }_2^{new}{y}_2\end{array}$$
2. 由于对偶问题中已经求得ω=∑mi=1αiyixi$\omega =\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$，SVM的超平面为f(x)=ωTx+b(4.10)$\begin{array}{}\text{(4.10)}& f(x)={\omega }^{T}x+b\end{array}$，则
   
   f(x)=∑i=1mαiyixix+b(4.11)$$\begin{array}{}\text{(4.11)}& f(x)=\sum _{i=1}^m{\alpha }_i{y}_i{x}_{i}x+b\end{array}$$
   
   由于vi=∑mj=3αjyjxjxii=1,2$v_i=\sum _{j=3}^m{\alpha }_j{y}_j{x}_j{x}_{i}i=1,2$
   
   v1=f(x)−b−∑j=12αjxjyjx1(4.12)$$\begin{array}{}\text{(4.12)}& v_1=f(x)-b-\sum _{j=1}^2{\alpha }_j{x}_j{y}_j{x}_1\end{array}$$
   
   
   v2=f(x)−b−∑j=12αjxjyjx2(4.13)$$\begin{array}{}\text{(4.13)}& v_2=f(x)-b-\sum _{j=1}^2{\alpha }_j{x}_j{y}_j{x}_2\end{array}$$

将(4.9),(4.12),(4.13)$(4.9),(4.12),(4.13)$带入(4.8)$(4.8)$中

其中E表示预测值和真实值的差。Ei=f(xi)−yi,η=x21+x22−2x1x2$E_i=f(x_i)-y_i,\eta =x_1^2+x_2^2-2x_1{x}_2$

根据上篇KKT这个约束：

• 0≤α≤C$0\le \alpha \le C$
• α1y1+α2y2=ζ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\zeta$

在二维平面上表达两个约束条件：

最优解一定在方框内&&直线上取得，因此L≤αnew2≤H$L\le {\alpha }_2^{new}\le H$
当y1≠y2,L=max(0,αold2−αold1)H=min(C,C+αold2−αold1)$y_1\ne y_2,L=max(0,{\alpha }_2^{old}-{\alpha }_1^{old})H=min(C,C+{\alpha }_2^{old}-{\alpha }_1^{old})$
当y1≠y2,L=max(0,αold1+αold2−C)H=min(C,αold1+αold2)$y_1\ne y_2,L=max(0,{\alpha }_1^{old}+{\alpha }_2^{old}-C)H=min(C,{\alpha }_1^{old}+{\alpha }_2^{old})$

经过上述处理，最终α2${\alpha }_2$:

由于ζ=αold1y1+αold2y2=αnew1y1+αnew2y2$\zeta ={\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2={\alpha }_1^{new}{y}_1+{\alpha }_2^{new}{y}_2$，两边同时乘y1$y_1$得到：

αi,αj${\alpha }_i,{\alpha }_j$应该怎么选择？

(4,2)$(4,2)$式子需要满足KKT(Karush-Kuhn-Tucker)条件，即

第一个变量的选择
第一个变量的选择称为外循环，首先遍历整个样本集，选择违反KKT约束的条件作为αi${\alpha }_i$的第一个变量。只要有一个不满足KKT约束，目标函数就会在迭代后变小，直观的说，KKT违背的程度越大，则变量更新后可能导致目标函数降幅越大。于是，SMO先选取违背KKT程度最大的变量。

第二个变量的选择
第二个变量的选择过程称为内循环，假设在外循环中找到第一个变量α1${\alpha }_1$，第二个变量的选择希望能使α2${\alpha }_2$有较大的变化，在实际中找到一个α2${\alpha }_2$使得|E1−E2$E_1-E2$|最大。

确定b

在西瓜书中：
注意由于KKT条件的约束，对于任意支持向量(xs,ys)$(x_s,y_s)$都有ysf(xs)=1$y_{s}f(x_s)=1$，即：

理论上，可选取任意支持向量机并通过求解(4.16)$(4.16)$来获得b，但是现实中，用一种更加鲁棒的做法，使用所有支持向量求解的平均值：

机器学习实战：
KKT

在对每两个α$\alpha$进行优化后，要对b的值进行更新：
1. 如果0<anew1<C⇒y1(ωTx1+b)=1⇒∑mi=1αiyix1xi+b=y1$0<a_1^{new}<C\Rightarrow y_1({\omega }^T{x}_1+b)=1\Rightarrow \sum _{i=1}^m{\alpha }_i{y}_i{x}_1{x}_i+b=y_1$

由于Ei=f(xi)−yi$E_i=f(x_i)-y_i$，公式yi−∑Ni=3αiyixix1$y_i-\sum _{i=3}^N{\alpha }_i{y}_i{x}_i{x}_1$可以替换为：

可以得到

2.如果0<αnew2<C$0<{\alpha }_2^{new}<C$,则

3.如果同时满足0<αnewi<C$0<{\alpha }_i^{new}<C$,则bnew1=bnew2$b_1^{new}=b_2^{new}$
4.如果同时不满足，取两个值中点。

SMO代码，请戳

参考资料

https://blog.****.net/luoshixian099/article/details/51227754
机器学习（周志华）