On the convergence of the decomposition method for support vector machines
IEEE Transactions on Neural NetworksPublished 1 January 2001
Chih‐Jen Lin
Citations249
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 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.
Abstract
The decomposition method is currently one of the major methods for solving support vector machines (SVM). Its convergence properties have not been fully understood. The general asymptotic convergence was first proposed by Chang et al. However, their working set selection does not coincide with existing implementation. A later breakthrough by Keerthi and Gilbert (2000, 2002) proved the convergence finite termination for practical cases while the size of the working set is restricted to two. In this paper, we prove the asymptotic convergence of the algorithm used by the software SVM(light) and other later implementation. The size of the working set can be any even number. Extensions to other SVM formulations are also discussed.
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
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.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Statistics and ComputingA tutorial on support vector regression
13,005 Citations2004Alex Smola, Bernhard Schölkopf
This tutorial gives an overview of the basic ideas underlying Support Vector (SV) machines for function estimation, and includes a summary of currently used algorithms for training SV machines, covering both the quadratic programming part and advanced methods for dealing with large datasets.
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.
Computers & Operations ResearchNonlinear programming: theory and algorithms
5,829 Citations1993
The book is a solid reference for professionals as well as a useful text for students in the fields of operations research, management science, industrial engineering, applied mathematics, and also in engineering disciplines that deal with analytical optimization techniques.
International Conference on Neural Information ProcessingAdvances in kernel methods: support vector learning
5,815 Citations1999Bernhard Schölkopf, Christopher J. C. Burges +1 more
Support vector machines for dynamic reconstruction of a chaotic system, Klaus-Robert Muller et al pairwise classification and support vector machines, Ulrich Kressel.
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.
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
IEEE Transactions on Neural NetworksImprovements to the SMO algorithm for SVM regression
861 Citations2000Shirish Shevade, S. Sathiya Keerthi +2 more
Using clues from the KKT conditions for the dual problem, two threshold parameters are employed to derive modifications of SMO for regression that perform significantly faster than the original SMO on the datasets tried.
Methods of Feasible Directions
541 Citations2005Mokhtar S. Bazaraa, Hanif D. Sherali +1 more
Neural ComputationTraining <i>v</i>-Support Vector Classifiers: Theory and Algorithms
503 Citations2001Chih-Chung Chang, Chih‐Jen Lin
IEEE Transactions on Neural NetworksSuccessive overrelaxation for support vector machines
437 Citations1999O. L. Mangasarian, David R. Musicant
Successive overrelaxation for symmetric linear complementarity problems and quadratic programs is used to train a support vector machine (SVM) for discriminating between the elements of two massive datasets, each with millions of points.
Applied Physics Letters10.1162/15324430152733142
389 Citations2000Ronan Collobert, Samy Bengio
A decomposition algorithm, SVMTorch, similar to SVM-Light proposed by Joachims (1999) for classification problems, but adapted to regression problems is proposed, which can now efficiently solve large-scale regression problems.
Mathematical ProgrammingOn search directions for minimization algorithms
319 Citations1973M. J. D. Powell
The relevance of differentiable functions of three variables, having the property that if they are treated by the minimization algorithm that searches along the coordinate directions in sequence, then the search path tends to a closed loop, is discussed.
Machine LearningEfficient SVM Regression Training with SMO
317 Citations2002Gary William Flake, Steve Lawrence
This work generalizes SMO so that it can handle regression problems, and addresses problems with several modifications that enable caching to be effectively used with SMO.
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.
Machine LearningA Simple Decomposition Method for Support Vector Machines
300 Citations2002Chih‐Wei Hsu, Chih‐Jen Lin
This paper through the design of decomposition methods for bound-constrained SVM formulations it is demonstrated that the working set selection is not a trivial task and a simple selection is proposed which leads to faster convergences for difficult cases.
The Kernel-Adatron Algorithm: A Fast and Simple Learning Procedure for Support Vector Machines
246 Citations1998Thilo-Thomas Frieß, Nello Cristianini +1 more
This paper proposes an adaptation of the Adatron algorithm for clas-siication with kernels in high dimensional spaces that can find a solution very rapidly with an exponentially fast rate of convergence towards the optimal solution.
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.
ePrints Soton (University of Southampton)Support Vector Machine Reference Manual
143 Citations1998Craig Saunders, Weston Stitson Mo +2 more
The Support Vector Machine (SVM) program allows a user to carry out pattern recognition and regression estimation, using support vector techniques on some given data.
IBM Journal of Research and DevelopmentOn the Convergence of Gradient Methods under Constraint
58 Citations1972Philip Wolfe
Machine LearningFeasible Direction Decomposition Algorithms for Training Support Vector Machines
53 Citations2002Pavel Laskov
It is proved that the two algorithms are equivalent for the pattern recognition SVM, and the feasible direction interpretation of the maximal inconsistency algorithm is given for the regression SVM.
An Improved Decomposition Algorithm for Regression Support Vector Machines
27 Citations1999Pavel Laskov
A new decomposition algorithm for training regression Support Vector Machines (SVM) that builds on the basic principles of decomposition proposed by Osuna et.