原文地址: https://www.csie.ntu.edu.tw/~cjlin/papers/linear_oneclass_SVM/siam.pdf.
这篇2020年的论文讨论了单类线性SVM的训练，该算法也被添加到了LIBLINEAR中。论文发表时间令人在意，因为我们前面讨论的LIBLINEAR论文都是十多年前的成果。
引入
单类SVM主要用于边缘检测任务，也就是离群点判断，我们在https://welts.xyz/2021/09/25/one_class_svm/中提及其原理与实现。在这篇文章中，还有一种异常检测方法：支持向量数据描述(Support vector data description, SVDD)，我们后面会解释。在过去的研究中，常常是对带核方法的单类SVM进行研究，但当数据的特征多到一定数量时，即使不采用核函数依然能取得不错的效果。作者考虑了当今研究的进展:
| 二分类SVM | 单分类SVM | |
|---|---|---|
| 核 | studied | studied |
| 线性 | studied | not yet |
因此，本篇文章正是讨论单类线性SVM的对偶坐标下降训练方法。
坐标下降与偏置项
我们在https://welts.xyz/2021/12/02/dcdm/中讨论过，对于决策函数
\[\text{sgn}(\pmb w^T\pmb x+b)\]偏置项$b$的存在，使得对偶问题中多出一个线性约束。比如在线性SVM的对偶问题中，如果不存在偏置项$b$，那么对偶问题是
\[\begin{aligned} \min_{\pmb\alpha}\quad&\frac12\pmb\alpha^TQ\pmb\alpha-\pmb e^T\pmb\alpha\\ \text{s.t.}\quad&0\leq\alpha_i\leq C,i=1,\cdots,l \end{aligned}\]如果偏置项存在，则上述问题会多出一个线性约束
\[\pmb y^T\pmb\alpha=0\]线性约束带来的问题就是收敛慢，这个很好理解。坐标下降也被称作分解方法(Decomposition methods)，核心思想是从整个变量集中选取子集，对该子集进行优化，使问题规模缩小形成子问题。我们称这样的子集为工作集(Working set)，设为$B$，它的大小在不同问题下效果不同:
- 没有偏置项的对偶问题中，$\vert B\vert=1$时，子问题常常会有一个闭式解；
- 有偏执项的对偶问题中，由于线性约束的存在，$\vert B\vert=1$将导致无法更新；
- 因此在有偏执项的对偶问题中，$\vert B\vert=2$是一个好选择，比如SMO算法；
- $\vert{B}\vert>2$时，子问题也需要迭代求解，导致问题难度增大。
坐标下降的问题框架:
其中问题(2.2)就是待优化子问题。坐标下降方法有两个重要组件:
- 梯度$\nabla_B f(\pmb\alpha)$的计算；
- 工作集的选择。
文章在梯度计算上的讨论还是基于LIBSVM那一套，没什么新意。至于工作集选择，他指出了两种方法，在后面会讨论：
- 随机或循环选择；
- 基于梯度信息的贪婪选择。
偏置项的用处
前面提到，偏置项的存在与否对算法可行性和收敛速度等方面都存在影响。对于核SVM，传统做法是使用偏置项，如LIBSVM那样。作者引用了一篇文章的结果(针对核SVM):
- 如果没有偏置项，原问题的坐标下降法在$\vert{B}\vert=2$的情况下会更快，相比于$\vert{B}\vert=1$；
- 在$\vert{B}\vert=2$时，无偏置项对偶问题的坐标下降法会比有偏置项的更快。
有趣的是，对于有和没有偏差项的线性SVM，CD算法之间的差异更显著。在随机或循环选择下，如果对偶问题不包含线性约束（即不考虑偏差项），CD算法的收敛速度要快得多。原因在于对于二变量的工作集
\[B=\{i,j\}\]线性约束可能会导致子问题很容易已经是最优的。一个简单的解释是，可行域变得更加更加严格。接着作者讨论了最优条件和变量选择方法，这些都是LIBSVM中老生常谈的内容，可参考https://welts.xyz/2021/07/10/wss/。
针对线性SVDD和线性单类SVM的坐标下降
对于线性单类SVM和SVDD，论文提出了新的CD设置，可以避免当线性约束在对偶问题中时的许多更新步骤的浪费。
先来看问题形式：给定$0<\nu<1$，单类SVM求解下面的原问题
\[\begin{aligned} \min_{\pmb w,\pmb\xi,\rho}\quad&\frac12\pmb w^T\pmb w-\rho+\frac1{\nu l}\sum_{i=1}^l\xi_i\\ \text{s.t.}\quad&\pmb w^T\pmb x_i>\rho-\xi_i\\ &\xi_i>0,i=1,\cdots,l \end{aligned}\tag{1}\]我们来观察下原问题，回到没有松弛变量的时候:
\[\begin{aligned} \min_{\pmb w,\rho}\quad&\frac12\pmb w^T\pmb w-\rho\\ \text{s.t.}\quad&\pmb w^T\pmb x_i>\rho\\ \end{aligned}\]进一步，将目标函数转换:
\[\begin{aligned} \min_{\pmb w,\rho}\quad&\frac12-\frac\rho{\pmb w^T\pmb w}\\ \text{s.t.}\quad&\pmb w^T\pmb x_i>\rho\\ \end{aligned}\]即
\[\begin{aligned} \max_{\pmb w,\rho}\quad&\frac\rho{\Vert\pmb{w}\Vert}\\ \text{s.t.}\quad&\pmb w^T\pmb x_i>\rho\\ \end{aligned}\tag{2}\]这里没有了标签$y$，因此约束条件希望训练样本点处于以$\pmb w$为法线的超平面的一边，处于超平面另一边的便是离群点。此外，最大化$\rho$是让这些训练样本离该超平面尽可能“远”，这一点是原二分类SVM所不具备的。值得注意的是上述问题已经没有了偏置项$b$。回到上面带松弛变量的问题(1)，其对偶问题为
\[\begin{aligned} \min_{\pmb\alpha}\quad&\frac12\pmb\alpha^TQ\pmb\alpha\\ \text{s.t.}\quad&0\leq\alpha_i\leq\frac1{\nu l},i=1,\dots,l\\ &\pmb e^T\pmb\alpha=1 \end{aligned}\tag3\]其中
\[Q_{ij}=\pmb x_i^T\pmb x_j\]也就是说，即使单类SVM在原问题中通过数据增广消除了偏置项，在对偶问题中仍存在线性约束，这是和SVC(SVM classification)以及SVR(SVM regression)任务不一样的地方。
单类SVM用超平面来区分数据是否离群，而SVDD使用一个多维球体来区分：处于这个球体之外的便是离群点。原问题如下
\[\begin{aligned} \min_{R,\pmb a,\pmb\xi}\quad& R^2+C\sum_{i=1}^l\xi_i\\ \text{s.t.}\quad&\Vert\pmb x_i-\pmb\alpha\Vert^2\leq R^2+\xi_i\\ &\xi_i\geq0,i=1,\dots,l \end{aligned}\tag4\]优化问题的目的很明确：保证所有样本点尽可能在以$\pmb\alpha$为圆心，以$R$为半径的球体内，同时最小化半径$R$。其对偶问题
\[\begin{aligned} \min_{\pmb\alpha}\quad&\pmb\alpha^TQ\pmb\alpha-\sum_{i=1}^l\alpha_iQ_{ii}\\ \text{s.t.}\quad&0\leq\alpha_i\leq C,i=1,\cdots,l\\ &\pmb e^T\pmb\alpha=1 \end{aligned}\tag5\]$Q$矩阵的定义和上面相同。可以看到这里也是存在线性约束的。上面的两种对偶问题符合下面的通式
\[\begin{aligned} \min_{\pmb\alpha}\quad&\frac12\pmb\alpha^TQ\pmb\alpha+\pmb p^T\pmb\alpha\\ \text{s.t.}\quad&0\leq\alpha_i\leq C,i=1,\cdots,l\\ &\pmb y^T\pmb\alpha=\Delta \end{aligned}\tag6\]其中$y_i=\pm1$，$\Delta$是常数。
大工作集的选择和两层坐标下降框架
前面提过，如果一次更新只选择两个变量作为工作集，线性约束导致其不易下降。一个自然的想法就是扩大工作集，这样工作集对应的变量$\pmb\alpha_B$不大会受线性约束的限制。但是大工作集带来的是计算梯度的开销增大，它是与$\vert B\vert$成正比的；此外，当$\vert{B}\vert>2$，子问题也不再有闭式解了，迭代优化必然导致计算代价增大。如果使用一般的优化软件包精确求解，计算代价是$O(\vert{B}\vert^2)$甚至是$O(\vert{B}\vert^3)$的。作者因此考虑近似求解子问题：在选择大变量集后，从工作集中选择两个变量进行更新，因为此时问题(应该叫子子问题)是有闭式解的。为此作者设计了二层的坐标下降框架，在内循环中，算法执行$r$次坐标下降，其中$r$是一个人为指定的超参数。下图是该框架的伪代码
上述框架并没有指定工作集选择的方法，因此框架可以有多种实现，作者这里介绍了两种实现方法。
外部随机/循环+内部贪婪
该方法使用随机或者是循环来选择大工作集$B$，然后基于梯度信息来进行贪婪选择，这里考虑的是最大违反对方法，还是可以参考https://welts.xyz/2021/07/10/wss/。伪代码如下
外部贪婪+内部随机/循环
该实现和上面的实现相反，这里是基于贪心选择$r$个最大违反对，即 \(B=\{i_1,j_1\}\cup\{i_2,j_2\}\cup\cdots\cup\{i_r,j_r\}\) 其中每一对$(i,j)$都是当前变量集中的最大违反对，也就是前$r$个违反程度最大的变量对。对于求解具有大|B|的子问题的内部坐标下降过程，我们提到了贪婪选择和随机/循环选择都不合适。主要思想是，因为外部工作集B现在包含了r个最违反的对，这些对可以被依次认为是内部工作集。如果向量$\pmb\alpha$在内部迭代中没有明显的变化，很可能每一对仍然是违反的。因此在$r$次内部求解中，大部分情况下$\pmb\alpha$是可以被更新的。算法过程如下所示
注意到算法在用$r$个违反对连续更新$\pmb\alpha$，而不考虑更新一次后，后面的$(i,j)$是否仍是违反对:
文章的后面是实验部分，我们这里不做过多介绍。
总结
我们对单类SVM和SVDD问题做了简单介绍，同时借助论文得到了求解该对偶问题的框架与方法，其中单类SVM对偶问题的求解法被纳入到LIBLINEAR中。
