背景

SVM 的学习问题可以形式化为如下凸二次规划的对偶问题：
$\min\limits_{\alpha} \;\; \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum\limits_{i=1}^{N}\alpha_i\\ s.t. \; \sum\limits_{i=1}^{N}\alpha_iy_i = 0 \\ 0 \leq \alpha_i \leq C$αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)−i=1∑N​αi​s.t.i=1∑N​αi​yi​=00≤αi​≤C
在这个问题中，变量是拉格朗日乘子，一个变量$\alpha_i$αi​ 对应一个样本点$(x_i,y_i)$(xi​,yi​)，变量总数等于训练样本总数。这个问题我们通过序列最小最优算法(SMO)来解决。

SMO算法思路：选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这两个变量分别是：（1）违反KTT条件最严重的那个。（2）另一个由约束条件确定。

SMO算法包括下面两个部分：

1. 求解两个变量二次规划的解析方法
2. 选择变量的启发式方法

两个变量二次规划的求解方法

假设选择两个变量是$\alpha_1,\alpha_2$α1​,α2​ ，其他变量$\alpha_i(i=3,4\ldots,N)$αi​(i=3,4…,N) 是固定的。固定项为常数，可以直接省略。所以SMO的最优化问题可以写成：
$\begin{aligned} \min_{\alpha_1,\alpha_2} 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_1\sum_{i=3}^Ny_i\alpha_iK_{il}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}\\ s.t. \ \ \ &\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\varsigma\\ &0\leqslant\alpha_i\leqslant C, i=1,2 \end{aligned}$α1​,α2​min​W(α1​,α2​)=s.t.   ​21​K11​α12​+21​K22​α22​+y1​y2​K12​α1​α2​+(α1​+α2​)+y1​α1​i=3∑N​yi​αi​Kil​+y2​α2​i=3∑N​yi​αi​Ki2​α1​y1​+α2​y2​=−i=3∑N​yi​αi​=ς0⩽αi​⩽C,i=1,2​
其中，$K_{ij}=K(x_i,x_j),\varsigma$Kij​=K(xi​,xj​),ς 是常数。 最优化问题有两个约束：不等式约束和等式约束。

根据约束条件$\alpha_1y_1+\alpha_2y_2=k$α1​y1​+α2​y2​=k ，$y_i$yi​ 的取值只能是1，-1。 且$0\leqslant\alpha_i\leqslant C,$0⩽αi​⩽C, 所以$(\alpha_1,\alpha_2)$(α1​,α2​) 在平行于盒子$[0,C]\times [0,C]$[0,C]×[0,C] 的对角线上。如下图所示：

因此要求的目标函数在一条平行于对角线的线段的最优值。这使得两个变量的最优化问题成为实质上的单变量优化问题（$\alpha_1 = k-\alpha_2$α1​=k−α2​）。

假设原始问题的初始可行解为$\alpha_1^{old},\alpha_2^{old}$α1old​,α2old​，本次迭代的最优解为$\alpha_1^{new},\alpha_2^{new}$α1new​,α2new​，假设沿着约束方向$\alpha_2$α2​未经剪辑(未考虑不等式约束)的解是$\alpha_2^{new,unc}$α2new,unc​ 。

由于设L、H为$\alpha_2^{new}$α2new​ 所在对角线的端点。则 $\alpha_2^{new}$α2new​ 的取值范围必须满足条件：
$L \leq \alpha_2^{new} \leq H$L≤α2new​≤H
当$y_1 \neq y_2$y1​​=y2​ 时，如上左图，则：
$L = max(0, \alpha_2^{old}-\alpha_1^{old}) \;\;\;H = min(C, C+\alpha_2^{old}-\alpha_1^{old})$L=max(0,α2old​−α1old​)H=min(C,C+α2old​−α1old​)
当$y_1 = y_2$y1​=y2​ 时，如上左图，则：
$L = max(0, \alpha_2^{old}+\alpha_1^{old}-C) \;\;\; H = min(C, \alpha_2^{old}+\alpha_1^{old})$L=max(0,α2old​+α1old​−C)H=min(C,α2old​+α1old​)
所以，最终的$\alpha_2^{new}$α2new​ 应该要满足以下情况：
$\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}$α2new​=⎩⎪⎨⎪⎧​Hα2new,unc​L​α2new,unc​>HL≤α2new,unc​≤Hα2new,unc​<L​
那么应该如何求$\alpha_2^{new,unc}$α2new,unc​ ?，通过对目标函数求导可以解决。

引入变量：
$g(x) =\sum\limits_{j=1}^{m}\alpha_j^{*}y_jK(x, x_j)+ b^{*}\\E_i = g(x_i)-y_i = \sum\limits_{j=1}^{m}\alpha_j^{*}y_jK(x_i, x_j)+ b - y_i \\ 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$g(x)=j=1∑m​αj∗​yj​K(x,xj​)+b∗Ei​=g(xi​)−yi​=j=1∑m​αj∗​yj​K(xi​,xj​)+b−yi​vi​=j=3∑m​yj​αj​K(xi​,xj​)=g(xi​)−j=1∑2​yj​αj​K(xi​,xj​)−b
注：$E_i$Ei​ 是样本的真实值与预测值的误差。

将$v_1,v_2$v1​,v2​ 带入目标函数：
$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$W(α1​,α2​)=21​K11​α12​+21​K22​α22​+y1​y2​K12​α1​α2​−(α1​+α2​)+y1​α1​v1​+y2​α2​v2​
由$\alpha_1y_1 + \alpha_2y_2 = \varsigma, \quad y_i^2=1$α1​y1​+α2​y2​=ς,yi2​=1 得：
$\alpha_1 = y_1(\varsigma - \alpha_2y_2)$α1​=y1​(ς−α2​y2​)
带入$W(\alpha_1,\alpha_2)$W(α1​,α2​) 消去$\alpha_1$α1​ ，得：
$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$W(α2​)=21​K11​(ς−α2​y2​)2+21​K22​α22​+y2​K12​(ς−α2​y2​)α2​−(ς−α2​y2​)y1​−α2​+(ς−α2​y2​)v1​+y2​α2​v2​
这样问题就变成了单变量优化问题。接下来我们通过求导来得到$\alpha_2^{new,unc}$α2new,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$∂α2​∂W​=K11​α2​+K22​α2​−2K12​α2​−K11​ςy2​+K12​ςy2​+y1​y2​−1−v1​y2​+y2​v2​=0
整理得：
$\begin{aligned} (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\left[y_2-y_1 + \varsigma K_{11} - \varsigma K_{12} + \left(g(x_1) - \sum\limits_{j=1}^{2}y_j\alpha_jK(x_1,x_j) -b\right) - \left(g(x_2) - \sum\limits_{j=1}^{2}y_j\alpha_jK(x_2,x_j) -b\right) \right] \end{aligned}$(K11​+K22​−2K12​)α2​​=y2​(y2​−y1​+ςK11​−ςK12​+v1​−v2​)=y2​[y2​−y1​+ςK11​−ςK12​+(g(x1​)−j=1∑2​yj​αj​K(x1​,xj​)−b)−(g(x2​)−j=1∑2​yj​αj​K(x2​,xj​)−b)]​
将$\alpha_1 = y_1(\varsigma - \alpha_2y_2)$α1​=y1​(ς−α2​y2​) 带入上式：
$\begin{aligned} (K_{11} +K_{22}-2K_{12})\alpha_2^{new,unc} &=y_2 [ y_2-y_1 +g(x_1)- g(x_2)+(\alpha_1y_1 + \alpha_2^{old}y_2)K_{11}-(\alpha_1y_1 + \alpha_2^{old}y_2 )K_{12}\\ &\quad-(y_1\alpha_1K_{11}+y_2\alpha_2^{old} K_{12})+(y_1\alpha_1K_{21}+y_2\alpha_2 ^{old}K_{22}) ] \\\\&= 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)\\ \end{aligned}$(K11​+K22​−2K12​)α2new,unc​​=y2​[y2​−y1​+g(x1​)−g(x2​)+(α1​y1​+α2old​y2​)K11​−(α1​y1​+α2old​y2​)K12​−(y1​α1​K11​+y2​α2old​K12​)+(y1​α1​K21​+y2​α2old​K22​)]=y2​[(K11​+K22​−2K12​)α2old​y2​+y2​−y1​+g(x1​)−g(x2​)]=(K11​+K22​−2K12​)α2old​+y2​(E1​−E2​)​
所以：
$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1-E_2)}{K_{11} +K_{22}-2K_{12})}$α2new,unc​=α2old​+K11​+K22​−2K12​)y2​(E1​−E2​)​

加上不等式约束，即剪辑后的结果为：
$\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}$α2new​=⎩⎪⎨⎪⎧​Hα2new,unc​L​α2new,unc​>HL≤α2new,unc​≤Hα2new,unc​<L​
由$\alpha_1^{old}y_1 + \alpha_2^{old}y_2 = \alpha_1^{new}y_1 + \alpha_2^{new}y_2 =\varsigma$α1old​y1​+α2old​y2​=α1new​y1​+α2new​y2​=ς，可得：
$\alpha_1^{new} = \alpha_1^{old} + y_1y_2(\alpha_2^{old} - \alpha_2^{new})$α1new​=α1old​+y1​y2​(α2old​−α2new​)

选择变量的启发式方法

SMO算法在每个子问题中选择两个变量优化，其中至少一个变量时违反KKT条件的。

第一个变量的选择

SMO称选择第一个变量的过程为外层循环，外层循环选择出不满足KKT条件的样本点。

先来回顾一下KKT条件的对偶互补条件为：
$\alpha_{i}^{*}(y_i(w^Tx_i + b) - 1 + \xi_i^{*}) = 0$αi∗​(yi​(wTxi​+b)−1+ξi∗​)=0
令$g(x) =\sum\limits_{j=1}^{m}\alpha_j^{*}y_jK(x, x_j)+ b^{*}$g(x)=j=1∑m​αj∗​yj​K(x,xj​)+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$αi∗​=0⇒yi​g(xi​)≥10<αi∗​<C⇒yi​g(xi​)=1αi∗​=C⇒yi​g(xi​)≤1
选择的顺序是：首先选择违反$0 <\alpha_{i}^{*} < C \Rightarrow y_ig(x_i) = 1$0<αi∗​<C⇒yi​g(xi​)=1 这个条件的点，即在间隔边界上的支持向量点。如果满足，再选择违反 $\alpha_{i}^{*} = 0 \Rightarrow y_ig(x_i) \geq 1，\alpha_{i}^{*}= C \Rightarrow y_ig(x_i) \leq 1$αi∗​=0⇒yi​g(xi​)≥1，αi∗​=C⇒yi​g(xi​)≤1 这个条件的点。

第二个变量的选择

在确定第一个变量$\alpha_1$α1​ 的条件下，寻找第二个变量$\alpha_2$α2​ 。由公式可知：
$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1-E_2)}{K_{11} +K_{22}-2K_{12}}$α2new,unc​=α2old​+K11​+K22​−2K12​y2​(E1​−E2​)​
可知：$\alpha_2^{new}$α2new​ 依赖于$|E_1-E_2|$∣E1​−E2​∣ 。选择$\alpha_2$α2​ 的一个标准是：使得$|E_1-E_2|$∣E1​−E2​∣ 最大。因为$\alpha_1$α1​ 已经确定，$E_1$E1​ 也确定了。所以：

（1）当$E_1>0$E1​>0 时，选择最小的$E_i$Ei​ 作为$E_2$E2​

（2）当$E_1 \leq 0$E1​≤0 时，选择最大的$E_i$Ei​ 作为$E_2$E2​

注：为了节省计算时间。通常把所有的$E_i$Ei​ 的值保存在一个列表中。

计算阈值b和差值$E_i$Ei​

每次完成两个变量的优化后，都要重新计算阈值$b$b。当$0<\alpha_1^{new}<C$0<α1new​<C 时，由KKT条件：$0 <\alpha_{i}^{*} < C \Rightarrow y_ig(x_i) = 1$0<αi∗​<C⇒yi​g(xi​)=1 可知：
$y_1 = \sum\limits_{i=1}^{N}\alpha_iy_iK_{i1} +b_1$y1​=i=1∑N​αi​yi​Ki1​+b1​
所以：
$b_1^{new} = y_1 - \sum\limits_{i=3}^{N}\alpha_iy_iK_{i1} - \alpha_{1}^{new}y_1K_{11} - \alpha_{2}^{new}y_2K_{21}$b1new​=y1​−i=3∑N​αi​yi​Ki1​−α1new​y1​K11​−α2new​y2​K21​
由$E_1$E1​ 的定义式得：
$E_1 = g(x_1) - y_1 = \sum\limits_{i=3}^{N}\alpha_iy_iK_{i1} + \alpha_{1}^{old}y_1K_{11} + \alpha_{2}^{old}y_2K_{21} + b^{old} -y_1$E1​=g(x1​)−y1​=i=3∑N​αi​yi​Ki1​+α1old​y1​K11​+α2old​y2​K21​+bold−y1​
所以：
$y_1 - \sum\limits_{i=3}^{N}\alpha_iy_iK_{i1} = \alpha_{1}^{old}y_1K_{11} + \alpha_{2}^{old}y_2K_{21} + b^{old} - E_1$y1​−i=3∑N​αi​yi​Ki1​=α1old​y1​K11​+α2old​y2​K21​+bold−E1​
带入$b_1^{new}$b1new​ 得：
$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}$b1new​=−E1​−y1​K11​(α1new​−α1old​)−y2​K21​(α2new​−α2old​)+bold
当$0<\alpha_2^{new}<C$0<α2new​<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}$b2new​=−E2​−y1​K12​(α1new​−α1old​)−y2​K22​(α2new​−α2old​)+bold
所以：
$b^{new} = \frac{b_1^{new} + b_2^{new}}{2}$bnew=2b1new​+b2new​​
更新$E_i$Ei​:
$E_i = \sum\limits_{S}y_j\alpha_jK(x_i,x_j) + b^{new} -y_i$Ei​=S∑​yj​αj​K(xi​,xj​)+bnew−yi​
其中，$S$S 是所有支持向量得集合。

SMO算法

输入是m个样本${(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),}$(x1​,y1​),(x2​,y2​),...,(xm​,ym​), 其中，$x_i \in \mathcal X = \mathbf R^n $ ，$y_i \in \mathcal Y = {-1,+1}，i=1,2\ldots,N$yi​∈Y=−1,+1，i=1,2…,N，精度$\varepsilon$ε ;

输出：近似解$\hat \alpha$α^

（1）取初值$\alpha^{(0)}=0$α(0)=0 ，令$k=0$k=0 。

（2） 选取优化变量$\alpha_1^{k},\alpha_2^{k}$α1k​,α2k​，解析求解两个变量的最优化问题，求解得最优解$\alpha_1^{(k+1)},\alpha_2^{(k+1)}$α1(k+1)​,α2(k+1)​ ，更新$\alpha$α 为$\alpha^{k+1}$αk+1 。

（3）若在精度$\varepsilon$ε 范围内满足停机条件：
$\sum\limits_{i=1}^{m}\alpha_iy_i = 0,\quad 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$i=1∑m​αi​yi​=0,0≤αi​≤C,i=1,2...mαik+1​=0⇒yi​g(xi​)≥10<αik+1​<C⇒yi​g(xi​)=1αik+1​=C⇒yi​g(xi​)≤1
其中：
$g(x) =\sum\limits_{j=1}^{N}\alpha_j^{*}y_jK(x, x_j)+ b^{*}$g(x)=j=1∑N​αj∗​yj​K(x,xj​)+b∗
则转(4)，否则令$k=k+1$k=k+1 ，转(2)；

（4）取 $\hat \alpha = \alpha^{(k+1)}$α^=α(k+1)