Multi-parameter safe sample elimination rule for accelerating nonlinear multi-class support vector machines. (November 2019)

• Record Type: Journal Article
• Authors: Pang, Xinying; Pan, Xianli; Xu, Yitian
• Is Part Of: Pattern recognition. Volume 95(2019:Nov.)
• Page Start: 1
• Page End: 11
• Publication Date: 2019-11
• Subjects: K-SVCR -- Twin-KSVC -- Safe elimination rule -- Multi-class classification -- Multi-parameter; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.05.037
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: A safe sample elimination rule (SSE) for the multi-class models K-SVCR and Twin-KSVC is presented based on variational inequality. Our SSE can delete the redundant samples to accelerate the computational speed. Our SSE guarantees the solution to be exactly the same with the original problem. Our SSE is not only efficient for single parameter case but also for multi-parameter case. Abstract: K-SVCR and Twin-KSVC are two novel algorithms to deal with multi-class problems. They have achieved good performance since they evaluate all training samples into a "1-versus-1-versus-rest" structure. But they are extremely time consuming, so it remains challenging to apply them into large-scale problems directly. Inspired by the sparse solution of SVMs, in this paper, we propose a safe sample elimination rule (SSE) for multi-class classifiers K-SVCR and Twin-KSVC, termed as SSE-K-SVCR and SSE-T-KSVC, to reduce computation time. With our rule, many redundant samples of all classes can be identified and deleted before actually solving the problem, so the scale of dual problems can be reduced a lot. And our methods are safe, i.e., they can derive identical optimal solutions as K-SVCR and Twin-KSVC, respectively. So the testing accuracy keeps unchanged. Besides, the methods can be embedded into grid search method to accelerate the whole training process, and they are effective both for penalty parameter and kernel parameter. Finally, a fast algorithm clipDCD is introduced to reduce the computation time for larger datatset. Experimental results on one artificial dataset and seventeen benchmark datasets demonstrate the effectiveness and safety of our proposed methods.