An improved training algorithm for support vector machines

E. Osuna; Robert M. Freund; Federico Girosi

doi:10.1109/nnsp.1997.622408

Abstract

We investigate the problem of training a support vector machine (SVM) on a very large database in the case in which the number of support vectors is also very large. Training a SVM is equivalent to solving a linearly constrained quadratic programming (QP) problem in a number of variables equal to the number of data points. This optimization problem is known to be challenging when the number of data points exceeds few thousands. In previous work done by us as well as by other researchers, the strategy used to solve the large scale QP problem takes advantage of the fact that the expected number of support vectors is small (<3,000). Therefore, the existing algorithms cannot deal with more than a few thousand support vectors. In this paper we present a decomposition algorithm that is guaranteed to solve the QP problem and that does not make assumptions on the expected number of support vectors. In order to present the feasibility of our approach we consider a foreign exchange rate time series database with 110,000 data points that generates 100,000 support vectors.

Keywords

Computer scienceTraining (meteorology)Support vector machineArtificial intelligenceAlgorithmMachine learning

Related Publications

Fast Training of Support Vector Machines Using Sequential Minimal Optimization

John Platt

This chapter describes a new algorithm for training Support Vector Machines: Sequential Minimal Optimization, or SMO. Training a Support Vector Machine (SVM) requires the soluti...

1998 The MIT Press eBooks 5457 citations

Making Large-Scale SVM Learning Practical

Thorsten Joachims

Training a support vector machine SVM leads to a quadratic optimization problem with bound constraints and one linear equality constraint. Despite the fact that this type of pro...

2006 Technical reports 4316 citations

Pegasos

Shai Shalev‐Shwartz , Yoram Singer , Nathan Srebro

We describe and analyze a simple and effective iterative algorithm for solving the optimization problem cast by Support Vector Machines (SVM). Our method alternates between stoc...

2007 980 citations

Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms

N. Srinivas , Kalyanmoy Deb

In trying to solve multiobjective optimization problems, many traditional methods scalarize the objective vector into a single objective. In those cases, the obtained solution i...

1994 Evolutionary Computation 6721 citations

Kernel Logistic Regression and the Import Vector Machine

Ji Zhu , Trevor Hastie

The support vector machine (SVM) is known for its good performance in two-class classification, but its extension to multiclass classification is still an ongoing research issue...

2001 136 citations

Publication Info

Year: 2002
Type: article
Citations: 1065
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

An improved training algorithm for support vector machines

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1065

OpenAlex

Cite This

APA Style

                            
                                    E. Osuna, 
                                
                                    Robert M. Freund, 
                                
                                    Federico Girosi
                                
                            (2002). 
                            An improved training algorithm for support vector machines. 
                            
                            .
                            https://doi.org/10.1109/nnsp.1997.622408

Identifiers

DOI: 10.1109/nnsp.1997.622408