SMO Algorithm流程

SMO Algorithm流程

SMO Algorithm

Input: $T$ = ${(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$ ,精度 $\epsilon$
Output:近似解 $\hat{y}$
1. 取初值 $\alpha^{(0)}$ =0, k=0
2.1： 选取最优变量：对于第一个变量 $\alpha_1^{(k)}$ ，遍历所有 $0< \alpha_i <C$ 的值，也就是 $y_{i}*g(x_{i})=1$ 的值，也就是支持向量，检验是否满足KKT条件，也就是,是否满足一下三个条件：
$\sum_{i=1}^{N}\alpha_iy_i=0$
$o\le\alpha_i\le C$ ,$i=1,2,...,N$
$y_{i}*g(x_{i}) \ge1,for$ $\{$ $x_i|$ $\alpha_i=0$ $\}$
$y_{i}*g(x_{i})=1,for$ $\{$ $x_i|$ $0\lt\alpha_i \lt C$ $\}$
$y_{i}*g(x_{i}) \le1,for$ $\{$ $x_i|$ $\alpha_i=C$ $\}$
其中 $g(x_i)=\sum_{j=1}^N \alpha_j y_j K(x_j,x_i)+b$
若不满足，则选取该点，若支持向量全部满足，则遍历其他非支持向量，直到找到不满足该KKT条件为之
对于第一个变量 $\alpha_2^{(k)}$ ，则采用以下策略：
若对于第一个变量$\alpha_1^{(k)}$ 对应的$E_1\gt0$ ,则选取使得 $E_2$ 最小的点 ，
若对于第一个变量$\alpha_1^{(k)}$ 对应的$E_1\lt0$ ,则选取使得 $E_2$ 最大的点 ，
其目的，使得 $\alpha_2^{new}$ 依赖于 $E_1 - E_2$ , 则去使得$E_1 - E_2$最大（加快计算）的点

其中 $E_i=g(x_i)-y_i=\{\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b \}-y_i$
2.2 二次规划求解： 对于选取的第一个变量
其中，原始为剪辑的值为，


剪辑之后得到第一个变量的解：

于此同时，由 $\alpha_1^{old}*y_1 + \alpha_2^{old}*y_2 = \varepsilon = \alpha_1^{new}*y_1 + \alpha_2^{new,clipped}*y_2$
可得到第二个变量的解：
$\alpha_1^{new}= \alpha_1^{old}+y_1*y_2(\alpha_2^{old}-\alpha_2^{new,clipped})$
基于以上的算法，可以得到最优解 $\alpha_1^{(k+1)}$ $\alpha_2^{(k+1)}$
3. 若在精度范围内所有点都满足KKT条件，则跳转（3），否则转（2）
4. 取 $\hat{\alpha} = \alpha^{(k+1)}$