Working Set Selection Using Second Order Information for Training Support Vector Machines
Journal of Machine Learning ResearchPublished 1 December 2005
Rong-En Fan, Pai-Hsuen Chen, Chih‐Jen Lin
Citations1,413
SJR quartileQ1
SJR score2.02
SNIP3.07
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new technique for working set selection in SMO-type decomposition methods that uses second order information to achieve fast convergence andoretical properties such as linear convergence are established.
Abstract
Working set selection is an important step in decomposition methods for training support vector machines (SVMs). This paper develops a new technique for working set selection in SMO-type decomposition methods. It uses second order information to achieve fast convergence. Theoretical properties such as linear convergence are established. Experiments demonstrate that the proposed method is faster than existing selection methods using first order information.
Keywords
Computer ScienceEngineering
ACM Transactions on Intelligent Systems and TechnologyLIBSVM
41,340 Citations2011Chih-Chung Chang, Chih‐Jen Lin
Issues such as solving SVM optimization problems theoretical convergence multiclass classification probability estimates and parameter selection are discussed in detail.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization
5,462 Citations1998John Platt
Technical reportsMaking Large-Scale SVM Learning Practical
4,317 Citations2006Thorsten Joachims
This chapter presents algorithmic and computational results developed for SVM light V 2.0, which make large-scale SVM training more practical and give guidelines for the application of SVMs to large domains.
Neural ComputationNew Support Vector Algorithms
2,816 Citations2000Bernhard Schölkopf, Alex Smola +2 more
A new class of support vector algorithms for regression and classification that eliminates one of the other free parameters of the algorithm: the accuracy parameter in the regression case, and the regularization constant C in the classification case.
Training support vector machines: an application to face detection
2,496 Citations2002E. Osuna, Robert M. Freund +1 more
A decomposition algorithm that guarantees global optimality, and can be used to train SVM's over very large data sets is presented, and the feasibility of the approach on a face detection problem that involves a data set of 50,000 data points is demonstrated.
TechnometricsMachine Learning, Neural and Statistical Classification
2,188 Citations1995Bill Fulkerson, D. Michie +2 more
Neural ComputationImprovements to Platt's SMO Algorithm for SVM Classifier Design
1,817 Citations2001S. Sathiya Keerthi, Shirish Shevade +2 more
Using clues from the KKT conditions for the dual problem, two threshold parameters are employed to derive modifications of SMO that perform significantly faster than the original SMO on all benchmark data sets tried.
IEEE Transactions on Neural NetworksA Study on SMO-Type Decomposition Methods for Support Vector Machines
345 Citations2006Pai-Hsuen Chen, Rong-En Fan +1 more
The main results include a simple asymptotic convergence proof, a general explanation of the shrinking and caching techniques, and the linear convergence of the methods.
IEEE Transactions on Neural NetworksOn the convergence of the decomposition method for support vector machines
249 Citations2001Chih‐Jen Lin
The asymptotic convergence of the algorithm used by the software SVM(light) and other later implementation is proved and the size of the working set can be any even number.
IEEE Transactions on Neural NetworksAsymptotic convergence of an SMO algorithm without any assumptions
138 Citations2002Chih‐Jen Lin
Building projectable classifiers of arbitrary complexity
97 Citations1996Tin Kam Ho, E. M. Kleinberg
This work presents a method that constructs a classifier up to arbitrary complexity while presenting generalization accuracy, and reveals that the conflict is resolvable by building classifiers based on projectable elements, which are weak discriminators that perform equally well for both training and testing data.
Machine LearningPolynomial-Time Decomposition Algorithms for Support Vector Machines
79 Citations2003Don Hush, Clint Scovel
This paper provides a model algorithm for decomposition, and shows that when the slack multiplier C satisfies √1/2 ≤ C ≤ mL, then it takes no more than 4LC2m4/∈ iterations to drive the criterion to within ∈ of its optimum.
Optimization methods & softwareOn the convergence of a modified version of SVM<i><sup>light</sup></i>algorithm
37 Citations2005Laura Palagi, Marco Sciandrone
This work proposes a decomposition method on the basis of a proximal point modification of the subproblem and the basis of a working set selection rule that includes, as a particular case, the one used by the SVM light algorithm.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Automatic recognition of USGS land use/cover categories using statistical and neural network classifiers</title>
18 Citations1993Robert R. Bailey, Elaine J. Pettit +3 more
Part of an end-to-end system being developed for the automatic recognition of general land use/cover categories from digitized aerial photography is presented, and a new, fast method of training the multilayer perceptron is described.
Lecture notes in computer scienceOn the Complexity of Working Set Selection
9 Citations2004Hans Ulrich Simon