A Study on SMO-Type Decomposition Methods for Support Vector Machines
IEEE Transactions on Neural NetworksPublished 1 July 2006
Pai-Hsuen Chen, Rong-En Fan, Chih‐Jen Lin
Citations345
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
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.
Abstract
Decomposition methods are currently one of the major methods for training support vector machines. They vary mainly according to different working set selections. Existing implementations and analysis usually consider some specific selection rules. This paper studies sequential minimal optimization type decomposition methods under a general and flexible way of choosing the two-element working set. The main results include: 1) a simple asymptotic convergence proof, 2) a general explanation of the shrinking and caching techniques, and 3) the linear convergence of the methods. Extensions to some support vector machine variants are also discussed.
Keywords
Computer Science
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
40,463 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.
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
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.
Neural ComputationEstimating the Support of a High-Dimensional Distribution
5,946 Citations2001Bernhard Schölkopf, John Platt +3 more
The algorithm is a natural extension of the support vector algorithm to the case of unlabeled data by carrying out sequential optimization over pairs of input patterns and providing a theoretical analysis of the statistical performance of the algorithm.
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.
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.
Neural ComputationAsymptotic Behaviors of Support Vector Machines with Gaussian Kernel
1,616 Citations2003S. Sathiya Keerthi, Chih‐Jen Lin
The behavior of the SVM classifier when these hyper parameters take very small or very large values is analyzed, which helps in understanding thehyperparameter space that leads to an efficient heuristic method of searching for hyperparameter values with small generalization errors.
Journal of Machine Learning ResearchWorking Set Selection Using Second Order Information for Training Support Vector Machines
1,413 Citations2005Rong-En Fan, Pai-Hsuen Chen +1 more
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.
Interpolation of Scattered Data: Distance Matrices and Conditionally Positive Definite Functions
1,307 Citations1984Charles A. Micchelli
Constructive ApproximationInterpolation of scattered data: Distance matrices and conditionally positive definite functions
1,213 Citations1986Charles A. Micchelli
A Study on Sigmoid Kernels for SVM and the Training of non-PSD Kernels by SMO-type Methods
591 Citations2005Hsuan-Tien Lin
This paper discusses non-PSD kernels through the viewpoint of separability, and shows that the sigmoid kernel matrix is conditionally positive definite (CPD) in certain parameters and thus are valid kernels there.
Neural ComputationTraining <i>v</i>-Support Vector Classifiers: Theory and Algorithms
503 Citations2001Chih-Chung Chang, Chih‐Jen Lin
Machine LearningConvergence of a Generalized SMO Algorithm for SVM Classifier Design
306 Citations2002S. Sathiya Keerthi, Éric Gilbert
Convergence of a generalized version of the modified SMO algorithms given by Keerthi et al. for SVM classifier design is proved and the results are extended to modifiedSMO algorithms for solving ν-SVM classifiers problems.
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 NetworksThe analysis of decomposition methods for support vector machines
163 Citations2000Chih‐Chung Chang, Chih‐Wei Hsu +1 more
This paper connects this method to projected gradient methods and provides theoretical proofs for a version of decomposition methods and shows that this convergence proof is valid for general decomposition methods if their working set selection meets a simple requirement.
IEEE Transactions on Neural NetworksAsymptotic convergence of an SMO algorithm without any assumptions
138 Citations2002Chih‐Jen Lin
IEEE Transactions on Neural NetworksA formal analysis of stopping criteria of decomposition methods for support vector machines
85 Citations2002Chih‐Jen Lin
A result shows that, in final iterations of the decomposition method, only a particular set of variables are still being modified, which supports the use of the shrinking and caching techniques in some existing implementations.
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.
Neural Information Processing SystemsA geometric interpretation of ν-SVM classifiers
75 Citations1999David J. Crisp, Christopher J. C. Burges
It is shown that the recently proposed variant of the Support Vector machine (SVM) algorithm, known as ν-SVM, can be interpreted as a maximal separation between subsets of the convex hulls of the data, which are called soft convex Hulls.
Lecture notes in computer sciencePositive Definite Rational Kernels
37 Citations2003Corinna Cortes, Patrick Haffner +1 more
It is shown that under some conditions these kernels are closed under sum, product, or Kleene-closure and a general method for constructing a PDS rational kernel from an arbitrary transducer defined on some non-idempotent semirings is given.
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.
Computational Optimization and ApplicationsA convergent decomposition algorithm for support vector machines
30 Citations2007Stefano Lucidi, Laura Palagi +2 more
The new rule for sequentially selecting the subproblems appears to be suited to tackle large scale problems, while the introduction of the proximal point term allows us to ensure the global convergence of the algorithm for the general case of nonconvex objective function.
Lecture notes in computer scienceA General Convergence Theorem for the Decomposition Method
29 Citations2004Niko List, Hans Ulrich Simon
This paper presents a variant of the decomposition method that basically converges for any convex quadratic optimization problem provided that the policy for working set selection satisfies three abstract conditions.