A safe sample screening rule for Universum support vector machines

摘要

Universum support vector machine (U-SVM), due to its tremendous accuracy improvements, has been expanded and applied in all kinds of fields. Universum encodes related prior knowledge but does not belong to any class of interest. With Universum, the number of training samples and computational complexity are clearly increased. Inspired by the sparsity of SVMs, a safe sample screening rule (SSSR) for U-SVM is proposed in this paper. Our SSSR eliminates not only the labelled samples but also the Universum samples before training process, then the computational cost is dramatically reduced. Moreover, the same solution as the original problem can be obtained by utilizing our SSSR, that is, the training process is guaranteed to be accelerated safely. Besides, we extend our rule to the Universum twin support vector machine (U-TSVM), and the SSSR for U-TSVM is also discussed in this paper. To the best of our knowledge, SSSR is the only existing safe screening method for U-SVMs. Numerical experiments on seventeen benchmark datasets, ABCDETC dataset and Chinese wine dataset demonstrate that the computational cost can be dramatically reduced without sacrificing the optimality of the final solution by our SSSR.