Title :
An improved training algorithm for support vector machines
Author :
Osuna, Edgar ; Freund, Robert ; Girosi, Federico
Author_Institution :
CBCL, MIT, Cambridge, MA, USA
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 :
financial data processing; learning systems; pattern classification; quadratic programming; time series; very large databases; decomposition algorithm; foreign exchange rate; learning systems; optimization; pattern classification; quadratic programming; support vector machine; time series; training algorithm; very large database; Classification algorithms; Exchange rates; Large-scale systems; Minimization methods; Neural networks; Pattern classification; Polynomials; Quadratic programming; Support vector machine classification; Support vector machines;
Conference_Titel :
Neural Networks for Signal Processing [1997] VII. Proceedings of the 1997 IEEE Workshop
Conference_Location :
Amelia Island, FL
Print_ISBN :
0-7803-4256-9
DOI :
10.1109/NNSP.1997.622408
