求解非凸截断L 1⁃SVM的多阶段非精确线搜割平面方法

图1 截断损失函数

Fig.1 Truncated⁃Loss function

令 $H_{δ} (u) = {(δ - u)}_{+}$ ，显然 $H_{δ}$ 是一个凸函数，所以截断Hinge损失函数可以由两个凸函数之差构成，其中两个凸函数分别为 $L_{1}$ 和 $H_{δ}$ .此外，根据MM框架原理，显然可以得知 $\hat{F} (w)$ 就是 $F (w)$ 的替代函数.但是在这里 ${\hat{L}}_{1} (u)$ 不是光滑误差，不满足Lipschitz条件，因此不能直接套用MM框架来解决此问题.然而可以通过多阶段策略，避免MM框架必须要满足Lipschitz条件的约束，巧妙地解决这类非凸非光滑问题.

MS⁃SVM算法表明，浮点运算已经严重影响了 $L_{1}$ 正则化在随机学习和在线学习中的稀疏性^[25].有学者通过分别处理正则化和损失函数，得到一个子问题的闭式解，使这个问题得以解决^[26,27].MS⁃SVM算法也延续了这个优点，因此使用多阶段策略同样可以继承这些优点.MS⁃SVM算法是在每个阶段之前首先剔除一部分outlier点，然后求解SVM原问题或对偶问题，得到解 $w_{t}$ ，进行多个阶段的批处理直到算法收敛，停止迭代.这种方法能得到稀疏的支持向量，但时间消耗较大，因为每个阶段都必须求解一个批处理问题，计算复杂度相当高，不适于大规模问题求解.其实每个阶段不需要批处理精确求解 $w_{t}$ ，只需要得到满足outlier点条件的解 $w_{t}$ 就可以进入下一阶段，将outlier点剔除之后，对样本进行更新，继续进行训练.因此可以用一种快速的方法来替代原有的批处理SVM方法以提升其性能.

2 非精确线搜割平面算法

在上一节定义的样本集中，式(3)可以写成如下优化问题形式：

\underset{w}{m i n} F (w) = \frac{1}{2} {‖w‖}^{2} + C R (w)

(6)

其中，

R (w) = \sum_{i = 1}^{m} L_{1} [y_{i} (〈w, x_{i}〉 + b)]

称为Hinge损失函数.实际应用中，有时SVM会带有偏置项 $b$ ，常用的处理技巧是将其放入权重 $w$ 中统一处理：

x_{i}^{T} ← [x_{i}^{T}, 1], w^{T} ← [w^{T}, b]

在CPA算法中原始问题式(6)被称为主问题，使用Teo et al^[21]的方法可以定义一个子问题：

w_{t} = \underset{w}{a r g m i n} F_{t} (w) = [\frac{1}{2} {‖w‖}^{2} + C R_{t} (w)]

(7)

因为 $R (w)$ 在 $S$ 上为凸损失函数，若在 $w'$ 处的次梯度为 $a'$ ，则有不等式：

R (w) ≥ R (w') + 〈w - w', a'〉, ∀ w ∈ S

成立.推广开，设 $R (w)$ 在点 $w_{1}, w_{2}, ⋯, w_{t}$ 的次梯度分别为 $a_{1}, a_{2}, ⋯, a_{t}$ ，则 $R (w)$ 的分段线性近似函数可表示为：

R_{t} (w) = \underset{i = 1,2, ⋯, t}{m a x} \{0, R (w_{i}) + 〈w - w_{i}, a_{i}〉\}

(8)

其中， $R (w_{i}) + 〈w - w_{i}, a_{i}〉 = 0$ 被称为点 $w_{i}$ 处的割平面.显然 $R_{t} (w)$ 也是凸函数，而且随着迭代次数的增加，分段线性逼近更加精确，如图2所示.

图2

图2 凸函数的分段线性近似

Fig.2 Piecewise linear approximation for convex function

OCAS算法在每次求得 $w_{t}$ 后，关键是进行一次精确线性搜索，如式(9)：

λ_{t} = \underset{λ ≥ 0}{a r g m i n} J ((1 - λ) w_{t - 1}^{b} + λ w_{t})

(9)

在精确线性搜索求解时需要通过排序所有的 $λ_{i}$ 值来得到 $λ_{t}$ 值.容易知道，排序算法的时间复杂度为 $O (m l g m)$ .在处理大规模机器学习问题的时候，一方面，精确线性搜索式(9)不仅受到特征维数的影响，并且关键的排序算法会受到数据规模的限制；另一方面，优化算法只是一种手段，其目的是使机器学习有更好的泛化能力，有时为了使机器学习算法获得良好的鲁棒性，无需求得模型的最优精确解.储德军等^[24]在Franc and Sonnenburg^[22]工作的基础上（算法2），提出一种非精确线性搜索的优化割平面算法（INexact⁃Line⁃Search OCAS,INOCAS，算法3），克服了上述缺点，并且保持了OCAS算法的优点，能够保证目标函数值 $F (w_{t})$ 单调下降，并且比OCAS算法的效率更高.加速效果如图3所示.

图3

图3 非精确线性搜索割平面方法的加速效果^[24]

Fig.3 Speedup effect of INOCAS^[24]

算法2 非精确线性搜索算法

Input： $γ = 0.01, λ_{n e w} = 0, λ_{o l d} = 0, a_{n e w} = 0,$ a_old=0,k=0

Repeat

k = k + 1

计 算 梯 度 [a_{n e w} ← m a x \{∂ f (λ_{n e w})\}]

如果 $a_{n e w} < 0, λ_{n e w} ← λ_{o l d} + 2^{k} γ$ ，则

λ_{o l d} ← λ_{n e w}, a_{o l d} ← a_{n e w}

否则，根据二点二次插值方法：

λ^{*} ← λ_{n e w} - \frac{λ_{n e w} - λ_{o l d}}{a_{n e w} - a_{o l d}} a_{n e w}

Until： $a_{n e w} > 0$

Output： $λ^{*}$

算法3 基于非精确线性搜索的加速割平面算法（INOCAS）

Input： $w_{0}, w_{0}^{*} ← w_{0}, t ← 0, ε ≥ 0$

Repeat

t ← t + 1

1.求解子问题式(7)，得到 $w_{t}$

2.利用非精确线性搜索（算法2），求得 $λ_{t}$

3. 更新 $w_{t}^{*} ← (1 - λ_{t}) w_{t - 1}^{*} + λ_{t} w_{t}$ ，并在 $w_{t}^{*}$ 处添加新的割平面，更新分段近似函数 $R_{t} (w)$

Until： $F (w_{t}^{b}) - F_{t} (w_{t}) ≤ ϵ$ 3 Output： $w_{t}^{*}$

多阶段策略不是一次批处理求解得到最优值，因此在每个阶段都利用批处理精确求解会降低算法的效率.非精确线性搜索能在保证单调性的条件下求得满足要求的解，同时计算复杂度很低.下一节将阐述这样求解的优点.

3 多阶段非精确线搜割平面方法

本节提出一个简单有效的多阶段非精确线性搜索的优化割平面方法（Multistage Inexact⁃Line⁃Search Ocas,MILSO）来解决关于截断Hinge损失的线性SVM问题，如算法4所示.

算法4 MILSO

Input： $w_{0}$

Repeat

1.计算 $S_{t} = S - O^{t}$

2.利用INOCAS算法，在样本集 $S_{t}$ 上求得 $w_{t}$

Until： $O^{t + 1} = O^{t}$

Output： $w_{t}$

定义2 outlier点满足式(10)的点称为outlier点.其中 $O^{t}$ 代表第 $t$ 阶段的outlier点：

O^{t} = \{(x_{i}, y_{i}) ∈ S : y_{i} [〈w_{t}, x_{i}〉 + b^{t}] < δ\}

(10)

算法第一步首先要计算得到提前删去的outlier点；第二步对于样本集合 $S_{t}$ ，利用INOCAS算法非精确解搜索100次，得到一个不是最优解但趋于最优解的解 $w_{t}$ .以上为一个阶段.然后利用式(10)继续计算得到集合 $O^{t}$ ，反复迭代最终得到最优解.

直观地说，多阶段程序的目的是不断从之前的支持向量集合中剔除所有当前异常值（outlier点），并通过截断的损失函数提供更鲁棒的分类器，朝一个最佳的优化子集移动.特别的，算法2是一种非常简单直观的方法，每次迭代的时间消耗为 $O (m)$ ，主要用来计算梯度，因此整个算法2的时间复杂度为 $O (k m)$ ，其中 $k$ 为迭代次数， $m$ 为样本个数.在大规模数据问题中，通常 $k ≪ l g m$ ，所以该算法的时间复杂度较算法1中的排序算法更小.对比算法1和算法3可以发现，两种算法都能保证目标函数单调下降，但算法3将算法1的精确排序问题转化为求解次梯度函数值的问题，减少了计算复杂度.在MS⁃SVM算法里，每个阶段都需要用一个批处理算法求解一个精确解，调用的LIBSVM算法的时间复杂度为 $O (m^{3})$ ，远远高于算法2.理论分析表明，MILSO算法比MS⁃SVM算法的计算复杂度更低.下面给出算法4的收敛性分析.

定理1 $∀ w_{0} ∈ R^{N}$ ，假设 $w_{t}$ 是由MILSO算法得到，则有：

(1) $\hat{F} (w_{t})$ 是单调递减的.若 $S_{t + 1} ≠ S_{t}$ ，则 $\hat{F} (w_{t + 1}) < \hat{F} (w_{t})$ .

(2)存在一个正常数 $t_{0}$ 使 $S_{t_{0} + 1} = S_{t_{0}}$ ，则 $S_{t} = S_{t_{0}}, ∀ t ≥ t_{0}$ .

(3)存在一个向量 $w^{*} ∈ R^{N + 1}$ ，使 $w_{t}$ 在有限步骤收敛到 $w^{*}$ .

(4) $w^{*}$ 是 $\hat{F}$ 的一个局部最小点.

证明因为算法MILSO在每次迭代过程中都会进行非精确线性搜索，保证目标函数值 $F (w_{t})$ 序列是单调下降的(见文献[22]中的Theorem 1)，即定理1第（1）条得证.

定理1第（2）条很显然.

注意到每个原始SVM子问题在指定集合 $S_{t}$ 上的解是唯一的，而最多存在有 $2^{m}$ 种集合 $S_{t}$ ，所以定理1第（3）条得证.

令:

S^{*} = S - \{(x_{i}, y_{i}) ∈ S : y_{i} [〈w^{*}, x_{i}〉 + b^{*}] < δ\}

显然，存在一个数 $δ > 0$ ，使得如果 $‖w - w^{*}‖ < δ_{0}$ ，那么与 $w$ 相关的异常值包含 $S^{*}$ ，即对于所有满足 $‖w - w^{*}‖ < δ_{0}$ 的点 $w$ ，有 $\hat{F} (w^{*}) ≤ \hat{F} (w)$ ，定理1第（4）条得证.

下面简单将本文算法与相关参考算法进行对比分析.

(1)与标准的CCCP算法^[8,9]相比较，MILSO算法不是另一种简单的寻找局部最小值的方法，除了纯凹凸优化技巧外，它应被视作一种实用的学习策略.

(2)与MS⁃SVM算法相比，多阶段策略能在保证稀疏性的同时，以更少的时间消耗来解决问题.

(3)多阶段优化策略已被用于解决一些非凸问题.如Zhang^[28]面对截断正则化项导致的非凸性提出一种有效的多级凸松弛策略来解决稀疏学习中的非凸问题，目标是改进文献[9,10]中求解支持向量稀疏性的方法，其中支持向量的稀疏性是由非凸损失导致的.

4 多阶段非精确线搜割平面方法

本节对本文提出的方法进行对比验证.实验采用Mac Pro工作站（2×2.8 GHz Quad⁃Core Intel Xeon处理器，4 GB 667 MHz DDR2内存，Mac OS X版本10.5.4）.C语言编译器gcc 4.2.1.在常用的大规模数据库(表1）上进行实验.标准数据库均来自林智仁小组(https:∥www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/).

表1 数据库描述

Table 1 Description of databases

数据集	训练集大小	测试集大小	维数
Covtype	116202	464810	54
Ijcnn1	49990	91701	22
A9a	32561	16281	123
Rcv1	20242	677399	47236

在常用的大规模数据库上，分别用三种算法对其进行训练测试，设置参数 $C = 1, δ = 0$ ,且均不含偏置 $b$ ，实验结果如表2至表5所示.

表2 三种算法在数据集Covtype上的线性分类结果

Table 2 Linear classification of three algorithms on the Covtype dataset

算法

阶段

支持

向量数

准确度

(%)

CPU

时间（s）

SVM

257123

75.5231

3.96

MS⁃SVM

331

14127

77.0152

122.61

MILSO

266

11578

77.1022

76.32

表3 三种算法在数据集Ijcnn1上的线性分类结果

Table 3 Linear classification of three algorithms on the Ijcnn1 dataset

算法

阶段

支持

向量数

准确度

(%)

CPU

时间（s）

SVM

21915

91.7896

0.21

MS⁃SVM

2057

93.4568

2.05

MILSO

1983

93.4886

1.13

表4 三种算法在数据集A9a上的线性分类结果

Table 4 Linear classification of three algorithms on the A9a dataset

算法

阶段

支持

向量数

准确度

(%)

CPU

时间（s）

SVM

19793

84.9886

0.45

MS⁃SVM

1102

84.8634

1.98

MILSO

1078

84.9126

1.09

表5 三种算法在数据集Rcv1上的线性分类结果

Table 5 Linear classification of three algorithms on the Rcv1 dataset

算法

阶段

支持

向量数

准确度

(%)

CPU

时间（s）

SVM

7017

96.1493

0.06

MS⁃SVM

6735

96.2216

0.23

MILSO

6653

96.2354

0.14

对比三种算法在四个数据库上的实验效果可以发现，MILSO算法得到的支持向量数是远低于传统SVM算法的，也是低于MS⁃SVM算法的，因此MILSO算法在稀疏性上有很好的表现.此外，CPU时间消耗也大大减少.从图4可以看出，MILSO算法的CPU时间比MS⁃SVM几乎少了一半.因为MILSO算法在每个阶段采用的都是非精确线性搜索算法，计算复杂度低于传统SVM，实验还表明，在每个阶段非精确线性搜索100次就可以达到对解的要求，在多阶段策略中很快就能从当前阶段跳到下一阶段，每个阶段用的时间也是少于MS⁃SVM的，因而减少了CPU总时间，如图5和图6所示.综上所述，在常用的大规模数据库上，和传统算法相比，MILSO算法利用多阶段准则对损失函数进行截断，可以得到更稀疏的支持向量，并且能够大大减少时间消耗，验证了MILSO方法的有效性.

图4

图4 不同算法的CPU时间

Fig.4 The CPU time of difference algorithms

图5

图5 MILSO 和MS⁃SVM在数据集A9a上的每个阶段所用的CPU时间

Fig.5 The CPU time of each stage of MILSO and MS⁃SVM on the A9a dataset

图6

图6 MILSO 和MS⁃SVM在数据集Rcv1上的每个阶段所用的CPU时间

Fig.6 The CPU time of each stage of MILSO and MS⁃SVM on the Rcv1 dataset

SVM在处理大规模数据时，线性增长的支持向量是限制其效率的主要原因，因此采用截断策略可以得到更稀疏的支持向量.在处理相同的非凸截断问题时，和传统MS⁃SVM算法相比，MILSO算法得到的支持向量数更少，并在每个阶段都使用处理效率更高的INOCAS算法，因此在CPU时间上几乎快了一倍，如前文的表2至表5所示.

为验证算法的收敛性，对比三种算法的目标函数值变化情况，如图7至图10所示，可以看出：

图7

图7 三种算法在Covtype上的收敛性

Fig.7 Convergence of three algorithms on the Covtype dataset

图8

图8 三种算法在Ijcnn1上的收敛性

Fig.8 Convergence of three algorithms on the Ijcnn1 dataset

图9

图9 三种算法在A9a上的收敛性

Fig.9 Convergence of three algorithms on the A9a dataset

图10

图10 三种算法在Rcv1上的收敛性

Fig.10 Convergence of three algorithms on the Rcv1 dataset

(1)MILSO算法优化的目标函数在有限时间内收敛到稳定值，验证了算法具有收敛性.

(2)对比不同数据集，多阶段准则对目标函数的优化大大优于传统的SVM算法，收敛时目标函数值远低于SVM收敛时的目标函数值.

(3)和MS⁃SVM算法相比，由于MILSO算法使用了非精确线搜索，在CPU时间上的表现更优.

5 总结

本文提出一种基于非精确线性搜索的多阶段策略MILSO，继承了非精确线性搜索的优点.与MS⁃SVM算法里的每个阶段都要调用批处理方法相比较，MILSO算法在每个阶段进行非精确求解，能迅速进入下一阶段，计算复杂度低，且能保证目标函数的单调性，保证了模型的稳定性.另一方面，多阶段策略在每个阶段剔除一部分outlier点，得到了稀疏的支持向量.理论分析该方法具有收敛性，实验也证明MILSO算法的性能优于MS⁃SVM算法.下一步的主要工作是将此方法扩展到随机或增量形式.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Vapnik

The nature of statistical learning theory

New York：Springer，1995，314.

[2]

Kelley

J E

The cutting plane method for solving convex problems

Journal of the Society for Industrial & Applied Mathematics,1960，8(4)：703-712.

[3]

Chang

K W

， Hsieh

C J

， Lin

C J

Coordinate descent method for large⁃scale L2⁃loss linear support vector machines

Journal of Machine Learning Research，2008，9(3)：1369-1398.

[4]

Hastie

， Zhu

Comment on "Support vector machines with applications"

Statistical Science，2006，21(3)：352-357.

[5]

Zhang

Statistical behavior and consistency of classification methods based on convex risk minimization

The Annals of Statistics，2004，32(1)：56-85.

[6]

Cheung

Y M

， Lou

Efficient generalized conditional gradient with gradient sliding for composite optimization

∥Proceedings of the 24^th International Conference on Artificial Intelligence. Buenos Aires，Argentina：AAAI Press，2015：3409-3415.

[7]

Steinwart

Sparseness of support vector machines

Journal of Machine Learning Research，2003，4(6)：1071-1105.

[8]

Collobert

， Sinz

， Weston

，et al .

Trading convexity for scalability

∥Proceedings of the 23^rd International Conference on Machine Learning. Pittsburgh，PA，USA：ACM，2006：201-208.

[9]

Liu

S J

， Shen

X T

， Wong

W H

Computational developments of ψ⁃learning

∥Proceedings of the 5^th SIAM International Conference on Data Mining. Newport Beach，CA,USA：Society for Industrial and Applied Mathematics，2005：1-11.

[本文引用: 3]

[10]

Y C

， Liu

Y F

Robust truncated hinge loss support vector machines

Journal of the American Statistical Association，2007，102(479)：974-983.

[11]

L T H

， Tao

P D

Solving a class of linearly constrained indefinite quadratic problems by D

.C. algorithms. Journal of Global Optimization，1997，11(3)：253-285.

[12]

Yuille

A L

， Rangarajan

The concave⁃convex procedure

Neural computation，2003，15(4)：915-936.

[13]

Mairal

Stochastic majorization⁃minimization algorithms for large⁃scale optimization

∥Proceedings of the 26^th International Conference on Neural Information Processing Systems. Lake Tahoe，NV,USA：Curran Associates Inc.，2013：2283-2291.

[14]

Mairal

Incremental majorization⁃minimization optimization with application to large⁃scale machine learning

SIAM Journal on Optimization，2015，25(2)：829-855.

[15]

Fang

， Li

C J

， Lin

Z C

，et al .

Spider：near⁃optimal non⁃convex optimization via stochastic path integrated differential estimator

2018，arXiv：1807. 01695.

[16]

Carmon

， Duchi

J C

， Hinder

，et al .

Accelerated methods for nonconvex optimization

SIAM Journal on Optimization，2018，28(2)：1751-1772.

[17]

Lan

G H

， Yang

Accelerated stochastic algorithms for nonconvex finite⁃sum and multi⁃block optimi⁃zation

2018，arXiv：1805.05411.

[18]

Tao

， Wu

G W

， Chu

D J

Improving sparsity and scalability in regularized nonconvex truncated⁃loss learning problems

IEEE Transactions on Neural Networks and Learning Systems，2018，29(7)：2782-2793.

[19]

Shalev⁃Shwartz

， Singer

， Srebro

，et al .

Pegasos：primal estimated sub⁃gradient solver for SVM

Mathematical Programming，2011，127(1)：3-30.

[20]

Joachims

Training linear SVMs in linear time

∥Proceedings of the 12^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia，PA，USA：ACM，2006：217-226.

[21]

Teo

C H

， Smola

， Vishwanathan

S V N

，et al .

A scalable modular convex solver for regularized risk minimization

∥Proceedings of the 13^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose，CA，USA：ACM，2007：727-736.

[22]

Franc

， Sonnenburg

Optimized cutting plane algorithm for support vector machines

∥Proceedings of the 25^th International Conference on Machine Learning. Helsinki，Finland：ACM，2008：320-327.

[本文引用: 3]

[23]

Chu

D J

， Zhang

C S

， Tao

A faster cutting plane algorithm with accelerated line search for linear SVM

Pattern Recognition，2017，67：127-138.

[24]

储德军，陶安，高乾坤等 .

求解线性SVM的非精确步长搜索割平面方法

模式识别与人工智能，2014，27(8)：692-700.

[本文引用: 4]

Chu

D J

， Tao

， Gao

Q K

，et al .

Optimized cutting plane method for linear SVM via inexact step⁃length search

Pattern Recognition and Artificial Intelligence，2014，27(8)：692-700.

[本文引用: 4]

[25]

Langford

， Li

L H

， Zhang

Sparse online learning via truncated gradient

Journal of Machine Learning Research，2009，10：777-801.

[26]

Duchi

J C

， Shalev⁃Shwartz

， Singer

，et al .

Composite objective mirror descent

∥23^rd International Conference on Learning Theory. Haifa,Israel：COLT，2010：14-26.

[27]

Xiao

Dual averaging methods for regularized stochastic learning and online optimization

The Journal of Machine Learning Research，2010，11：2543-2596.

[28]

Zhang

Analysis of multi⁃stage convex relaxation for sparse regularization

Journal of Machine Learning Research,2010,11：1081-1107.