Reference EPFL-ARTICLE-229257 URL: http: arxiv.org abs 0903.4856 Record created on 2017-06-21, modified on 2017-06-21
An algorithm to compute the entire regularization path of the @math -SVM has originally been reported by @cite_8 . @cite_20 gave such an algorithm for the LASSO, and later @cite_7 and @cite_19 proposed solution path algorithms for @math -SVM and one-class SVM respectively. Also Receiver Operating Characteristic (ROC) curves of SVM were solved by such methods @cite_10 . Support vector regression (SVR) is interesting as its underlying quadratic program depends on two parameters, a regularization parameter (for which the solution path was tracked by @cite_15 @cite_13 @cite_7 ) and a tube-width parameter (for which @cite_35 recently gave a solution path algorithm). See also @cite_11 for a recent overview.
@cite_13 @cite_35 @cite_7 @cite_8 @cite_19 @cite_15 @cite_10 @cite_20 @cite_11
2963049858 2227752230 2148418853 2032708784
We investigate the relation of two fundamental tools in machine learning and signal processing, that is the support vector machine (SVM) for classification, and the Lasso technique used in regression. We show that the resulting optimization problems are equivalent, in the following sense. Given any instance of an L2-loss soft-margin (or hard-margin) SVM, we construct a Lasso instance having the same optimal solutions, and vice versa. As a consequence, many existing optimization algorithms for both SVMs and Lasso can also be applied to the respective other problem instances. Also, the equivalence allows for many known theoretical insights for SVM and Lasso to be translated between the two settings. One such implication gives a simple kernelized version of the Lasso, analogous to the kernels used in the SVM setting. Another consequence is that the sparsity of a Lasso solution is equal to the number of support vectors for the corresponding SVM instance, and that one can use screening rules to prune the set of support vectors. Furthermore, we can relate sublinear time algorithms for the two problems, and give a new such algorithm variant for the Lasso. We also study the regularization paths for both methods. This paper presents the ν-SVM and theν-SVR full regularization paths along with aleave-one-out inspired stopping criterion and an efficientimplementation. In the ν-SVR method, two parameters areprovided by the user: the regularization parameter Candνwhich settles the width of the ν-tube. Inthe classical ν-SVM method, parameter νisan lower bound on the number of support vectors in the solution.Based on the previous works of [1,2], extensions of regularizationpaths for SVM and SVR are proposed and permit to automaticallycompute the solution path by varying νor theregularization parameter. In this paper, regularization path algorithms were proposed as a novel approach to the model selection problem by exploring the path of possibly all solutions with respect to some regularization hyperparameter in an efficient way. This approach was later extended to a support vector regression (SVR) model called epsiv -SVR. However, the method requires that the error parameter epsiv be set a priori. This is only possible if the desired accuracy of the approximation can be specified in advance. In this paper, we analyze the solution space for epsiv-SVR and propose a new solution path algorithm, called epsiv-path algorithm, which traces the solution path with respect to the hyperparameter epsiv rather than lambda. Although both two solution path algorithms possess the desirable piecewise linearity property, our epsiv-path algorithm overcomes some limitations of the original lambda-path algorithm and has more advantages. It is thus more appealing for practical use. In the interest of deriving classifiers that are robust to outlier observations, we present integer programming formulations of Vapnik's support vector machine (SVM) with the ramp loss and hard margin loss. The ramp loss allows a maximum error of 2 for each training observation, while the hard margin loss calculates error by counting the number of training observations that are in the margin or misclassified outside of the margin. SVM with these loss functions is shown to be a consistent estimator when used with certain kernel functions. In computational studies with simulated and real-world data, SVM with the robust loss functions ignores outlier observations effectively, providing an advantage over SVM with the traditional hinge loss when using the linear kernel. Despite the fact that training SVM with the robust loss functions requires the solution of a quadratic mixed-integer program (QMIP) and is NP-hard, while traditional SVM requires only the solution of a continuous quadratic program (QP), we are able to find good solutions and prove optimality for instances with up to 500 observations. Solution methods are presented for the new formulations that improve computational performance over industry-standard integer programming solvers alone.