序列最小优化算法

序列最小优化(Sequential Minimal Optimization)

在支持向量机模型中，需要解决如下的规划问题：

$$\begin{align}\max_\alpha~~&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}\kappa(x^{(i)},x^{(j)})\\ \text{s.t.}~~& \begin{cases} \sum_{i=1}^{m}\alpha_iy^{(i)}=0,\\ \alpha_i\geq0,~~~~~~~~~~~~~i=1,2,\dots ,m \end{cases} \end{align}$$

当训练样本很庞大、维度高时，求解是很难的。序列最小优化算法可以解决如上的规划问题。

SMO算法是一种启发式算法，基本思路是：如果所有变量的解都满足于此优化问题的KKT条件，那么这个最优化问题的解就找到了。

在支持向量机的那篇博客中，已经提到了SMO的大致做法

先选取一对要更新的变量 $\alpha_i$ 和 $\alpha_j$；再固定除了$\alpha_i$ 和 $\alpha_j$ 之外的其他参数求解上面的式子获得更新后的 $\alpha_i$ 和 $\alpha_j$。

上面选取的 $\alpha_i$ 和 $\alpha_j$ 中有一个不满足KKT条件，目标函数值就会在迭代后减小。于是我们就可以将 $\alpha_i$ 选取为最不满足KKT条件的变量，$\alpha_j$ 选取为能使目标函数更改最大的变量，这样就可以最快的最优化目标函数值。但是这样又很麻烦，所以SMO采用的是：选取的 $\alpha_i$ 和 $\alpha_j$ 所对应的样本点间隔最大，那么这样就可以对目标函数进行最大的变化。

解出 $\alpha$ 后，就可以将 $\alpha$ 代入，求解出模型：

$$f(x^{(i)}) = \omega^Tx+b=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)^T}x+b$$

其实，根据 $\sum_{i=1}^{m}\alpha_iy^{(i)}=0$，随着 $\alpha_i$ 的确定，$\alpha_j$ 也会随之而确定。

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

假设选择的两个变量是 $\alpha_1,\alpha_2$，其余变量 $\alpha_i(i = 3,4,\dots,m)$ 均是固定常数，那么可以将原规划问题写成：

$$\begin{align} \min_{\alpha_1,\alpha_2}~~&\frac{1}{2} \alpha_1^2 \kappa(x^{(1)},x^{(1)})+\frac{1}{2} \alpha_2^2 \kappa(x^{(2)},x^{(2)})+\alpha_1\alpha_2y^{(1)}y^{(2)}\kappa(x^{(1)},x^{(2)}) \\ & +\alpha_1y^{(1)}\sum_{i=3}^m\alpha_iy^{(i)}\kappa(x^{(1)},x^{(i)})+\alpha_2y^{(2)}\sum_{i=3}^m\alpha_iy^{(i)}\kappa(x^{(2)},x^{(i)})\\ & +\sum_{i=3}^{m}\sum_{j=3}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}\kappa(x^{(i)},x^{(j)})-(\alpha_1+\alpha_2)-\sum_{i=3}^{m}\alpha_i \\ \text{s.t.}~~& \begin{cases} \alpha_1y^{(1)}+\alpha_2y^{(2)}+\sum_{i=3}^{m}\alpha_iy^{(i)}=0,\\ 0\leq\alpha_i\leq C,\qquad\qquad i=1,2 \end{cases} \end{align}$$

将 $\kappa(x^{(i)},x^{(j)})$ 记成 $\kappa_{ij}$，令

$$\sum_{i=3}^{m}\sum_{j=3}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}\kappa_{ij}-\sum_{i=3}^{m}\alpha_i=A\\ -\sum_{i=3}^{m}\alpha_iy^{(i)}=\varsigma$$

原规划问题可记作：

$$\begin{align} \min_{\alpha_1,\alpha_2}~~&\frac{1}{2} \alpha_1^2 \kappa_{11}+\frac{1}{2} \alpha_2^2 \kappa_{22}+\alpha_1\alpha_2y^{(1)}y^{(2)}\kappa_{12} \\ & +\alpha_1y^{(1)}\sum_{i=3}^m\alpha_iy^{(i)}\kappa_{1i}+\alpha_2y^{(2)}\sum_{i=3}^m\alpha_iy^{(i)}\kappa_{2i}\\ & -(\alpha_1+\alpha_2)+A \\ \text{s.t.}~~& \begin{cases} \alpha_1y^{(1)}+\alpha_2y^{(2)}=\varsigma,\\ 0\leq\alpha_i\leq C,\qquad\qquad i=1,2 \end{cases} \end{align}$$

由于这个问题是一个二元问题，目标函数还是一个凸函数，那么可以用画图来表示他的定义域。

由于问题的第一个约束 $\alpha_1y^{(1)}+\alpha_2y^{(2)}=\varsigma$，$(\alpha_1,\alpha_2)$ 只能在红色的虚线上；由于问题的第二个约束，$(\alpha_1,\alpha_2)$ 只能在 $[0,C]\times[0,C]$ 的空间中。那么我们可以将这个约束问题的自变量设定为 $\alpha_2$。

令上述问题的初始可行解为 $\alpha_1^\text{old},\alpha_2^\text{old}$，最优解为 $\alpha_1^\text{new},\alpha_2^\text{new}$，不考虑第二个约束（未经剪辑）时 $\alpha_2$ 的最优解为 $\alpha_2^\text{new,unc}$。以 $y^{(1)}\neq y^{(2)}$ 为例（左侧），这些解的分布可能如下图：

由于 $\alpha_1^\text{old},\alpha_2^\text{old}$ 为约束的可行解，那么有 $\alpha_1^\text{old}+\alpha_2^\text{old}=k$。由于最优解 $\alpha_1^\text{new},\alpha_2^\text{new}$ 必须遵守第二个约束，那么 $\alpha_2^\text{new}$ 一定满足：

$$L\leq\alpha_2^\text{new}\leq H$$

$L,H$ 为 $\alpha_2^\text{new}$ 的上下界。以 $y^{(1)}\neq y^{(2)}$ 为例：

解根据 $k$ 的正负不同，$\alpha_2^\text{new}$ 可能分布在图中的上下两条对角线中的一个上。那么 $L,H$ 可以写成：

$$L = \max\{0,-k\},\quad H = \min\{C,C-k\}$$

又因为 $\alpha_1^\text{old}+\alpha_2^\text{old}=k$，那么可以将上下界写为：

$$L = \max\{0,\alpha_2^\text{old}-\alpha_1^\text{old}\},\quad H = \min\{C,C-\alpha^\text{old}_2+\alpha_1^\text{old}\}$$

同理，当 $y^{(1)}= y^{(2)}$ 时，则有：

$$L = \max\{0,\alpha_2^\text{old}+\alpha_1^\text{old}-C\},\quad H = \min\{C,\alpha^\text{old}_2+\alpha_1^\text{old}\}$$

下面我们先忽略第二个约束，先求解 $\alpha_2^\text{new,unc}$，再根据 $\alpha_2$ 的上下限求得最优解 $\alpha_2^\text{new}$。

记模型决策边界

$$f(x)=\sum_{i=1}^m\alpha_iy^{(i)}\kappa(x^{(i)},x)+b$$

令 $E_i(i=1,2)$ 为预测值 $f(x^{(i)})$ 与真实值 $y^{(i)}$ 之差，有：

$$E_i=f(x^{(i)})-y^{(i)}=\left( \sum_{i=1}^m\alpha_iy^{(i)}\kappa(x^{(i)},x)+b \right)-y^{(i)}\qquad i=1,2$$

引进记号 $v_i$，令：

$$\begin{align} v_i=&\sum_{j=3}^m\alpha_iy^{(j)}\kappa(x^{(i)},x^{(j)})\\ =&f(x^{(i)})-\sum_{j=2}^m\alpha_jy^{(j)}\kappa(x^{(i)},x^{(j)})-b\quad i=1,2 \end{align}$$

忽略常数项 $A$，那么规划问题的目标函数可以写成：

$$\begin{align} W (\alpha_1,\alpha_2)&= \frac{1}{2} \alpha_1^2 \kappa_{11}+\frac{1}{2} \alpha_2^2 \kappa_{22}+\alpha_1\alpha_2y^{(1)}y^{(2)}\kappa_{12} \\ & +\alpha_1y^{(1)}v_1+\alpha_2y^{(2)}v_2-(\alpha_1+\alpha_2) \end{align}$$

由 $\alpha_1y^{(1)}+\alpha_2y^{(2)}=\varsigma$ 与 $y^{(i)^2}=1$，可将 $\alpha_1$ 表示为：

$$\alpha_1=(\varsigma-\alpha_2y^{(2)})y^{(1)}$$

带入目标函数，有：

$$\begin{align} W (\alpha_2)&= \frac{1}{2} \kappa_{11} (\varsigma-\alpha_2y^{(2)})^2+\frac{1}{2} \alpha_2^2 \kappa_{22}+(\varsigma-\alpha_2y^{(2)})\alpha_2y^{(1)}y^{(2)}\kappa_{12} \\ & +(\varsigma-\alpha_2y^{(2)})y^{(1)}v_1+\alpha_2y^{(2)}v_2-(\varsigma-\alpha_2y^{(2)})-\alpha_2 \end{align}$$

对 $\alpha_2$ 求导：

$$\begin{align} \frac{\partial W}{\partial \alpha_2} = &\kappa_{11}\alpha_2+\kappa_{22}\alpha_2-2\kappa_{12}\alpha_2-\kappa_{11}\varsigma y^{(2)}+\kappa_{12}\varsigma y^{(2)}\\ + &y^{(1)}y^{(2)}-v_1y^{(2)}+v_2y^{(2)}-1 \end{align}$$

令导数为 $0$，得：

$$\begin{align} (\kappa_{11}+\kappa_{22}-2\kappa_{12})\alpha_2 =& y^{(2)}(y^{(2)}-y^{(1)}+\varsigma\kappa_{11}-\varsigma\kappa_{12}+v_1-v_2)\\ =& y^{(2)}\Biggr[y^{(2)}-y^{(1)}+\varsigma\kappa_{11}-\varsigma\kappa_{12}\\ +& \left(f(x^{(1)})-\sum_{j=2}^m\alpha_jy^{(j)}\kappa_{1j}-b\right)\\ -& \left(f(x^{(2)})-\sum_{j=2}^m\alpha_jy^{(j)}\kappa_{2j}-b\right)\Biggr] \end{align}$$

将 $\varsigma=\alpha_1y^{(1)}+\alpha_2y^{(2)}$ 代入得：

$$\begin{align} (\kappa_{11}+\kappa_{22}-2\kappa_{12})\alpha_2 ^\text{new,unc} =& y^{(2)}\Bigr(y^{(2)}-y^{(1)}+(\kappa_{11}+\kappa_{22}-2\kappa_{12})\alpha^\text{old}_2y^{(2)}\\ +& f(x^{(1)})-f(x^{(2)})\Bigr)\\ =& (\kappa_{11}+\kappa_{22}-2\kappa_{12})\alpha^\text{old}_2+y^{(2)}(E_1-E_2)\\ \end{align}$$

令 $\eta=\kappa{11}+\kappa{22}-2\kappa_{12}=\Vert\phi(x^{(1)})-\phi(x^{(2)})\Vert^2$，得到

$$\alpha_2 ^\text{new,unc}=\alpha^\text{old}_2+\frac{y^{(2)}(E_1-E_2)}{\eta}$$

上述的一顿操作，只是根据目标函数与第一个约束进行的未经剪辑的最优解 $\alpha_2 ^\text{new,unc}$，之后需要根据之前求得的最优解上下界，对最优解进行剪辑：

$$\alpha_2 ^\text{new}= \begin{align} \begin{cases} H,&\alpha_2 ^\text{new,unc}\ge H\\ \alpha_2 ^\text{new,unc},\quad &L\leq\alpha_2 ^\text{new,unc}\leq H\\ L,&\alpha_2 ^\text{new,unc}\leq L \end{cases} \end{align}$$

并可以求得 $\alpha_1 ^\text{new}$：

$$\alpha_1 ^\text{new}=\alpha_1 ^\text{old}+y^{(1)}y^{(2)}(\alpha_1 ^\text{old}-\alpha_1 ^\text{new})$$

变量的选择方法

SMO算法每次需要选择两个变量 $\alpha_1,\alpha_2$ 进行优化。在变量选择开始时，将所有的 $\alpha_i $ 初始化为 $0$。

第一个变量的选择

第一个变量选择被称为外层循环。外层循环中先选取训练样本中最严重违反KKT条件的样本点，并将样本点对应的 $\alpha_i$ 作为第一个变量。在SVM那篇博客中有提到对KKT条件的解释：

代入拉格朗日函数就可以得到原问题的对偶问题：

$$\begin{align} \max_\alpha~~&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)^T}x^{(j)}\\ \text{s.t.}~~& \begin{cases} \sum_{i=1}^{m}\alpha_iy^{(i)}=0\\ 0\leq\alpha\leq C~~~~~~~~~~~~~i=1,2,\dots ,m \end{cases} \end{align}$$

KKT条件要求如下：

$$\begin{cases} \alpha_i\geq 0;\quad \mu_i\geq 0;\quad\xi_i\geq 0\\ \mu_i\xi_i=0\\ \alpha_i(1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))=0\\ 1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))\leq0\\ \end{cases}$$

当 $\alpha_i=0$ 时，则$i$样本点不会对模型产生影响；当 $\alpha_i>0$ 时，$1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b)=0$，则 $i$ 样本点是支持向量：当 $\alpha<C$ 时，$\mu_i\neq0$，$\xi_i=0$，样本点落在边界上；当 $\alpha=C$ 时，$\mu_i=0$：若 $\xi_i\leq1$，则样本点被正确分类；反之，若 $\xi_i\geq1$，则样本点分类错误，损失函数就会大大增加。

如上的文字解释可以记成如下的数学语言：

$$\begin{cases} \alpha_i=0 ~\Leftrightarrow~ y^{(i)}f(x^{(i)}) \geq1\\ 0<\alpha_i<C ~\Leftrightarrow~ y^{(i)}f(x^{(i)}) = 1\\ \alpha_i=C ~\Leftrightarrow~ y^{(i)}f(x^{(i)}) \leq1 \end{cases}$$

外层循环首先要选取满足条件 $0<\alpha_i<C$ 的样本点，这些样本点就是支持向量上的点。检验他们是否满足KKT条件。如果这些样本点都满足KKT条件，则转而遍历整个训练集，检验他们是否满足KKT条件。

书上写到这里就写完了。下面是自己的理解👇

SVM的对偶算法的目的是找到一组 $\alpha$，它们不同的值对应每个样本点不同的状态，是正确分类，还是错误分类，或者是支持向量。当每个样本点的状态确定，则最优的决策边界就会出现。则问题从样本点的不同状态转移到了 $\alpha$ 上。而SMO算法则是有效率的确定 $\alpha$ 的过程，从本文的第二幅图中可以看到，不管约束的情况下，子问题的最优解落在 $[0,C]\times[0,C]$ 的空间的概率少的可怜，所以外层循环首先要选取满足条件 $0<\alpha_i<C$ 的样本点。它们是最值得优化的点。或者说，支持向量就像是线性规划中单纯形法的边界顶点，改变、迭代这些支持向量就可以尽可能的改变决策边界。

换个角度，以下的式子是没有经过对偶的拉格朗日方程：

$$\begin{align} L(\omega,b,\alpha,\xi,\mu)=&\frac{1}{2}\Vert \omega\Vert^2+C\sum_{i=1}^m\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))\\&-\sum_{i=1}^{m}\mu_i\xi_i \end{align}$$

最违反KKT的指的是最值得优化的点，格朗日函数中 $\alpha_i(1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))$ 项最大的一项，改变或者说修正它，才能最大化的最优的目标函数。

以上👆（我写的真好）。

第二个变量的选择

第二个变量的选择被称为内层循环。假设在我们在外侧循环找到了第一个变量 $\alpha_1$，那们我们要找到第二个变量 $\alpha_2$。这个变量的选择标准是希望能使 $\alpha_2$ 有足够的变化。

$$\alpha_2 ^\text{new,unc}=\alpha^\text{old}_2+\frac{y^{(2)}(E_1-E_2)}{\eta}$$

上式是 $\alpha_2$ 的迭代公式。为了能使 $\alpha_2^{\text{new}}$ 得到更大的变化，那么就要让 $|E_1-E_2|$ 的值足够大。$E_1$ 是已知的定值，当 $E_1\geq 0$ 时，那就要选择最小的 $E_i$ 作为 $E_2$； 当 $E_1\leq0$ 时，那就要选择最大的 $E_i$ 作为 $E_2$。

在特殊情况下，如果内层循环不能通过上述方式得到的 $\alpha_2$ 不能使目标函数有足够的下降，那么就需要遍历在间隔边界上的支持向量的点，将他们以次作为 $\alpha_2$ 进行尝试；如果还找不到，那么就遍历整个数据集。要是还找不到，就放弃第一个 $\alpha_1$，通过外层循环寻找其他的 $\alpha_1$。

计算 $b$ 和 $E_i$

每次完成两个变量的优化后，都需要重新计算阈值 $b$。当 $0\leq \alpha_1^{\text{new}}\leq C$ 时，由KKT条件可得：

$$\sum_{i=1}^m\alpha_iy^{(i)}\kappa(x^{(i)},x^{(1)})+b=y^{(1)}$$

于是则有：

$$b_1^{\text{new}} = y^{(1)}-\sum_{i=3}^m\alpha_iy^{(i)}\kappa_{i1}-\alpha_1y^{(1)}\kappa_{11}-\alpha_2y^{(2)}\kappa_{21}$$

$E_1$ 可写成：

$$E_1 =\sum_{i=3}^m\alpha_iy^{(i)}\kappa_{i1}+\alpha_1^{\text{old}}y^{(1)}\kappa_{11}+\alpha_2^{\text{old}}y^{(2)}\kappa_{21}+b^{\text{old}}-y^{(1)}$$

两式综合，可得 $b^{\text{new}}_1$ 的迭代公式：

$$b^{\text{new}}_1 = -E_1-y^{(1)}\kappa_{11}(\alpha^{\text{old}}_1-\alpha^{\text{new}}_1)-y^{(2)}\kappa_{21}(\alpha^{\text{old}}_2-\alpha^{\text{new}}_2)+b^{\text{old}}$$

同理，如果 $0\leq \alpha_2^{\text{new}}\leq C$ 时，有：

$$b^{\text{new}}_2 = -E_2-y^{(1)}\kappa_{12}(\alpha^{\text{old}}_1-\alpha^{\text{new}}_1)-y^{(2)}\kappa_{22}(\alpha^{\text{old}}_2-\alpha^{\text{new}}_2)+b^{\text{old}}$$

如果同时有 $0\leq \alpha_i^{\text{new}}\leq C,~~~i =1,2$ ，那么 $b^{\text{new}}_1 = b^{\text{new}}_2$；如果 $\alpha_i^{\text{new}}$ 为 $0$ 或 $C$，那么在 $b^{\text{new}}_1,b^{\text{new}}_2$ 区间中的数都符合KKT条件，这时选取他们的中点作为 $b^{\text{new}}$。

每次完成两个变量的优化后需要更新所有样本点的 $E_i$:

$$E_i=\sum_{j\in S}\alpha_jy^{(j)}\kappa(x^{(i)},x^{(j)})+b^{\text{new}}-y^{(i)}$$

其中 $S$ 为所有支持向量集合。