SMO算法 公式推导

$$\begin{array}{rl}& \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i\\ & \text{ s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,i=1,2,\cdots ,N\end{array}\text{\hspace{1em}(9-69)}$$

9.4.2 SMO 算法

SMO 算法主要用来求解式(9-69)的凸二次规划问题，在该问题中，变量是拉格朗日乘子 ${\alpha }_i$，一个 ${\alpha }_i$ 对应一个样本点 $(x_i,y_i)$，所以变量总数就是样本量 $N$。SMO 算法是一种针对非线性支持向量机凸优化问题快速求解的优化算法，其基本想法是：不断地将原二次规划问题分解为只有两个变量的子二次规划问题，并对该子问题进行解析和求解，直到所有变量都满足 KKT 条件为止。

假设选择的两个变量为 ${\alpha }_1$ 和 ${\alpha }_2$，${\alpha }_3,{\alpha }_4,\cdots ,{\alpha }_N$ 固定，那么式(9-69)的子问题可以表示为：

$$\begin{array}{rl}\underset{{\alpha }_1,{\alpha }_2}{\min }& S({\alpha }_1,{\alpha }_2)=\frac{1}{2}{K}_{11}{\alpha }_1^2+\frac{1}{2}{K}_{22}{\alpha }_2^2+y_1{y}_2{K}_{12}{\alpha }_1{\alpha }_2-({\alpha }_1+{\alpha }_2)+\\ & y_1{\alpha }_1\sum _{i=3}^N{y}_i{\alpha }_i{K}_{i1}+y_2{\alpha }_2\sum _{i=3}^N{y}_i{\alpha }_i{K}_{i2}\\ \text{s.t.}& {\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{y}_i{\alpha }_i=\gamma \\ & 0\le {\alpha }_i\le C,i=1,2\end{array}\text{\hspace{1em}(9-72)}$$

其中 $K_{ij}=K(x_i,x_j)$。

式(9-72)即为两个变量的二次规划问题，先分析约束条件来考虑 ${\alpha }_2$ 的上下界问题。${\alpha }_1$ 和 ${\alpha }_2$ 都在 $[0,C]$ 范围内，由式(9-72)的第一个约束条件可知，$({\alpha }_1,{\alpha }_2)$ 在平行于 $[0,C]\times [0,C]$ 的对角线的直线上，如图 9-10 所示。

由图 9-10 可得 ${\alpha }_2$ 的上下界描述如下：当 $y_1\ne y_2$ 时，下界 $L=\max (0,{\alpha }_2-{\alpha }_1)$，上界 $H=\min (C,C+{\alpha }_2-{\alpha }_1)$；当 $y_1=y_2$ 时，下界 $L=\max (0,{\alpha }_2+{\alpha }_1-C)$，上界 $H=\min (C,{\alpha }_2+{\alpha }_1)$。

下面对 ${\alpha }_1$ 和 ${\alpha }_2$ 求解进行简单推导。假设子问题式(9-72)的初始可行解为 ${\alpha }_1^{\text{old}}$ 和 ${\alpha }_2^{\text{old}}$，最优解为 ${\alpha }_1^{\text{new}}$ 和 ${\alpha }_2^{\text{new}}$，沿着约束方向上未经截断的 ${\alpha }_2$ 的最优解为 ${\alpha }_2^{\text{new, unc}}$。一般情况下，我们尝试首先沿着约束方向求未经截断即不考虑式(9-72)的第二个约束条件的最优解 ${\alpha }_2^{\text{new, unc}}$，然后再求截断后的最优解 ${\alpha }_2^{\text{new}}$。

令：
$$g(x)=\sum _{i=1}^N{\alpha }_i{y}_{i}K(x_i,x)+b\text{\hspace{1em}(9-73)}$$

$$E_i=g(x_i)-y_i=\left(\sum _{j=1}^N{\alpha }_j{y}_{j}K(x_j,x_i)+b\right)-y_i\text{\hspace{1em}(9-74)}$$

当 $i=1,2$ 时，$E_i$ 为函数 $g(x)$ 对输入 $x_i$ 的预测值和真实值 $y_i$ 之间的误差。

关于目标函数对 ${\alpha }_2$ 求偏导并令其为 0，可求得未经截断的 ${\alpha }_2$ 的最优解为：
$${\alpha }_2^{\text{new, unc}}={\alpha }_2^{\text{old}}+\frac{y_2(E_1-E_2)}{\kappa }\text{\hspace{1em}(9-75)}$$

其中，
$$\kappa =K_{11}+K_{22}-2K_{12}=\Vert \varphi (x_1)-\varphi (x_2){\Vert }^2\text{\hspace{1em}(9-76)}$$

$\varphi (x)$ 为输入空间在特征空间中的映射。

经截断后的 ${\alpha }_2$ 可表示为：
$${\alpha }_2^{\text{new}}=\{\begin{array}{ll}H,& {\alpha }_2^{\text{new, unc}}>H\\ {\alpha }_2^{\text{new, unc}},& L\le {\alpha }_2^{\text{new, unc}}\le H\\ L,& {\alpha }_2^{\text{new, unc}}<L\end{array}\text{\hspace{1em}(9-77)}$$

接着基于 ${\alpha }_2^{\text{new}}$ 可求得 ${\alpha }_1^{\text{new}}$：
$${\alpha }_1^{\text{new}}={\alpha }_1^{\text{old}}+y_1{y}_2\left({\alpha }_2^{\text{old}}-{\alpha }_2^{\text{new}}\right)\text{\hspace{1em}(9-78)}$$

最后，每次完成两个变量的优化后，还需要重新计算参数 $b$。$b$ 的计算分为四种情况：

当 $0<{\alpha }_1^{\text{new}}<C$ 时，由：
$$\sum _{i=1}^N{\alpha }_i{y}_i{K}_{i1}+b=y_1\text{\hspace{1em}(9-79)}$$

可得：
$$b_1^{\text{new}}=y_1-\sum _{i=3}^N{\alpha }_i{y}_i{K}_{i1}-{\alpha }_1^{\text{new}}{y}_1{K}_{11}-{\alpha }_2^{\text{new}}{y}_2{K}_{21}\text{\hspace{1em}(9-80)}$$

同样，当 $0<{\alpha }_2^{\text{new}}<C$ 时，有：
$$b_2^{\text{new}}=y_2-\sum _{i=3}^N{\alpha }_i{y}_i{K}_{i1}-{\alpha }_2^{\text{new}}{y}_2{K}_{22}-{\alpha }_1^{\text{new}}{y}_1{K}_{12}\text{\hspace{1em}(9-81)}$$

当 ${\alpha }_1^{\text{new}}$ 和 ${\alpha }_2^{\text{new}}$ 同时满足 $0<{\alpha }_1^{\text{new}}<C$ 时，有：
$$b_1^{\text{new}}=b_2^{\text{new}}\text{\hspace{1em}(9-82)}$$

最后一种情况是，${\alpha }_1^{\text{new}}$ 和 ${\alpha }_2^{\text{new}}$ 都不在 $[0,C]$ 范围内，$b_1^{\text{new}}$ 和 $b_2^{\text{new}}$ 都满足 KKT 条件，直接对其取均值即可。

综上，参数 $b$ 可计算归纳为：
$$b^{\text{new}}=\{\begin{array}{ll}{b}_1^{\text{new}},& 0<{\alpha }_1^{\text{new}}<C\\ b_2^{\text{new}},& 0<{\alpha }_2^{\text{new}}<C\\ \frac{b_1^{\text{new}}+b_2^{\text{new}}}{2},& 其他\end{array}\text{\hspace{1em}(9-83)}$$

以下是本文部分公式的详细解释：
公式9-72
拉格朗日乘子上界和下界
公式9-78