Safe Sample Screening for Support Vector Machines
Sparse classifiers such as the support vector machines (SVM) are efficient in test-phases because the classifier is characterized only by a subset of the samples called support vectors (SVs), and the rest of the samples (non SVs) have no influence on the classification result. However, the advantage of the sparsity has not been fully exploited in training phases because it is generally difficult to know which sample turns out to be SV beforehand. In this paper, we introduce a new approach called safe sample screening that enables us to identify a subset of the non-SVs and screen them out prior to the training phase. Our approach is different from existing heuristic approaches in the sense that the screened samples are guaranteed to be non-SVs at the optimal solution. We investigate the advantage of the safe sample screening approach through intensive numerical experiments, and demonstrate that it can substantially decrease the computational cost of the state-of-the-art SVM solvers such as LIBSVM. In the current big data era, we believe that safe sample screening would be of great practical importance since the data size can be reduced without sacrificing the optimality of the final solution.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise
Robust Support Vector Machines (R-SVMs) address feature noise by adopting a worst-case robust formulation that explicitly incorporates uncertainty sets into training. While this robustness improves reliability, it also l…
Safe Sample Screening for Robust Support Vector Machine
Robust support vector machine (RSVM) has been shown to perform remarkably well to improve the generalization performance of support vector machine under the noisy environment. Unfortunately, in order to handle the non-co…
Screening Rules for Convex Problems
We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations, and works in two steps. First, given any…
Safe and Efficient Screening For Sparse Support Vector Machine
Screening is an effective technique for speeding up the training process of a sparse learning model by removing the features that are guaranteed to be inactive the process. In this paper, we present a efficient screening…
Sparse LearningA Safe Screening Rule with Bi-level Optimization of $ν$ Support Vector Machine
Support vector machine (SVM) has achieved many successes in machine learning, especially for a small sample problem. As a famous extension of the traditional SVM, the $\nu$ support vector machine ($\nu$-SVM) has shown ou…