Fast multi-label core vector machine

摘要

The existing multi-label support vector machine (Rank-SVM) has an extremely high computational complexity due to a large number of variables in its quadratic programming. When the Frank-Wolfe (FW) method is applied, a large-scale linear programming still needs to be solved at any iteration. Therefore it is highly desirable to design and implement a new efficient SVM-type multi-label algorithm. Binary core vector machine (CVM), as a variant of traditional SVM, is formulated as a quadratic programming with a unit simplex constraint, in which each linear programming in FW has an analytical solution. In this paper, we combine Rank-SVM with CVM to construct a novel SVM-type multi-label classifier (Rank-CVM) which is described as the same optimization form as binary CVM. At its any iteration of FW, there exist analytical solution and step size, and several useful recursive formulae for proxy solution, gradient vector, and objective function value, all of which reduce computational cost greatly. Experimental study on nine benchmark data sets shows that when Rank-CVM performs as statistically well as its rival Rank-SVM according to five performance measures, our method runs averagely about 13 times faster and has less support vectors than Rank-SVM in the training phase under C/C++ environment.