SVM——（七）SMO（序列最小最优算法）
在说SMO (Sequential minimal optimization)之前，先介绍一种与之类似的算法，坐标上升（下降）算法.1.Coordinate ascent
所谓坐标上升（下降）指的是同一个算法，只是若实际问题是求极大值则是上升，反之为下降。我们知道梯度下降算法在每次迭代过程中都是沿着梯度的（反）方向进行的；而坐标下降算法则是在每次迭代中分步沿着你n个(n为特征维度)方向进行的。下图是2维情况下，两者求解的示意图。
具体的就是每次只把第i个变量看做是未知数，其他看做常数进行求导，令为0解出第i个变量。求出所有参数的表达式后，利用旧的参数一次更新得到每一个新的参数。也就是：梯度下降强调所有参数同时（simultaneously)更新,而坐标下降则是每个参数分别更新
下面是一个两者的一个代码片段：
% gradient descent
for i = 1:200
grad(1)=4*x1-2*x2-4;
grad(2)=-2*x1+10*x2-24;% 都是用旧的参数得到梯度
x = x-alpha*grad;% 同时更新得到新的参数
f1 = f(x(1),x(2));
end
% coordinate descent
for i = 200
x1=1+0.5*x2;
x2=2.4+0.2*x1;% 用上一步更新的参数，来更新另外一个参数，未同时
f2 = f(x1,x2);
end
2.SMO算法
如下我们要之前推导出来要优化的目标函数：
max α W ( α ) = ∑ i = 1 m α i − 1 2 ∑ i , j = 1 m y ( i ) y ( j ) α i α j ⟨ x ( i ) , x ( j ) ⟩ s . t . 0 ≤ α i ≤ C , i = 1 , . . . , m ∑ i = 1 m α i y ( i ) = 0 (2.1) \begin{aligned} \max_{\alpha} &W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle\\ s.t. &0\leq\alpha_i\leq C,i=1,...,m\\ &\sum_{i=1}^m\alpha_iy^{(i)}=0\tag{2.1} \end{aligned} αmaxs.t.W(α)=i=1∑mαi−21i,j=1∑my(i)y(j)αiαj⟨x(i),x(j)⟩0≤αi≤C,i=1,...,mi=1∑mαiy(i)=0(2.1)
照着上面的想法，我们是否也能将同样的思路用在此处呢？答案是否定的，因为此处多了一个约束条件。
例如，我们将 α 1 \alpha_1 α1看做是未知量，其它视为常量，那么由约束条件我们可以得到：
α 1 y ( 1 ) = − ∑ i = 1 m α i y ( i ) ( 两边同乘以 y ( 1 ) ) α 1 = − y ( 1 ) ∑ i = 2 m α i y ( i ) (2.2) \begin{aligned} \alpha_1y^{(1)}=-\sum_{i=1}^m\alpha_iy^{(i)} \;\;(\textrm{两边同乘以}y^{(1)})\\ \alpha_1=-y^{(1)}\sum_{i=2}^m\alpha_iy^{(i)}\tag{2.2} \end{aligned} α1y(1)=−i=1∑mαiy(i)(两边同乘以y(1))α1=−y(1)i=2∑mαiy(i)(2.2)
由此我们可以看出 α 1 \alpha_1 α1不可能是一个变量，因为它是右边一串常数的和；也就是说有了 ( 2.1 ) (2.1) (2.1)这个约束条件，就不可能将其中一个 α i \alpha_i αi视为变量，其余的视为常量。
那怎么办呢？既然一个不行，那就同时将两个视为变量，其余的视为常量。不失一般性，我们任选两个，记为 α 1 , α 2 \alpha_1,\alpha_2 α1,α2。由 ( 2.1 ) (2.1) (2.1)我们同样可以得到 ( 2.2 ) (2.2) (2.2)且还有：
α 1 y ( 1 ) + α 2 y ( 2 ) = − ∑ i = 3 m α i y ( i ) = ζ (2.3) \alpha_1y^{(1)}+\alpha_2y^{(2)}=-\sum_{i=3}^m\alpha_iy^{(i)}=\zeta\tag{2.3} α1y(1)+α2y(2)=−i=3∑mαiy(i)=ζ(2.3)
此时我们再来看 ( 2.3 ) (2.3) (2.3)，虽说 α 1 y ( 1 ) + α 2 y ( 2 ) \alpha_1y^{(1)}+\alpha_2y^{(2)} α1y(1)+α2y(2)依旧等于一个常量，但是 α 1 ， α 2 \alpha_1，\alpha_2 α1，α2确是可以自由变化的（注：两者事实上只有一个事变量，因为一个确定了，另一个也就确定了）。
由 ( 2.3 ) (2.3) (2.3)我们可以画出下面这条直线：
由此我们可以得到：
[*]
[*]
[*]根据约束条件 0 ≤ α i ≤ C 0\leq\alpha_i\leq C 0≤αi≤C知，可行解位于‘盒子’ [ 0 ， C ] , [ C , 0 ] , ,中；
[*]根据约束条件 ( 2.3 ) (2.3) (2.3)知，可行解同时又位于直线 α 1 y ( 1 ) + α 2 y ( 2 ) = ζ \alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta α1y(1)+α2y(2)=ζ上；
[*]由2,3知，最优解位于盒子中的线段上；
[*]此图为 y ( 1 ) , y ( 2 ) y^{(1)},y^{(2)} y(1),y(2)异号时的情况；
[*]
假设 ( 2.1 ) (2.1) (2.1)的初始可行解为 α 1 o l d , α 2 o l d \alpha_1^{old},\alpha_2^{old} α1old,α2old，最优解为 α 1 n e w , α 2 n e w \alpha_1^{new},\alpha_2^{new} α1new,α2new，并且假设在沿着约束（直线）方向未经剪切时 α 2 \alpha_2 α2的最优解为 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc则有：
L ≤ α 2 n e w ≤ H (2.4) L\leq\alpha_2^{new}\leq H\tag{2.4} L≤α2new≤H(2.4)
且当 y ( 1 ) ≠ y ( 2 ) y^{(1)}\neq y^{(2)} y(1)=y(2)(即异号)时
L = max ( 0 , α 2 o l d − α 1 o l d ) , H = min ( C , C + α 2 o l d − α 1 o l d ) (2.5) L = \max(0,\alpha_2^{old}-\alpha_1^{old}),H=\min(C,C+\alpha_2^{old}-\alpha_1^{old})\tag{2.5} L=max(0,α2old−α1old),H=min(C,C+α2old−α1old)(2.5)
当 y ( 1 ) = y ( 2 ) y^{(1)}=y^{(2)} y(1)=y(2)时
L = max ( 0 , α 2 o l d + α 1 o l d − C ) , H = min ( C , α 2 o l d + α 1 o l d ) (2.6) L = \max(0,\alpha_2^{old}+\alpha_1^{old}-C),H=\min(C,\alpha_2^{old}+\alpha_1^{old})\tag{2.6} L=max(0,α2old+α1old−C),H=min(C,α2old+α1old)(2.6)
举例：
( α 1 o l d , α 2 o l d ) = ( 4 , 7 ) ⟹ L = max 0 , 7 + 4 − 8 ) = 3 ; ⟹ H = min ( 8 , 7 + 4 ) = 8 ; ⟹ 3 ≤ α 2 n e w ≤ 8 \begin{aligned} &(\alpha_1^{old},\alpha_2^{old})=(4,7)\\ \implies &L = \max0,7+4-8)=3;\\ \implies &H =\min(8,7+4)=8;\\ \implies &3\leq \alpha_2^{new}\leq 8 \end{aligned} ⟹⟹⟹(α1old,α2old)=(4,7)L=max0,7+4−8)=3;H=min(8,7+4)=8;3≤α2new≤8
由 ( 2.3 ) (2.3) (2.3)知：
α 1 = ( ζ − α 2 y ( 2 ) ) y ( 1 ) (2.7) \alpha_1=(\zeta-\alpha_2y^{(2)})y^{(1)}\tag{2.7} α1=(ζ−α2y(2))y(1)(2.7)
因此,
W ( α ) = W ( α 1 , α 2 , . . . , α m ) = W ( ( ζ − α 2 y ( 2 ) ) y ( 1 ) , α 2 , . . . α m ) (2.8) W(\alpha)=W(\alpha_1,\alpha_2,...,\alpha_m)=W((\zeta-\alpha_2y^{(2)})y^{(1)},\alpha_2,...\alpha_m)\tag{2.8} W(α)=W(α1,α2,...,αm)=W((ζ−α2y(2))y(1),α2,...αm)(2.8)
由于我们是将 α 3 , . . . α m \alpha_3,...\alpha_m α3,...αm视为常数的，所以此时 W ( α ) W(\alpha) W(α)实质上是一个仅关于 α 2 \alpha_2 α2的二次函数 W ( α 2 ) W(\alpha_2) W(α2)。为什么是二次？由 ( 2.1 ) (2.1) (2.1)可知，其最高次数仅为2。所以 W ( α 2 ) W(\alpha_2) W(α2)又可以表示成 a ( α 2 ) 2 + b α 2 + c a(\alpha_2)^2+b\alpha_2+c a(α2)2+bα2+c的形式。如果我们暂时先忽略条件 ( 2.4 ) (2.4) (2.4)，然后令其导数为0，则很容易求得 α 2 \alpha_2 α2未剪切的解 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc。
且剪切后的解为：
α 2 n e w { H , i f α 2 n e w , u n c > H α 2 n e w , u n c , i f L ≤ α 2 n e w , u n c ≤ H L , i f α 2 n e w , u n c < L \begin{aligned} \alpha_2^{new}\begin{cases}H,\;&if\;\alpha_2^{new,unc}>H\\ \alpha_2^{new,unc},\; &if\;L\leq\alpha_2^{new,unc}\leq H\\ L,\;&if\;\alpha_2^{new,unc}<L \end{cases} \end{aligned} α2new⎩⎪⎪⎨⎪⎪⎧H,α2new,unc,L,ifα2new,unc>HifL≤α2new,unc≤Hifα2new,unc<L
最后，在计算得到 α 2 n e w \alpha_2^{new} α2new之后，就可以利用公式 ( 2.3 ) (2.3) (2.3)求得 α 1 n e w \alpha_1^{new} α1new
以上都是根据cs229-notes3.pdf整理的笔记，琢磨了很久还是没有彻底将SMO算法弄明白，姑且先放着，等到后续实在要用到再探究，因为在SVM这章着实停留得太久了，前前后后一个月。我相信一口气是吃不成一个胖子的，循序渐进。
https://blog.51cto.com/u_15268254/4866684
页:
[1]