@mastersthesis {47,
	title = {Practical Implementations of the Active Set Method for Support Vector Machine Training with Semi-definite Kernels},
	volume = {Electrical Engineering},
	year = {2014},
	month = {05/2014},
	pages = {209},
	school = {University of Central Florida},
	type = {phd},
	address = {Orlando, Florida},
	abstract = {<p>The Support Vector Machine (SVM) is a popular binary classification model due to its superior generalization performance, relative ease-of-use, and applicability of kernel methods. SVM training entails solving an associated quadratic programming (QP) that presents significant challenges in terms of speed and memory constraints for very large datasets; therefore, research on numerical optimization techniques tailored to SVM training is vast. Slow training times are especially of concern when one considers that re-training is often necessary at several values of the model{\textquoteright}s regularization parameter, C, as well as associated kernel parameters. The active set method is suitable for solving SVM problem and is in general ideal when the Hessian is dense and the solution is sparse-the case for the l1-loss SVM formulation. There has recently been renewed interest in the active set method as a technique for exploring the entire SVM regularization path, which has been shown to solve the SVM solution at all points along the regularization path (all values of C) in not much more time than it takes, on average, to perform training at a single value of C with traditional methods. Unfortunately, the majority of active set implementations used for SVM training require positive definite kernels, and those implementations that do allow semi-definite kernels tend to be complex and can exhibit instability and, worse, lack of convergence. This severely limits applicability since it precludes the use of the linear kernel, can be an issue when duplicate data points exist, and doesn{\textquoteright}t allow use of low-rank kernel approximations to improve tractability for large datasets. The difficulty, in the case of a semi-definite kernel, arises when a particular active set results in a singular KKT matrix (or the equality-constrained problem formed using the active set is semi-definite). Typically this is handled by explicitly detecting the rank of the KKT matrix. Unfortunately, this adds significant complexity to the implementation; and, if care is not taken, numerical instability, or worse, failure to converge can result. This research shows that the singular KKT system can be avoided altogether with simple modifications to the active set method. The result is a practical, easy to implement active set method that does not need to explicitly detect the rank of the KKT matrix nor modify factorization or solution methods based upon the rank. Methods are given for both conventional SVM training as well as for computing the regularization path that are simple and numerically stable. First, an efficient revised simplex method is efficiently implemented for SVM training (SVM-RSQP) with semi-definite kernels and shown to out-perform competing active set implementations for SVM training in terms of training time as well as shown to perform on-par with state-of-the-art SVM training algorithms such as SMO and SVMLight. Next, a new regularization path-following algorithm for semi-definite kernels (Simple SVMPath) is shown to be orders of magnitude faster, more accurate, and significantly less complex than competing methods and does not require the use of external solvers. Theoretical analysis reveals new insights into the nature of the path-following algorithms. Finally, a method is given for computing the approximate regularization path and approximate kernel path using the warm-start capability of the proposed revised simplex method (SVM-RSQP) and shown to provide significant, orders of magnitude, speed-ups relative to the traditional {\textquotedblleft}grid search{\textquotedblright} where re-training is performed at each parameter value. Surprisingly, it also shown that even when the solution for the entire path is not desired, computing the approximate path can be seen as a speed-up mechanism for obtaining the solution at a single value. New insights are given concerning the limiting behaviors of the regularization and kernel path as well as the use of low-rank kernel approximations.</p>
},
	keywords = {active set method, approximate kernel path, approximate regularization path, regularization path following method, revised simplex, support vector machine},
	url = {http://purl.fcla.edu/fcla/etd/CFE0005251},
	author = {Christopher G. Sentelle}
}
@article {38,
	title = {Efficient Revised Simplex Method for SVM Training},
	journal = {Neural Networks, IEEE Transactions on},
	volume = {22},
	year = {2011},
	month = {Oct.},
	pages = {1650-1661},
	abstract = {<p>Existing active set methods reported in the literature for support vector machine (SVM) training must contend with singularities when solving for the search direction. When a singularity is encountered, an infinite descent direction can be carefully chosen that avoids cycling and allows the algorithm to converge. However, the algorithm implementation is likely to be more complex and less computationally efficient than would otherwise be required for an algorithm that does not have to contend with the singularities. We show that the revised simplex method introduced by Rusin provides a guarantee of nonsingularity when solving for the search direction. This method provides for a simpler and more computationally efficient implementation, as it avoids the need to test for rank degeneracies and also the need to modify factorizations or solution methods based upon those rank degeneracies. In our approach, we take advantage of the guarantee of nonsingularity by implementing an efficient method for solving the search direction and show that our algorithm is competitive with SVM-QP and also that it is a particularly effective when the fraction of nonbound support vectors is large. In addition, we show competitive performance of the proposed algorithm against two popular SVM training algorithms, SVMLight and LIBSVM.</p>
},
	keywords = {active set method, learning (artificial intelligence), LIBSVM algorithm, quadratic programming, rank degeneracy, set theory, simplex method, support vector machine, Support vector machines, SVM training, SVMLight algorithm},
	issn = {1045-9227},
	doi = {10.1109/TNN.2011.2165081},
	author = {Christopher G. Sentelle and Georgios C. Anagnostopoulos and Michael Georgiopoulos}
}
