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 \emph{et. al.} and follows the main idea of tracking the optimality conditions of the SVM solution for descending value of C. It differs from Hastie’s approach in that the tracked path is not assumed to be one-dimensional. Instead, a multi-dimensional feasible space for the optimality condition is used to solve the tracking problem. Such a treatment allows the algorithm to handle data set having duplicate points, nearly duplicate points and linearly dependent points, a common feature among many real-world data sets. Other contributions of this paper include a unifying formulation of the tracking process in the form of a linear program, an initialization routine that deals with duplicate data points, a routine that guards against accumulation of errors resulting from the use of incremental updates, a heuristics-based routine and update formula to speed up the algorithm. The algorithm is implemented under the Matlab environment and tested with several data sets including data set having up to several thousand data points.
Citation
Technical Report C09-002, Department of Mechanical Engineering.