SMO

1. 设训练样本数目为$N$，原始观测空间的维数为$m$。支持向量机所对应的二次规划问题往往使用SMO(Sequential Minimal Optimization)算法求解。SMO算法不断地求解仅涉及两个优化变量的二次规划问题。设给定训练样本为${(\mathbf xi,y_i)}{i=1}^N$，对偶问题为： $\begin{aligned} D(\alpha)=\sum _{i=1}^N \alpha_i-\frac12 \sum _{i=1}^N \sum _{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf x_i^{\mathrm T} \mathbf x_j \\ s.t. \sum _{i=1}^N \alpha_i y_i=0, \alpha_i>0, i=1,\ldots,N \end{aligned}$。 具体地，在每次迭代时，选中两个优化变量$\alpha{i^*}$和$\alpha{j^}$，同时保持其它变量固定，求解关于$\alpha_{i^}$和$\alpha{j^*}$的二次规划问题。请结合线性支持向量机（分为线性可分和线性不可分情况），给出在每次迭代过程中关于两个变量$\alpha{i^}$和$\alpha_{j^}$的解。

SVM使用一种非线性映射，把原训练数据映射到较高的维。在新的维上，搜索最佳分离超平面，两个类的数据总可以被超平面分开。

线性可分

要找到具有“最大间隔”的划分超平面，即 $\begin{aligned} \max_{w,b}\frac 2{||w||}\\ s.t. y_i(w^\mathrm{T}x_i+b)\geq 1,i=1,2,\ldots,N. \end{aligned}$ 等价于 $\begin{aligned} \max_{w,b}\frac 12{||w||}^2 \\ s.t. y_i(w^\mathrm{T}x_i+b)\geq 1,i=1,2,\ldots,N. \end{aligned}$

线性不可分

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，为了满足函数间隔大于1的约束条件，可以对每个样本$(\mathbf x_i,y_i)$引进一个松弛变量$\xi_i≥0$，使函数间隔加上松弛变量大于等于1： $y_i(w \cdot x_i+b)\geq 1-\xi_i$ 目标函数为 $\frac 12 ||w||^2 +C\sum_{j=1}^N \xi_i$ 其中$C>0$为惩罚参数。 因此，最小化目标函数也就是使$\frac12||w||^2$尽量小，同时使误分类点的个数尽量小。线性不可分的线性支持向量机问题变成下面的凸二次规划问题： $\begin{aligned} \min_{w,b,\xi}\frac12||w||^2+C\sum_{i=1}^N\xi_i\\ s.t. y_i(w \cdot x_i +b)\geq 1-\xi_i,i=1,2,\ldots,N,\xi_i\geq0,i=1,2,\ldots,N \end{aligned}$

对偶问题

使用拉格朗日乘子法得到其“对偶问题”： $L(w,b,\alpha)=\frac 12{||w||}^2+\sum_{i=1}^N\alpha_i(1-y_i(w^\mathrm{T}x_i+b))$ 其中$\alpha=(\alpha_1;\alpha_2;\ldots;\alpha_m)$。令$L(w,b,\alpha)$中的$w$和$b$的偏导为0可得

$\begin{aligned} w=\sum_{i=1}^N\alpha_iy_ix_i,\\ 0=\sum_{i=1}^N\alpha_iy_i. \end{aligned}$ 即可将$L(w,b,\alpha)$中的$w$和$b$消去，得到对偶问题 $\begin{aligned} D(\alpha)=\sum _{i=1}^N \alpha_i-\frac12 \sum _{i=1}^N \sum _{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf x_i^{\mathrm T} \mathbf x_j \\ s.t. \sum _{i=1}^N \alpha_i y_i=0, \alpha_i>0, i=1,\ldots,N \end{aligned}$

SMO算法

约束$\sum _{i=1}^N \alpha_i y_i=0$重写为： $\begin{aligned} \alpha_{i^*}y_{i^*} +\alpha_{j^*}y_{j^*}=c,\alpha_{i^*}\geq 0,\alpha_{j^*}\geq 0\\ c=-\sum _{k \neq i^*,j^*}\alpha_k y_k \end{aligned}$ 用上式中的$c$消去$D(\alpha)$中的$\alpha _j$： $\alpha_{j^*}=(c-\alpha_{i^*}y_{i^*})y_{j^*}$ 假设$i^=1$，$j^=2$： $\alpha_2=(c-\alpha_1y_1)y_2=\gamma-s\alpha_1$ $\gamma$为常数，$s=y_1y_2$。

$\begin{aligned} K_{ij}=K(\mathbf x_i,\mathbf x_i),f(x_i)=\sum_{j=1}^N y_j\alpha_jK_{ij}+b,\\ v_i=f(x_i)-\sum_{j=1}^2y_j\alpha_jK_{ij}-b \end{aligned}$ 固定$\alpha_1$、$\alpha_2$,得到： $D(\alpha)=\alpha_1+\alpha_2-\frac 12K_{11}\alpha_1^2-\frac 12K_{22}{\alpha_2}^2-y_{1}y_{2}K_{12}\alpha_1\alpha_2-y_1\alpha_1v_1-y_2\alpha_2v_2+constant$

取$\alpha_1$为变量，则得到一个关于$\alpha_1$的单变量二次规划问题，仅有的约束是$\alpha_1\geq 0$：

$\begin{aligned} D(\alpha_1)=\alpha_1+\gamma-s\alpha_1-\frac 12K_{11}\alpha_1^2-\frac 12K_{22}(\gamma-s\alpha_1)^2-sK_{12}\alpha_1(\gamma-s\alpha_1)\\ -y_1\alpha_1v_1-y_2(\gamma-s\alpha_1)v_2+constant \end{aligned}$

对$\alpha1$求偏导以求得最大值，有 $\frac {\partial W(\alpha_1)}{\partial \alpha_1}=1-s-K_{11}\alpha_1+sK_{22}\gamma-K_{22}\alpha_1-sK_{12}\gamma+2K_{12}\alpha_1-y_1v_1+y_1v_2=0$ 由此可得： $\alpha_1^{new}=\frac{y_1(y_1-y_2+y_2\gamma(K_{22}-K_{12})+v_2-v_1)}{K_{11}+K_{22}-2K_{12}}$ 根据$v$的定义，展开$v$得到： $v_2-v_1=f(x_2)-f(x_1)-\alpha_1y_1K_{12}-y_2\alpha_2K_{22}+y_1\alpha_1K_{11}+\alpha_2 y_2K_{12}$ 规定误差项$E_i=f(x_i)-y_i$，取$\gamma=s\alpha_1^{old}+\alpha_2^{old}$，并规定$\eta=K{11}+K{22}-2K{12}$， 上式可化简为： $\alpha_1^{new}=\alpha_1^{old}+\frac{y_1(E_2-E_1)}\eta$ 再考虑限制条件$0\leq \alpha_i \leq c$，$(\alpha_1,\alpha_2)$的取值只能为直线$\alpha_1y_1+\alpha_2y_2=\gamma$落在$[0,C]\times [0,C]$矩形中的部分。

因此需要检查$\alpha_2^{new}$的值以确认这个值落在约束区间之内： $\begin{aligned} \alpha_1^{new,clipped}= \left\{ \begin{array}{ll} H, \alpha_1^{new}>H \\ \alpha_1^{new}, L\leq \alpha_1^{new} \leq H\\ L, \alpha_1^{new}< L \end{array} \right. \end{aligned}$ 其中

$\begin{cases} L=max(0,\alpha_1-\alpha_2),H=max(C,C+\alpha_1+\alpha_2) & y_1 \neq y_2 \\ L=max(0,\alpha_1+\alpha_2-C),H=max(C,\alpha_1-\alpha_2) & y_1 = y_2 \end{cases}$

假设$s=y_1y_2$，则新的$\alpha_2^{new}$为 $\alpha_2^{new}=\alpha_2^{old}+s(\alpha_1^{old}-\alpha_1^{new,clipped})$