A faster cutting plane algorithm with accelerated line search for linear SVM
A faster cutting plane algorithm with accelerated line search for linear SVM
复制标题
一种具有线性 SVM 加速线搜索的更快割平面算法
DOI：
10.1016/j.patcog.2017.02.006
复制
发表时间：
2017-07
影响因子：
8
通讯作者：
Tao Qing
中科院分区：
文献类型：
--
作者：
Chu Dejun;Zhang Changshui;Tao Qing
切平面算法（CPA）是迭代一阶梯度法的一种推广，该算法通过支持超平面对目标函数进行逐次逼近。CPA通过利用正则化结构来解决机器学习中的正则化损失最小化问题。特别是对于线性支持向量机（SVM），嵌入直线搜索程序可以有效地弥补函数值的波动，加快实际问题的收敛速度。而现有的基于排序算法的线搜索策略耗时为0 （mlogm）。在本文中，我们提出了一个更有效的线搜索求解器，它只花费线性时间。它可以推广到多类支持向量机，其中预先安排了一种优化的显式分段线性函数查找算法。从理论上证明了支持向量机的总训练时间缩短，实验一致证实了算法的有效性。
Cutting plane algorithm (CPA) is a generalization of iterative first-order gradient method, in which the objective function is approximated successively by supporting hyperplanes. CPA has been tailored to solve regularized loss minimization in machine learning by exploiting the regularization structure. In particular, for linear Support Vector Machine (SVM) embedding a line search procedure effectively remedies the fluctuations of function value and speeds up the convergence in practical issue. However, the existing line search strategy based on sorting algorithm takesO(mlogm) time. In this paper, we propose a more effective line search solver which spends only linear time. It can be extended to multiclass SVM in which an optimized explicit piecewise linear function finding algorithm is prearranged. The total SVM training time is proved to reduce theoretically and experiments consistently confirm the effectiveness of the proposed algorithms.
登录
查看更多内容
DOI：
--
发表时间：
2007-12
期刊：
--
影响因子：
--
作者：
Alex Smola;S. Vishwanathan;Quoc V. Le
通讯作者：
Alex Smola;S. Vishwanathan;Quoc V. Le
DOI：
--
发表时间：
2001
期刊：
--
影响因子：
--
作者：
T. Cormen;C. Leiserson;R. Rivest;C. Stein
通讯作者：
T. Cormen;C. Leiserson;R. Rivest;C. Stein
DOI：
10.1017/cbo9780511801389.013
发表时间：
2000-03
期刊：
--
影响因子：
--
作者：
N. Cristianini;J. Shawe-Taylor
通讯作者：
N. Cristianini;J. Shawe-Taylor
DOI：
10.1145/1553374.1553523
发表时间：
2009-06
期刊：
--
影响因子：
--
作者：
C. Yu;T. Joachims
通讯作者：
C. Yu;T. Joachims
DOI：
10.5555/2503308.2503355
发表时间：
2012
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
T. Do;T. Artières
通讯作者：
T. Do;T. Artières