• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Knowledge-Based Systems >A fast algorithm for kernel 1-norm support vector machines
【24h】

A fast algorithm for kernel 1-norm support vector machines

机译：内核1-范数支持向量机的快速算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper presents a fast algorithm called Column Gencration Newton (CGN) for kernel 1-norm support vector machines (SVMs). CGN combines the Column Gencration (CG) algorithm and the Newton Linear Programming SVM (NLPSVM) method. NLPSVM was proposed for solving 1-norm SVM, and CG is frequently used in large-scale integer and linear programming algorithms. In each iteration of the kernel 1-norm SVM, NLPSVM has a time complexity of O(ℓ~3), where ℓ is the sample number, and CG has a time complexity between O(ℓ~3) and O(n~('3)), where n is the number of columns of the coefficient matrix in the subproblem. CGN uses CG to generate a sequence of subproblems containing only active constraints and then NLPSVM to solve each subproblem. Since the subproblem in each iteration only consists of n' unbound constraints, CGN thus has a time complexity of O(n~('3)), which is smaller than that of NLPSVM and CG. Also, CGN is faster than CG when the solution to 1-norm SVM is sparse. A theorem is given to show a finite step convergence of CGN. Experimental results on the Ringnorm and UCI data sets demonstrate the efficiency of CGN to solve the kernel 1 -norm SVM.
机译：本文提出了一种用于内核1-范数支持向量机（SVM）的称为Column Gencration Newton（CGN）的快速算法。 CGN结合了列生成（CG）算法和牛顿线性编程SVM（NLPSVM）方法。 NLPSVM是为解决1-范数支持向量机而提出的，CG通常用于大规模整数和线性规划算法中。在内核1-范数SVM的每次迭代中，NLPSVM的时间复杂度为O（ℓ〜3），其中ℓ是样本数，而CG的时间复杂度在O（ℓ〜3）和O（n〜（ '3）），其中n是子问题中系数矩阵的列数。 CGN使用CG生成仅包含活动约束的子问题序列，然后使用NLPSVM解决每个子问题。由于每次迭代中的子问题仅包含n'个未约束，因此CGN的时间复杂度为O（n〜（'3）），小于NLPSVM和CG的时间复杂度。同样，当针对1-norm SVM的解决方案稀疏时，CGN比CG快。给出了一个定理，以显示CGN的有限步收敛。在Ringnorm和UCI数据集上的实验结果证明了CGN解决内核1-norm SVM的效率。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号