An Improved Algorithm for the Solution of the Regularization Path of Support Vector Machine

摘要

This paper describes an improved algorithm for the numerical solution to the support vector machine (SVM) classification problem for all values of the regularization parameter $C$ . The algorithm is motivated by the work of Hastie and follows the main idea of tracking the optimality conditions of the SVM solution for ascending value of $C$ . It differs from Hastie's approach in that the tracked path is not assumed to be 1-D. Instead, a multidimensional feasible space for the optimality condition is used to solve the tracking problem. Such a treatment allows the algorithm to properly handle data sets which Hastie's approach fails. These data sets are characterized by the presence of linearly dependent points (in the kernel space), duplicate points, or nearly duplicate points. Such data sets are quite common among many real-world data, especially those with nominal features. Other contributions of this paper include a unifying formulation of the tracking process in the form of a linear programming problem, update formula for the linear programs, considerations that guard against accumulation of errors resulting from the use of incremental updates, and routines to speed up the algorithm. The algorithm is implemented under the Matlab environment and is available for download. Experiments with several data sets including data set having up to several thousand data points are reported.