RSVM: Reduced Support Vector Machines

By Yuh-Jye Lee, Olvi L. Mangasarian. SDM, 2001

741 citations recorded by the source corpus.

Abstract An algorithm is proposed which generates a nonlinear kernel-based separating surface that requires as little as 1% of a large dataset for its explicit evaluation. To generate this nonlinear surface, the entire dataset is used as a constraint in an optimization problem with very few variables corresponding to the 1% of the data kept. The remainder of the data can be thrown away after solving the optimization problem. This is achieved by making use of a rectangular m×m kernel K(A, Ā) that greatly reduces the size of the quadratic program to be solved and simplifies the characterization of the nonlinear separating surface. Here, the m rows of A represent the original m data points while the m rows of Ā represent a greatly reduced m data points. Computational results indicate that test set correctness for the reduced support vector machine (RSVM), with a nonlinear separating surface that depends on a small randomly selected portion of the dataset, is better than that of a conventional support vector machine (SVM) with a nonlinear surface that explicitly depends on the entire dataset, and much better than a conventional SVM using a small random sample of the data. Computational times, as well as memory usage, are much smaller for RSVM than that of a conventional SVM using the entire dataset.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Media Technology

View Paper: https://www.semanticscholar.org/paper/de4d36bc28e13917297d619f585cd8f7860848f0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

Classifying large data sets using SVMs with hierarchical clusters (2003, methodology): “Anot her method using random sampling [17] was developed for nonline ar SVMs using the random sampling technique in the kernel trick .”
Breaking the curse of kernelization: budgeted stochastic gradient descent for large-scale SVM training (2012, background): “Another line of work (Lee and Mangasarian, 2001; Wu et al., 2005; Dekel and Singer, 2006) is to directly train a reduced classifier from scratch by reformulating the optimization problem.”
A Feature Selection Newton Method for Support Vector Machine Classification (2004, methodology): “Because the nonlinear kernel matrix is square and since NLPSVM, NSVM and LSVM perform better on rectangular matrices, we also used a rectangular kernel formulation as described in the Reduced SVM (RSVM) [10].”
Discrete support vector decision trees via tabu search (2004, methodology): “A similar behavior was noticed by some authors (Lee and Mangasarian, 2001) in relation to other classi0ers, where reduced training sets were employed to improve accuracy and learning speed.”
Proximal support vector machine classifiers (2001, methodology): “In order to address this problem, we used a rectangular kernel with A E R 215xs12a instead, as described in [ 17 ].”
Fast Bundle Algorithm for Multiple-Instance Learning (2012, methodology): “This corresponds to training in a subspace of the kernel space defined by the training set and helps control overfitting [30].”
Developing optimal non-linear scoring function for protein design (2004, methodology): “In addition, new techniques such as finite Newton method for reduced support vector machine has recently shown great promise in further reducing the number of support vectors, where a reduction ratio of 1% has been reported ( Lee and Mangasarian, 2001; Fung and Mangasarian, 2002).”
Building Support Vector Machines with Reduced Classifier Complexity (2006, methodology): “This is almost the same as the RSVM method (Lee and Mangasarian, 2001; Lin and Lin, 2003), the only difference being the regularizer (βJ KJ,JβJ in (4) versus ‖βJ‖(2) in RSVM).”
Core Vector Machines: Fast SVM Training on Very Large Data Sets (2005, methodology): “RSVM, on the other hand, as to keep a rectangular kernel matrix of size ¯m×m (m̄ being the number of random samples used), and cannot be run on our machine whenm exceeds 10K. Similarly, the SimpleSVM has to store the kernel matrix of the active set, and runs into storage problem whenm xceeds 30K. Re”
Large-scale kernel machines (2007, background): “There are many strategies for specific problems which try to reduce this computational complexity by searching for a sparse representation of the data (Williams and Seeger, 2001; Smola and Bartlett, 2001; Fine and Scheinberg, 2001; Lee and Mangasarian, 2001; Lawrence et al., 2003; Csato and Opper, 2”
Training and Testing Low-degree Polynomial Data Mappings via Linear SVM (2010, methodology): “They propose methods to manipulate the kernels (e.g., Lee and Mangasarian, 2001; Keerthi et al., 2006).”
Lagrangian Support Vector Machines (2001, result): “However, this modiﬁcation to the SVM does not seem to have a detrimental eﬀect, as can be seen in the experimental results of Section 5.”
Multicategory Proximal Support Vector Machine Classifiers (2005, methodology): “For the Vehicle dataset, RSVM [20] with an 85% kernel reduction was used for the nonlinear MPSVM classifier here in order to obtain a smaller rectangular kernel problem that would fit in memory (2310 × 350 instead of 2310×2310).”
Surface EMG in advanced hand prosthetics (2008, background): “…the number of support vectors have been tried, e.g. in Orabona et al. (2007), in which sparseness is achieved without losing any accuracy, or, e.g. Lee and Mangasarian (2001); Keerthi et al. (2006) where a subset of the support vectors is heuristically selected and fewer support vectors are…”
Extreme Learning Machine for Regression and Multiclass Classification (2012, methodology): “IN THE PAST two decades, due to their surprising classification capability, support vector machine (SVM) [1] and its variants [2]–[4] have been extensively used in classification”