Speeding up parameter tuning for multi-class classification: A partial parametric path algorithm

The objective functions of Support Vector Machine methods (SVMs) often include parameters to weigh the relative importance of margins and training accuracy. For multi-class classification problems, in the presence of different misclassification costs, identifying a desirable set of values for these parameters is key for a good performance. We propose a partial parametric path algorithm, based on the property that the path of optimal solutions of the SVMs with respect to the preceding parameters is piecewise linear. This partial parametric path algorithm requires the solution of just one quadratic programming problem, and a number of linear systems of equations. Thus, it can significantly reduce the computational requirements of the algorithm. To systematically explore the different weights to assign to the misclassification costs, we combine the partial parametric path algorithm with a variable neighborhood search method. Our numerical experiments show the efficiency and reliability of the proposed partial parametric path algorithm. Furthermore through our numerical experiments we also verify the combination of partial parametric path algorithm and a variable neighborhood search method helps us to find a good set of parameters systematically.