RSVM: Reduced Support Vector Machines
Open accessAbstract
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 × 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 rows of Ā represent a greatly reduced 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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
RSVM and RSA use a random algorithm, which leads to uncertain results.
“For example, Reduced SVM (RSVM) [8] and Random Sampling Algorithm (RSA) [12] use a random algorithm which leads to uncertain results, while KMSVM [13,14] using clustering technology performs poorly when the classes are overlapped.”
From An efficient instance selection algorithm to reconstruct training set for support vector machine (2017) · cites this paper as [8]
The Conclusion says RSVM uses a randomly selected subset, but explicitly states that the choice of random data submatrix does not affect test-set correctness. Section 3 likewise reports a standard deviation of 0.002 or less across 50 random choices. This contradicts the uncertainty attributed to RSVM; the RSA and KMSVM portions of the sentence are attached to other citations. (LLM, conf=0.89)
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredRandom sampling algorithms' performance is uncertain because some support vectors may not be included in the randomly selected subset.
“Although their experiments show that these methods are faster than the original SVM, the performance of these randomly sampling algorithms is uncertain since some support vectors may not be included in the randomly selected subset.”
From An efficient instance selection algorithm to reconstruct training set for support vector machine (2017) · cites this paper as [8]
Section 3 and the Conclusion report that a conventional SVM trained on a random subset has test-set results that vary with the subset chosen. They do not attribute that variability to omitted support vectors. The Conclusion also says that random-subset choice does not affect RSVM test-set correctness, so the claim cannot be extended to the paper’s random-sampling method generally. Page numbers are unavailable in our copy. (LLM, conf=0.86)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 19
- P. S. Bradley and O. L. Mangasarian, Feature selection via concave minimization and support vector machines, in Machine Learning Proceedings of the Fifteenth International Conference(ICML '98), J. Shavlik, editor, Morgan Kaufmann, San Francisco, California, 1998, pp. 82-90.
- P. S. Bradley and O. L. Mangasarian, Massive data discrimination via linear support vector machines, Optimization Methods and Software, 13 (2000), pp. 1-10.
- C. J. C. Burges, A tutorial on support vector machines for pattern recogni- tion, Data Mining and Knowledge Discovery, 2(2) (1998), pp. 121-167.
- Chunhui Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems, Mathematical Programming 71(1) (1995), pp. 51-69.
- A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, 5(2) (1996), pp. 97- 138.
- V. Cherkassky and F. Mulier, Learning from Data -Concepts, Theory and Methods, John Wiley & Sons, New York, 1998.
- P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization, Academic Press, London, 1981.
- T. K. Ho and E. M. Kleinberg, Building projectable classifiers of ar- bitrary complexity, in Proceedings of the 13th International Conference on Pattern Recognition, Vienna, Austria, 1996, pp. 880-885. http://cm.bell- labs.com/who/tkh/pubs.html. Checker dataset at: ftp://ftp.cs.wisc.edu/math- prog/cpo-dataset/machine-learn/checker.
- L. Kaufman, Solving the quadratic programming problem arising in support vector classification, in Advances in Kernel Methods -Support Vector Learning, B. Schölkopf, C. J. C. Burges, and A. J. Smola, eds., MIT Press, 1999, pp. 147- 167.
- O. L. Mangasarian, Mathematical programming in neural networks, ORSA Journal on Computing, 5(4) (1993), pp. 349-360.
- Generalized support vector machines, in Advances in Large Margin Clas- sifiers, A. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, eds., MIT Press,Cambridge, MA, 2000, pp. 135-146.
- Successive overrelaxation for support vector machines, IEEE Transac- tions on Neural Networks, 10 (1999), pp. 1032-1037.
- Lagrangian support vector machines, Technical Report 00-06, Data Min- ing Institute, Computer Sciences Department, University of Wisconsin, Madi- son, Wisconsin, June 2000. Journal of Machine Learning Research, to appear. ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-06.ps.
- T. M. Mitchell, Machine Learning. McGraw-Hill, Boston, 1997.
- J. Platt, Sequential minimal optimization: A fast algorithm for training sup- port vector machines, in Advances in Kernel Methods -Support Vector Learn- ing, B. Schölkopf, C. J. C. Burges, and A. J. Smola, eds., MIT Press, 1999, pp. 185-208. http://www.research.microsoft.com/∼jplatt/smo.html.
- B. Schölkopf, C. Burges, and A. Smola (editors), Advances in Kernel Methods: Support Vector Machines, MIT Press, Cambridge, MA, 1998.
- A. Smola, P. L. Bartlett, B. Schölkopf, and J. Schürmann (ed- itors), Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000.
- V. N. Vapnik, The Nature of Statistical Learning Theory, Springer, New York, 1995.
- C. K. I. Williams and M. Seeger, Using the Nyström method to speed up kernel machines, in Advances in Neural Information Processing Systems (NIPS2000), 2000, to appear. http://www.kernel-machines.org.
Cited by
Sorted by citations
LIBSVM: A library for support vector machines
Chang, C.-C., & Lin, C.-J. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961199 · Cited by 40,918 · see citing works
An efficient instance selection algorithm to reconstruct training set for support vector machine
Liu, C., Wang, W., Wang, M., Lv, F., & Konan, M. (2017) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.10.031 · Cited by 146 · see citing works
Decomposition Methods for Linear Support Vector Machines
Kao, W.-C., Chung, K.-M., Sun, C.-L., & Lin, C.-J. (2004) · Neural Computation · doi:10.1162/089976604774201640 · Cited by 54 · see citing works
An Equivalence between the Lasso and Support Vector Machines
Jaggi, M. (2013) · arXiv · doi:10.48550/arxiv.1303.1152 · Cited by 35 · see citing works
- Authors
- Lee, Y.-J., & Mangasarian, O. L.
- Affiliations
- University of Wisconsin–Madison (US)
- Venue
- Proceedings of the 2001 SIAM International Conference on Data Mining
- Published
- 2001-04-05
- Pages
- 1-17
- OpenAlex
- W1621799579
- Cited by
- 647
- References
- 0
- Citations by year
- 2026: 1 · 2025: 7 · 2024: 6 · 2023: 13 · 2022: 12 · 2021: 20 · 2020: 11 · 2019: 21 · 2018: 19 · 2017: 26 · 2016: 23 · 2015: 30 · 2014: 39 · 2013: 49 · 2012: 20
- FWCI
- 10.92
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- SIAM International Conference on Data Mining (publishedVersion)
- Funders
- National Science Foundation
- Air Force Office of Scientific Research
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and ELM
- Keywords
- support vector machine, nonlinear classification, quadratic programming, limited training data, computational efficiency, memory usage
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
