The solution paths of multicategory support vector machines: Algorithm and applications

The solution path of a regularization method means the entire set of solutions indexed by each value of the regularization parameter that controls the complexity of a fitted model. An algorithm for fitting the entire regularization path of the support vector machine (SVM) was recently proposed by Hastie et al. (2004). It allows effective computation of solutions and greatly facilitates the choice of the regularization parameter that balances a trade-off between complexity of a solution and its fit to data. Extending the idea to more general setting of the multiclass case, we characterize the coefficient path of the multicategory SVM via the complementarity conditions for optimality. The extended algorithm provides a computational shortcut to attain the entire spectrum of solutions from the most regularized to the completely overfitted ones.; In practice, large data sets and the choice of a flexible kernel may pose a computational challenge to the sequential updating algorithm. We extend the solution path algorithm to incorporate different data weights and apply it to a compressed data set with weights by subset sampling to alleviate the computational load for large data sets. A few approaches for approximate solution paths are proposed. In addition, some related computational issues are discussed and the effectiveness of the algorithm is demonstrated for some benchmark data sets.