Reference EPFL-ARTICLE-229257 URL: http: arxiv.org abs 0903.4856 Record created on 2017-06-21, modified on 2017-06-21
As @cite_8 point out, one drawback of their algorithm for the two-class SVM is that it does not work for singular kernel matrices, but requires that in the process of the algorithm, all occurring principal minors of the kernel matrix need to be invertible. The same is required by the other existing path algorithms mentioned above. However, large kernel matrices do often have very low numerical rank, even in those cases where radial base function kernels are used [Section 5.1] Hastie:2004p3702 , but of course also in the case of linear SVMs with sparse features, such as in the application to conjoint analysis discussed in this paper. The inability to deal with singular sub-matrices is probably one of the main reasons that none of the above mentioned algorithms could so far effectively be applied on medium larger scale problems @cite_8 @cite_11 . [Section 4.2] Rosset:2007p6880 report that their algorithm prematurely terminates on @math matrices due to this described problem.
@cite_11 @cite_8
2057682568 2133958955
We consider the generic regularized optimization problem β(λ) = argminβ L(y, Xβ) + λJ(β). Efron, Hastie, Johnstone and Tibshirani [Ann. Statist. 32 (2004) 407-499] have shown that for the LASSO-that is, if L is squared error loss and J(β) = ∥β∥ 1 is the l 1 norm of β-the optimal coefficient path is piecewise linear, that is, ∂β(λ) ∂λ. is piecewise constant. We derive a general characterization of the properties of (loss L, penalty J) pairs which give piecewise linear coefficient paths. Such pairs allow for efficient generation of the full regularized coefficient paths. We investigate the nature of efficient path following algorithms which arise. We use our results to suggest robust versions of the LASSO for regression and classification, and to develop new, efficient algorithms for existing problems in the literature, including Mammen and van de Geer's locally adaptive regression splines. The support vector machine (SVM) is a widely used tool for classification. Many efficient implementations exist for fitting a two-class SVM model. The user has to supply values for the tuning parameters: the regularization cost parameter, and the kernel parameters. It seems a common practice is to use a default value for the cost parameter, often leading to the least restrictive model. In this paper we argue that the choice of the cost parameter can be critical. We then derive an algorithm that can fit the entire path of SVM solutions for every value of the cost parameter, with essentially the same computational cost as fitting one SVM model. We illustrate our algorithm on some examples, and use our representation to give further insight into the range of SVM solutions.