Training linear SVMs in linear time
Published 20 August 2006
Thorsten Joachims
Citations1,947
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 Cutting Plane Algorithm for training linear SVMs that provably has training time 0(s,n) for classification problems and o(sn log (n)) for ordinal regression problems and several orders of magnitude faster than decomposition methods like svm light for large datasets.
Abstract
Linear Support Vector Machines (SVMs) have become one of the most prominent machine learning techniques for high-dimensional sparse data commonly encountered in applications like text classification, word-sense disambiguation, and drug design. These applications involve a large number of examples n as well as a large number of features N, while each example has only s
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.
Lecture notes in computer scienceText categorization with Support Vector Machines: Learning with many relevant features
7,925 Citations1998Thorsten Joachims
SVMs achieve substantial improvements over the currently best performing methods and behave robustly over a variety of di-erent learning tasks, eliminating the need for manual parameter tuning.
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.
Optimizing search engines using clickthrough data
3,898 Citations2002Thorsten Joachims
The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking.
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.
Journal of Machine Learning ResearchRCV1: A New Benchmark Collection for Text Categorization Research
2,600 Citations2004David Lewis, Yiming Yang +2 more
This work describes the coding policy and quality control procedures used in producing the RCV1 data, the intended semantics of the hierarchical category taxonomies, and the corrections necessary to remove errorful data.
MPG.PuRe (Max Planck Society)Large Margin Methods for Structured and Interdependent Output Variables
1,952 Citations2005Ioannis Tsochantaridis, Thorsten Joachims +2 more
This paper proposes to appropriately generalize the well-known notion of a separation margin and derive a corresponding maximum-margin formulation and presents a cutting plane algorithm that solves the optimization problem in polynomial time for a large class of problems.
Inductive learning algorithms and representations for text categorization
1,465 Citations1998Susan Dumais, John Platt +2 more
A comparison of the effectiveness of five different automatic learning algorithms for text categorization in terms of learning speed, realtime classification speed, and classification accuracy is compared.
Core Vector Machines: Fast SVM Training on Very Large Data Sets
951 Citations2005Ivor W. Tsang, James T. Kwok +1 more
This paper shows that many kernel methods can be equivalently formulated as minimum enclosing ball (MEB) problems in computational geometry and obtains provably approximately optimal solutions with the idea of core sets, and proposes the proposed Core Vector Machine (CVM) algorithm, which can be used with nonlinear kernels and has a time complexity that is linear in m.
Proximal support vector machine classifiers
844 Citations2001Glenn Fung, O. L. Mangasarian
Computational results on publicly available datasets indicate that the proposed proximal SVM classifier has comparable test set correctness to that of standard S VM classifiers, but with considerably faster computational time that can be an order of magnitude faster.
A support vector method for multivariate performance measures
800 Citations2005Thorsten Joachims
An algorithm with which such multivariate SVMs can be trained in polynomial time for large classes of potentially non-linear performance measures, in particular ROCArea and all measures that can be computed from the contingency table are given.
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.
Journal of Machine Learning ResearchA Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs
272 Citations2005S. Sathiya Keerthi, Dennis DeCoste
A fast method for solving linear SVMs with L2 loss function that is suited for large scale data mining tasks such as text classification is developed by modifying the finite Newton method of Mangasarian in several ways.
SIAM Journal on OptimizationInterior-Point Methods for Massive Support Vector Machines
190 Citations2002Michael C. Ferris, Todd Munson
This work investigates the use of interior-point methods for solving quadratic programming problems with a small number of linear constraints, where the quadratics term consists of a low-rank update to a positive semidefinite matrix.
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.
ACM SIGKDD Explorations NewsletterKDD-Cup 2004
51 Citations2004Rich Caruana, Thorsten Joachims +1 more
What fraction of the participants found good solutions, how well participants were able to optimize to different performance measures, how homogeneous their submitted predictions are, and if the best submissions represent the maximal performances that could reasonably be achieved are studied.
Lecture notes in computational science and engineeringLearning to Align Sequences: A Maximum-Margin Approach
44 Citations2006Thorsten Joachims, Tamara Galor +1 more
A discriminative method for learning the parameters of linear sequence alignment models from training examples that finds an arbitrarily close approximation after considering only a subset of the constraints that is linear in the number of training examples and polynomial in the length of the sequences.