摘要
截断Hinge损失能够获得更为稀疏的支持向量,因此在鲁棒性上有显著的优点,但却由此导致了难以求解的非凸问题.MM(Majorization⁃Minimization)是一种求解非凸问题的一般框架,多阶段MM策略已经在稀疏性上取得了很好的效果,但是计算复杂度较高.另一方面,非精确线搜割平面方法可以高效求解线性支持向量机问题.针对截断L1⁃SVM(L1 Support Vector Machine)这一非凸非光滑问题,提出一种基于非精确线性搜索的多阶段割平面方法,避免每个阶段都进行批处理求解,克服了计算复杂度高的缺点,具有每个阶段求解速度快的优点.该算法适用于大规模问题的求解,也从理论上保证了其收敛性.最后,与其他多阶段算法进行了实验对比,验证了该方法的有效性.
The truncated Hinge loss can get more sparse support vectors,thus it has significant advantages in robustness.But it leads to a non⁃convex problem which is difficult to solve.MM(Majorization⁃Minimization)is a general framework and is suitable for solving non⁃convex problems.The specific multi⁃stage MM strategy has a good effect in sparsity for the non⁃convex problem considering the structure of the objective function,but higher computational complexity is caused.On the other hand,a cutting plane method with inexact line search can efficiently solve linear support vector machines,and the theoretical analysis shows that it has the same optimal convergence bound as the exact line search method with a higher speed and lower cost.In this paper,for the truncated L1⁃SVM(L1 Support Vector Machine)which is non⁃convex and non⁃smooth,we propose a multi⁃stage cutting plane method with inexact line search.It avoids solving the problem by a batch method at each stage,which overcomes the shortcoming of high computational complexity.Meanwhile,there is an advantage that a faster solution can be got at each stage.The algorithm is suitable for solving large⁃scale problems and it is convergent in theory.Finally,comparison experiments with other multi⁃stage algorithm demonstrate that our method is effective.
作者
袁友宏
刘欣
鲍蕾
Yuan Youhong;Liu Xin;Bao Lei(Army Academy of Artillery and Air Defense of PLA,Hefei,230031,China)
出处
《南京大学学报（自然科学版）》
CAS
CSCD
北大核心
2020年第1期98-106,共9页
Journal of Nanjing University（Natural Science）
基金
国家自然科学基金(61673394)
安徽省自然科学基金(1908085MF193)
