Support Vector Machine Classifier via L0/1 Soft-Margin Loss
Support Vector Machine Classifier via L0/1 Soft-Margin Loss
复制标题
通过 $L_{0/1}$ 软边际损失的支持向量机分类器
DOI：
10.1109/tpami.2021.3092177
复制
发表时间：
2022-10-01
影响因子：
23.6
通讯作者：
Xiu, Naihua
中科院分区：
文献类型：
--
作者：
Wang, Huajun;Shao, Yuanhai;Xiu, Naihua
在过去的二十年里，支持向量机由于其广泛的应用而引起了广泛的关注，因此大量的工作已经开发了优化算法来解决具有各种软边际损失的支持向量机。有鉴于此，本文旨在解决一种理想的软边际损失支持向量机：L-0/1软边际损失支持向量机(简称L-0/1-支持向量机)。许多现有的(非)凸软保证金损失可以视为L-0/1软保证金损失的替代品之一。尽管L-0/1-支持向量机是离散的，但我们设法建立了它的最优性理论，包括最优解的存在性、最优解与P-平稳点的关系。这些不仅使我们能够提供L-0/1支持向量的严格定义，而且还允许我们定义工作集。结合这一工作集，提出了一种快速交替方向乘子法，其极限点是L-0/1-支持向量机的局部最优解。最后，数值实验表明，该方法在计算速度和支持向量个数方面均优于支持向量机社区中的一些主流分类算法。数据量越大，其优势就越明显。
Support vector machines (SVM) have drawn wide attention for the last two decades due to its extensive applications, so a vast body of work has developed optimization algorithms to solve SVM with various soft-margin losses. To distinguish all, in this paper, we aim at solving an ideal soft-margin loss SVM: L-0/1 soft-margin loss SVM (dubbed as L-0/1-SVM). Many of the existing (non)convex soft-margin losses can be viewed as one of the surrogates of the L-0/1 soft-margin loss. Despite its discrete nature, we manage to establish the optimality theory for the L-0/1-SVM including the existence of the optimal solutions, the relationship between them and P-stationary points. These not only enable us to deliver a rigorous definition of L-0/1 support vectors but also allow us to define a working set. Integrating such a working set, a fast alternating direction method of multipliers is then proposed with its limit point being a locally optimal solution to the L-0/1-SVM. Finally, numerical experiments demonstrate that our proposed method outperforms some leading classification solvers from SVM communities, in terms of faster computational speed and a fewer number of support vectors. The bigger the data size is, the more evident its advantage appears.