Multi-variable estimation-based safe screening rule for small sphere and large margin support vector machine

摘要

Small Sphere and Large Margin (SSLM) SVM is one of the most competitive methods for Novelty Detection. However, the existing solvers for SSLM cannot deal with large data due to the expensive time cost. Although recently emerged safe screening methods can effectively enhance the computational speed, it is not available for SSLM because SSLM has multiple variables which cannot be represented explicitly by the linear combination of training samples. In this work, we construct a new safe screening rule for SSLM (MVE-SSR-SSLM) by integrating the ν-property, KKT conditions and variational inequalities. It is the first safe screening rule for a family of hypersphere support vector machine with multiple variables. The inactive samples are removed before actually solving the problem to accelerate the solving procedure without any loss of safety. Numerical experiments on fifteen benchmark datasets and Chinese wine dataset are conducted to show the validity and stability of the proposed MVE-SSR-SSLM.