Regularization path for ν-support vector classification

Global Model Selection via Solution Paths for Robust Support Vector Machine

Robust support vector machine (RSVM) using ramp loss provides a better generalization performance than traditional support vector machine (SVM) using hinge loss. However, the good performance of RSVM heavily depends on the proper values of regularization parameter and ramp parameter. Traditional model selection technique with gird search has extremely high computational cost especially for fine-grained search. To address this challenging problem, in this paper, we first propose solution paths of RSVM (SPRSVM) based on the concave-convex procedure (CCCP) which can track the solutions of the non-convex RSVM with respect to regularization parameter and ramp parameter respectively. Specifically, we use incremental and decremental learning algorithms to deal with the Karush-Khun-Tucker violating samples in the process of tracking the solutions. Based on the solution paths of RSVM and the piecewise linearity of model function, we can compute the error paths of RSVM and find the values of regularization parameter and ramp parameter, respectively, which corresponds to the minimum cross validation error. We prove the finite convergence of SPRSVM and analyze the computational complexity of SPRSVM. Experimental results on a variety of benchmark datasets not only verify that our SPRSVM can globally search the regularization and ramp parameters respectively, but also show a huge reduction of computational time compared with the grid search approach.

Global Model Selection for Semi-Supervised Support Vector Machine via Solution Paths

Semi-supervised support vector machine (S3VM) is important because it can use plentiful unlabeled data to improve the generalization accuracy of traditional SVMs. In order to achieve good performance, it is necessary for S3VM to take some effective measures to select hyperparameters. However, model selection for semi-supervised models is still a key open problem. Existing methods for semi-supervised models to search for the optimal parameter values are usually computationally demanding, especially those ones with grid search. To address this challenging problem, in this article, we first propose solution paths of S3VM (SPS3VM), which can track the solutions of the nonconvex S3VM with respect to the hyperparameters. Specifically, we apply incremental and decremental learning methods to update the solution and let it satisfy the Karush-Kuhn-Tucker (KKT) conditions. Based on the SPS3VM and the piecewise linearity of model function, we can find the model with the minimum cross-validation (CV) error for the entire range of candidate hyperparameters by computing the error path of S3VM. Our SPS3VM is the first solution path algorithm for nonconvex optimization problem of semi-supervised learning models. We also provide the finite convergence analysis and computational complexity of SPS3VM. Experimental results on a variety of benchmark datasets not only verify that our SPS3VM can globally search the hyperparameters (regularization and ramp loss parameters) but also show a huge reduction of computational time while retaining similar or slightly better generalization performance compared with the grid search approach.

Kernel Path for Semisupervised Support Vector Machine

Semisupervised support vector machine (S3VM) is a powerful semisupervised learning model that can use large amounts of unlabeled data to train high-quality classification models. The choice of kernel parameters in the kernel function determines the mapping between the input space and the feature space and is crucial to the performance of the S3VM. Kernel path algorithms have been widely recognized as one of the most efficient tools to trace the solutions with respect to a kernel parameter. However, existing kernel path algorithms are limited to convex problems, while S3VM is nonconvex problem. To address this challenging problem, in this article, we first propose a kernel path algorithm of S3VM (KPS3VM), which can track the solutions of the nonconvex S3VM with respect to a kernel parameter. Specifically, we estimate the position of the breakpoint by monitoring the change of the sample sets. In addition, we also use an incremental and decremental learning algorithm to deal with the Karush-Khun-Tucker violating samples in the process of tracking the solutions. More importantly, we prove the finite convergence of our KPS3VM algorithm. Experimental results on various benchmark datasets not only validate the effectiveness of our KPS3VM algorithm but also show the advantage of choosing the optimal kernel parameters.

Kernel Error Path Algorithm

Tuning the values of kernel parameters plays a vital role in the performance of kernel methods. Kernel path algorithms have been proposed for several important learning algorithms, including support vector machine and kernelized Lasso, which can fit the piecewise nonlinear solutions of kernel methods with respect to the kernel parameter in a continuous space. Although the error path algorithms have been proposed to ensure that the model with the minimum cross validation (CV) error can be found, which is usually the ultimate goal of model selection, they are limited to piecewise linear solution paths. To address this problem, in this article, we extend the classic error path algorithm to the nonlinear kernel solution paths and propose a new kernel error path algorithm (KEP) that can find the global optimal kernel parameter with the minimum CV error. Specifically, we first prove that error functions of binary classification and regression problems are piecewise constant or smooth w.r.t. the kernel parameter. Then, we propose KEP for support vector machine and kernelized Lasso and prove that it guarantees to find the model with the minimum CV error within the whole range of kernel parameter values. Experimental results on various datasets show that our KEP can find the model with minimum CV error with less time consumption. Finally, it would have better generalization error on the test set, compared with grid search and random search.

Kernel Path for ν-Support Vector Classification

It is well known that the performance of a kernel method is highly dependent on the choice of kernel parameter. However, existing kernel path algorithms are limited to plain support vector machines (SVMs), which has one equality constraint. It is still an open question to provide a kernel path algorithm to ν -support vector classification ( ν -SVC) with more than one equality constraint. Compared with plain SVM, ν -SVC has the advantage of using a regularization parameter ν for controlling the number of support vectors and margin errors. To address this problem, in this article, we propose a kernel path algorithm (KP ν SVC) to trace the solutions of ν -SVC exactly with respect to the kernel parameter. Specifically, we first provide an equivalent formulation of ν -SVC with two equality constraints, which can avoid possible conflicts during tracing the solutions of ν -SVC. Based on this equivalent formulation of ν -SVC, we propose the KP ν SVC algorithm to trace the solutions with respect to the kernel parameter. However, KP ν SVC traces nonlinear solutions of kernel method rather than the errors of loss function, and it is still a challenge to provide the algorithm that guarantees to find the global optimal model. To address this challenging problem, we extend the classical error path algorithm to the nonlinear kernel solution paths and propose a new kernel error path (KEP) algorithm that ensures to find the global optimal kernel parameter by minimizing the cross validation error. We also provide the finite convergence analysis and computational complexity analysis to KP ν SVC and KEP. Extensive experimental results on a variety of benchmark datasets not only verify the effectiveness of KP ν SVC but also show the advantage of applying KEP to select the optimal kernel parameter.

Accelerating Sequential Minimal Optimization via Stochastic Subgradient Descent

Sequential minimal optimization (SMO) is one of the most popular methods for solving a variety of support vector machines (SVMs). The shrinking and caching techniques are commonly used to accelerate SMO. An interesting phenomenon of SMO is that most of the computational time is wasted on the first half of iterations for building a good solution closing to the optimal. However, as we all know, the stochastic subgradient descent (SSGD) method is extremely fast for building a good solution. In this paper, we propose a generalized framework of accelerating SMO through SSGD for a variety of SVMs of binary classification, regression, ordinal regression, and so on. We also provide a deep insight about why SSGD can accelerate SMO. Experimental results on a variety of datasets and learning applications confirm that our method can effectively speed up SMO.

A Solution Path Algorithm for General Parametric Quadratic Programming Problem

Parameter in learning problems (usually arising from the tradeoff between training error minimization and regularization) is often tuned by cross validation (CV). A solution path provides a compact representation of all optimal solutions, which can be used to determine the parameter with the global minimum CV error, without solving original optimization problems multiple times based on grid search. However, existing solution path algorithms do not provide a unified implementation to various learning problems. In this paper, we first introduce a general parametric quadratic programming (PQP) problem that can be instantiated to an extensive number of learning problems. Then, we propose a generalized solution path (GSP) for the general PQP problem. Particularly, we use the $QR$ decomposition to handle singularities in GSP. Finally, we analyze the finite convergence and the time complexity of GSP. Our experimental results on a variety of data sets not only confirm the identicality between GSP and several existing solution path algorithms but also show the superiority of our GSP over the existing solution path algorithms on both generalization and robustness. Finally, we provide a practical guild of using the GSP to solve two important learning problems, i.e., generalized error path and Ivanov SVM.

Cross Validation Through Two-Dimensional Solution Surface for Cost-Sensitive SVM

Model selection plays an important role in cost-sensitive SVM (CS-SVM). It has been proven that the global minimum cross validation (CV) error can be efficiently computed based on the solution path for one parameter learning problems. However, it is a challenge to obtain the global minimum CV error for CS-SVM based on one-dimensional solution path and traditional grid search, because CS-SVM is with two regularization parameters. In this paper, we propose a solution and error surfaces based CV approach (CV-SES). More specifically, we first compute a two-dimensional solution surface for CS-SVM based on a bi-parameter space partition algorithm, which can fit solutions of CS-SVM for all values of both regularization parameters. Then, we compute a two-dimensional validation error surface for each CV fold, which can fit validation errors of CS-SVM for all values of both regularization parameters. Finally, we obtain the CV error surface by superposing K validation error surfaces, which can find the global minimum CV error of CS-SVM. Experiments are conducted on seven datasets for cost sensitive learning and on four datasets for imbalanced learning. Experimental results not only show that our proposed CV-SES has a better generalization ability than CS-SVM with various hybrids between grid search and solution path methods, and than recent proposed cost-sensitive hinge loss SVM with three-dimensional grid search, but also show that CV-SES uses less running time.

A Robust Regularization Path Algorithm for $\nu $ -Support Vector Classification

The ν -support vector classification has the advantage of using a regularization parameter ν to control the number of support vectors and margin errors. Recently, a regularization path algorithm for ν -support vector classification ( ν -SvcPath) suffers exceptions and singularities in some special cases. In this brief, we first present a new equivalent dual formulation for ν -SVC and, then, propose a robust ν -SvcPath, based on lower upper decomposition with partial pivoting. Theoretical analysis and experimental results verify that our proposed robust regularization path algorithm can avoid the exceptions completely, handle the singularities in the key matrix, and fit the entire solution path in a finite number of steps. Experimental results also show that our proposed algorithm fits the entire solution path with fewer steps and less running time than original one does.

Feasibility and finite convergence analysis for accurate on-line ν-support vector machine

The ν-support vector machine ( ν-SVM) for classification has the advantage of using a parameter ν on controlling the number of support vectors and margin errors. Recently, an interesting accurate on-line algorithm accurate on-line ν-SVM algorithm (AONSVM) is proposed for training ν-SVM. AONSVM can be viewed as a special case of parametric quadratic programming techniques. It is demonstrated that AONSVM avoids the infeasible updating path as far as possible, and successfully converges to the optimal solution based on experimental analysis. However, because of the differences between AONSVM and classical parametric quadratic programming techniques, there is no theoretical justification for these conclusions. In this paper, we prove the feasibility and finite convergence of AONSVM under two assumptions. The main results of feasibility analysis include: 1) the inverses of the two key matrices in AONSVM always exist; 2) the rules for updating the two key inverse matrices are reliable; 3) the variable ζ can control the adjustment of the sum of all the weights efficiently; and 4) a sample cannot migrate back and forth in successive adjustment steps among the set of margin support vectors, the set of error support vectors, and the set of the remaining vectors. Moreover, the analyses of AONSVM also provide the proofs of the feasibility and finite convergence for accurate on-line C-SVM learning directly.