首先拿出最后要求解的问题：$\underset{\alpha}{min}W(\alpha)=\frac{1}{2} \sum_{i,j=1}^{n}y^{(i)}y^{(j)}\alpha_{i}\alpha_{j}k_{ij}-\sum_{i=1}^{n}\alpha_{i}$,使得满足:
(1)$0 \leq \alpha_{i}\leq C,1 \leq i \leq n$
(2)$\sum_{i=1}^{n}\alpha_{i}y^{(i)}=0$

求解的策略是每次选出两个$\alpha$进行更新。比如选取的是$\alpha_{1},\alpha_{2}$。由于$\sum_{i=1}^{n}\alpha_{i}y^{(i)}=0$，所以$\alpha_{1}y^{(1)}+\alpha_{2}y^{(2)}=-\sum_{i=3}^{n}\alpha_{i}y^{(i)}$。等号右侧是一个常数，设为$\xi$。当$y^{(1)}$和$y^{(2)}$异号时，有$\alpha_{1}-\alpha_{2}=\xi$或者$\alpha_{2}-\alpha_{1}=\xi$。同时它们还要满足$0\leq \alpha \leq C$。

我们设$\alpha_{2}$的合法区间为[L,R],那么此时有$L=max(0,\alpha_{2}-\alpha_{1}),R=min(C,C+\alpha_{2}-\alpha_{1})$。同理当$y^{(1)}$和$y^{(2)}$同号时有$L=max(0,\alpha_{2}+\alpha_{1}-C),R=min(C,\alpha_{2}+\alpha_{1})$。

首先定义$u=w^{T}x+b$

将$\alpha_{1},\alpha_{2}$带入$W(\alpha)$中得到：
$W(\alpha)=\frac{1}{2}(k_{11}\alpha_{1}^{2}+k_{22}\alpha_{2}^{2})+sk_{12}\alpha_{1}\alpha_{2}+y^{(1)}\alpha_{1}v_{1}+y^{(2)}\alpha_{2}v_{2}-\alpha_{1}-\alpha_{2}+P$

其中:
(1)$s=y^{(1)}y^{(2)}$
(2)$v_{1}=\sum_{i=3}^{n}y^{(i)}\alpha_{i}k_{1i}=u_{1}-b-y^{(1)}\alpha_{1}^{old}k_{11}-y^{(2)}\alpha_{2}^{old}k_{12}$
(3)$v_{2}=\sum_{i=3}^{n}y^{(i)}\alpha_{i}k_{2i}=u_{2}-b-y^{(1)}\alpha_{1}^{old}k_{12}-y^{(2)}\alpha_{2}^{old}k_{22}$

由于$y^{(1)}\alpha_{1}+y^{(2)}\alpha_{2}=y^{(1)}\alpha_{1}^{old}+y^{(2)}\alpha_{2}^{old}=\xi$
两边同时乘以$y^{(1)}$,得到$\alpha_{1}+s\alpha_{2}=\alpha_{1}^{old}+s\alpha_{2}^{old}=y^{(1)}\xi=T$

所以$\alpha_{1}=T-s\alpha_{2}$，将其带入$W(\alpha)$，得到$W(\alpha)=\frac{1}{2}(k_{11}(T-s\alpha_{2})^{2}+k_{22}\alpha_{2}^{2})+sk_{12}(T-s\alpha_{2})\alpha_{2}+y^{(1)}(T-s\alpha_{2})v_{1}+y^{(2)}\alpha_{2}v_{2}-(T-s\alpha_{2})-\alpha_{2}+P$

其实这是一个关于$\alpha_{2}$的二次函数，在一阶导数等于0的地方取得最小值，一阶导数为：$\frac{\partial W}{\partial \alpha_{2}}=-sk_{11}(T-s\alpha_{2})+k_{22}\alpha_{2}+sk_{12}(T-s\alpha_{2})-k_{12}\alpha_{2}-y^{(2)}v_{1}+y^{(2)}v_{2}+s-1=0$

移项得：$\alpha_{2}(k_{11}+k_{22}-2k_{12})=s(k_{11}-k_{12})T+y^{(2)}(v_{1}-v_{2})+1-s$

将$v_{1},v_{2}$带入得：$\alpha_{2}(k_{11}+k_{22}-2k_{12})=\alpha_{2}^{old}(k_{11}+k_{22}-2k_{12})+y^{(2)}(u_{1}-u_{2}+y^{(2)}-y^{(1)})$

令:
(1)$\eta =k_{11}+k_{22}-2k_{12}$
(2)$E_{1}=u_{1}-y^{(1)}$
(3)$E_{2}=u_{2}-y^{(2)}$

那么有：
$\alpha_{2}^{new}=\alpha_{2}^{old}+\frac{y^{(2)}(E_{1}-E_{2})}{\eta }$

这里就求出了新的$\alpha_{2}$。需要注意的是如果$\alpha_{2}$不在上面求出的[L,R]区间，要做一下裁剪。

由$y^{(1)}\alpha_{1}+y^{(2)}\alpha_{2}=y^{(1)}\alpha_{1}^{old}+y^{(2)}\alpha_{2}^{old}$可得：
$\alpha_{1}^{new}=\alpha_{1}^{old}+y^{(1)}y^{(2)}(\alpha_{2}^{old}-\alpha_{2}^{new})$

最后更新b
$b=\left\{\begin{matrix} b_{1} & 0<\alpha_{1}<C\\
b_{2} & 0<\alpha_{2}<C\\
\frac{1}{2}(b_{1}+b_{2}) & other
\end{matrix}\right.$

其中
$b_{1}=b-E_{1}-y^{(1)}(\alpha_{1}^{new}-\alpha_{1}^{old})k_{11}-y^{(2)}(\alpha_{2}^{new}-\alpha_{2}^{old})k_{12}$
$b_{2}=b-E_{2}-y^{(1)}(\alpha_{1}^{new}-\alpha_{1}^{old})k_{12}-y^{(2)}(\alpha_{2}^{new}-\alpha_{2}^{old})k_{22}$

这样更新b会迫使输入$x_{1}$时输出$y^{(1)}$,输入$x_{2}$时输出$y^{(2)}$

from numpy import *import operatorfrom time import sleepimport numpy as np;from svmplatt import *;import matplotlib.pyplot as plt class PlattSVM(object):        def __init__(self):                self.X = []                   self.labelMat = []                self.C = 0.0                   self.tol = 0.0                  self.b = 0.0                   self.kValue=http://www.mamicode.com/0.0"b:",svm.b)svm.scatterplot(plt)plt.show()

实验结果

SVM学习笔记5-SMO