SMO算法

引言

我们前面提过，SMO算法中的变量选择会影响目标函数的收敛速度，我们固然可以像下面这样选择变量：

但我们有更好的启发式的变量选择(working set selection)方法。

标准的变量选择法

在李航老师的《统计学习方法》中提到了如何通过二重循环来选择两个变量$x_i$和$x_j$。

第一个变量的选择

第一个循环会在所有$m$个样本（对应$m$个$\alpha_i$）中选择违反KKT条件最严重的样本点，将其对应的$\alpha_i$作为第一个变量。显然在优化完成之前，必会存在至少一个违反KKT条件的点。具体来说，就是遍历所有样本，观察其是否满足：

\[\begin{cases} \alpha_i=0\leftrightarrow y_if(x_i)\geqslant1,在边界外\\ 0<\alpha_i<C\leftrightarrow y_if(x_i)=1,在边界上，也就是支持向量\\ \alpha_i=C\leftrightarrow y_if(x_i)\leqslant1,在边界内 \end{cases}\]

其中$f(x_i)=\sum_{j=1}^m\alpha_jy_jK_{ij}+b$。由于支持向量机解的稀疏性，我们知道对解产生影响的只有支持向量，因此在选择第一个变量时，我们会用循环遍历所有满足$0<\alpha_i<C$的样本点，也就是所有支持向量点，检查是否满足上面的KKT条件。一个最坏情况是所有的支持向量点都满足KKT条件，那么我们只能遍历整个数据集来检查是否满足KKT条件。

第二个变量的选择

当我们已经找到第一个变量$x_i$之后，我们着手选择第二个变量$x_j$，我们之前提过，SMO算法的迭代公式：

\[\alpha_j^\text{new}=\alpha_j^\text{old}+\dfrac{y_2(E_i-E_j)}{\eta}\\ \Delta\alpha_j=\dfrac{y_2(E_i-E_j)}{\eta}\]

我们希望选择迭代步长更大的$\alpha_j$，也就是$\mathop{\arg\max}\limits_{j\in[1,m]}\vert\Delta\alpha_j\vert$。如果$E_j$是负数，我们希望$E_j$是最大的正数，反之亦然。如果我们找不到这样的$\alpha_j$使目标函数有足够导出下降，我们可以采用：遍历所有支持向量点$x_j$，将对应的$\alpha_j$作为第二个变量，直到目标函数有足够下降；如果还是找不到，那就回到前面，重新选择$\alpha_1$。

基于一阶近似的变量选择

在前面选择第一个变量时，我们只提到了选择“违反KKT条件最严重”的样本点，那么我们需要找到一种方法来度量违反KKT条件的严重性。由此我们引入基于一阶近似（First order approximation）的变量选择法。

我们将带有松弛变量的SVM的对偶问题改写成矩阵形式的标准优化问题：

\[\begin{aligned} \min_\alpha\quad &f(\alpha)=\dfrac{1}{2}\alpha^\top Q\alpha-e^\top\alpha\\ s.t.\quad&0\leqslant\alpha_i\leqslant C\quad i=1,\cdots,m\\ &\ y^\top\alpha=0 \end{aligned}\]

写出其拉格朗日函数：

\[\mathcal{L}(\alpha,\lambda,\mu,\eta)=f(\alpha)-\sum_{i=1}^m\lambda_i\alpha_i+\sum_{i=1}^m\mu_i(\alpha_i-C)+\eta y^\top\alpha\]

其中$\lambda$、$\mu$、$\eta$均为非负向量。如果$\alpha$是原问题的解，那么它必然是$\mathcal{L}$的有一个驻点，也就是梯度为零，整理后有：

\[\nabla f(\alpha)+\eta y=\lambda-\mu\\ \lambda_i\alpha_i=0,\mu_i(C-\alpha_i)=0,\alpha_i\geqslant0,\mu_i\geqslant0,i=1,\cdots,m\]

我们也不难求得$f(\alpha)$的梯度为$Q\alpha-e$。从而我们可以将上面的条件重写成：

\[\begin{aligned} &\nabla f(\alpha)_i+\eta y_i\geqslant 0\qquad\text{if }\alpha_i<C\\ &\nabla f(\alpha)_i+\eta y_i\leqslant 0\qquad\text{if }\alpha_i>0\\ \end{aligned}\]

我们定义关于$\alpha$的两个集合$I_{\text{up}}$和$I_{\text{low}}$：

\[\begin{aligned} I_{\text{up}}(\alpha)&=\{t\vert\alpha_t<C,y_t=1\text\}\cup\{t\vert\alpha_t>0,y_t=-1\text\}\\ I_{\text{low}}(\alpha)&=\{t\vert\alpha_t<C,y_t=-1\text\}\cup\{t\vert\alpha_t>0,y_t=1\text\}\\ \end{aligned}\]

可以推出这样的性质：$I_\text{up}(\alpha)$中的所有元素$i$都满足

\[-y_i\nabla f(\alpha)_i\leqslant\eta\]

$I_\text{low}(\alpha)$中的所有元素$i$都满足

\[-y_i\nabla f(\alpha)_i\geqslant\eta\]

$\alpha$是原问题的解当且仅当

\[m(\alpha)\leqslant M(\alpha)\]

其中

\[m(\alpha)=\max_{i\in I_\text{up}(\alpha)}-y_i\nabla f(\alpha)_i, M(\alpha)=\min_{i\in I_\text{low}(\alpha)}-y_i\nabla f(\alpha)_i\]

但我们前面提到，在求得解之前，这样的等式不会被满足，因此必然会存在这样一对$(i,j)$，$i\in I_{\text{up}}(\alpha)$，$j\in I_{\text{low}}(\alpha)$但$-y_i\nabla f(\alpha)_i>-y_j\nabla f(\alpha)_j$，那么我们称这对$(i,j)$为一个违反对（violating pair）。如果最大的一个违反对是$i$和$j$，那么我们选择变量$\alpha_i$和$\alpha_j$。当然我们也可以采用启发式方法，设置一个容忍值（tolerance）$\varepsilon$，如果在第$k$轮选择变量时有

\[m(\alpha^k)-M(\alpha^k)\leqslant\varepsilon\]

就停止算法。

我们重新审视“一阶近似”这个名称，在微积分中，一阶近似指的是用一阶导数（梯度）去近似函数值：

\[f(x+d)\approx f(x)+\nabla f(x)^\top d\]

而之所以称该算法基于一阶近似，是因为最大违反对$(i,j)$是一系列子问题

\[\begin{aligned} \text{Sub}(B)\equiv\min_{d_B}&\quad\nabla f(\alpha^k)^\top_Bd_B\\ \text{subject to}&\quad y_B^\top d_B=0\\ &\quad d_t\geqslant 0,\text{if }\alpha_t^k=0,t\in B,\\ &\quad d_t\leqslant 0,\text{if }\alpha_t^k=C,t\in B,\\ &\quad-1\leqslant d_t\leqslant1,t\in B \end{aligned}\]

的最优解。这里的下标$B$指的是选定的两个变量对应的数据，比如$B={1,3}$，那么$m$维向量$\alpha$就变成$[\alpha_1,\alpha_3]$。不难发现优化目标函数的由来：

\[\begin{aligned} f(\alpha^k+d)&\approx f(\alpha^k)+\nabla f(\alpha^k)^\top d\\ &=f(\alpha^k)+\nabla f(\alpha^k)_B^\top d_B \end{aligned}\]

正是一阶近似公式中的一阶近似项。

基于二阶近似的变量选择

LIBSVM是目前最为著名的SVM软件包之一，它的working set selection是根据second order information来选择的，它在选择$i$采用的是前面提到的一阶近似方法，而在选择$j$时，不仅要求其与$i$构成违反对，还需要它能够最大程度减小目标函数。

函数的二阶近似：

\[f(x+d)=f(x)+\nabla f(x)^\top d+\dfrac12d^\top\nabla^2f(x)d\]

类似的，我们想寻找一系列优化问题

\[\begin{aligned} \text{Sub}(B)\equiv\min_{d_B}&\quad\dfrac12d_B^\top\nabla^2f(\alpha)_{BB}d_B+\nabla f(\alpha^k)^\top_Bd_B\\ \text{subject to}&\quad y_B^\top d_B=0\\ &\quad d_t\geqslant 0,\text{if }\alpha_t^k=0,t\in B,\\ &\quad d_t\leqslant 0,\text{if }\alpha_t^k=C,t\in B.\\ \end{aligned}\]

的最优解，考虑到我们已经确定了$i$，那么子问题共$m-1$个。形式化$i$和$j$的选取：

\[i\in\arg\max_{t}\{-y_t\nabla f(\alpha^k)_t\vert t\in I_\text{up}(\alpha^k)\} \\ j\in\arg\min_t\{\text{Sub}(i,t)\vert t\in I_{\text{low}}(\alpha^k),-y_t\nabla f(\alpha^k)_t<-y_i\nabla f(\alpha^k)_i\}\]

我们下面的任务就是尝试求解子问题$\text{Sub}(i,j)$

\[\begin{aligned} \text{Sub}(B)&=\dfrac12d_B^\top\nabla^2f(\alpha)_{BB}d_B+\nabla f(\alpha^k)^\top_Bd_B\\ &=\frac12\begin{bmatrix}d_i&d_j\end{bmatrix} \begin{bmatrix} \frac{\nabla f(\alpha)_i}{\nabla\alpha_i}& \frac{\nabla f(\alpha)_i}{\nabla\alpha_j}\\ \frac{\nabla f(\alpha)_j}{\nabla\alpha_i}& \frac{\nabla f(\alpha)_j}{\nabla\alpha_j}\\ \end{bmatrix}\begin{bmatrix} d_i\\d_j \end{bmatrix}+\begin{bmatrix} \nabla f(\alpha)_i&\nabla f(\alpha)_j \end{bmatrix}\begin{bmatrix} d_i\\d_j \end{bmatrix}\\ &=\frac12\begin{bmatrix}d_i&d_j\end{bmatrix} \begin{bmatrix} y_i^2K_{ii}& y_iy_jK_{ij}\\ y_jy_iK_{ji}& y_j^2K_{jj}\\ \end{bmatrix}\begin{bmatrix} d_i\\d_j \end{bmatrix}+\begin{bmatrix} \nabla f(\alpha)_i&\nabla f(\alpha)_j \end{bmatrix}\begin{bmatrix} d_i\\d_j \end{bmatrix}\\ \end{aligned}\]

这里令$\hat{d}_i=y_id_i$，$\hat{d}_j=y_jd_j$，又由$y_B^\top d_B=0$，我们得到$d_i=-d_j$，从而我们进一步化简：

\[\begin{aligned} \text{Sub}(B) &=\dfrac12(K_{ii}-2K_{ij}+K_{jj})\hat{d}_j^2+[-y_i\nabla f(\alpha)_i+y_j\nabla f(\alpha)_j]\hat{d}_j\\ &=\dfrac12a_{ij}\hat{d}^2_j+b_{ij}\hat{d}_j\\ f(\hat{d}_j)&=\dfrac12a_{ij}(\hat{d}_j+\dfrac{b_{ij}}{a_{ij}})^2-\dfrac{b_{ij}^2}{2a_{ij}} \end{aligned}\]

从而对于每个$\text{Sub}(B)$，对应的最优值为

\[-\dfrac{b^2_{ij}}{2a_{ij}}=-\dfrac{[-y_i\nabla f(\alpha)_i+y_j\nabla f(\alpha)_j]^2}{2(K_{ii}-2K_{ij}+K_{jj})}\]

从而$j$的选取可以改写成

\[j\in\arg\min_t\{-\dfrac{b_{it}^2}{a_{it}}\vert t\in I_{\text{low}}(\alpha^k),-y_t\nabla f(\alpha^k)_t<-y_i\nabla f(\alpha^k)_i\}\]

这也就是LIBSVM中的变量选取方法。

源码解读

我们来看看libSVM中进行变量选择的源代码（Version 3.25）：

两个循环，分别对应一阶近似方法和二阶近似方法。

---

• Previous
  SMO算法
• Next
  LIBSVM中的SMO算法