research-article

Optimized cutting plane algorithm for support vector machines

Authors:

Vojtěch Franc,

Soeren SonnenburgAuthors Info & Claims

ICML '08: Proceedings of the 25th international conference on Machine learning

Pages 320 - 327

https://doi.org/10.1145/1390156.1390197

Published: 05 July 2008 Publication History

Abstract

We have developed a new Linear Support Vector Machine (SVM) training algorithm called OCAS. Its computational effort scales linearly with the sample size. In an extensive empirical evaluation OCAS significantly outperforms current state of the art SVM solvers, like SVM^light, SVM^perf and BMRM, achieving speedups of over 1,000 on some datasets over SVM^light and 20 over SVM^perf, while obtaining the same precise Support Vector solution. OCAS even in the early optimization steps shows often faster convergence than the so far in this domain prevailing approximative methods SGD and Pegasos. Effectively parallelizing OCAS we were able to train on a dataset of size 15 million examples (itself about 32GB in size) in just 671 seconds --- a competing string kernel SVM required 97,484 seconds to train on 10 million examples sub-sampled from this dataset.

References

[1]

Bottou, L., & Bousquet, O. (2008). The tradeoffs of large scale learning. In NIPS 20. MIT Press.

Digital Library

[2]

Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for svms. http://www.csie.ntu.edu.tw/~cjlin/libsvm.

[3]

Chapelle, O. (2007). Training a Support Vector Machine in the Primal. Neural Comp., 19, 1155--1178.

Digital Library

[4]

Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20, 273--297.

[5]

Cristianini, N., & Shwawe-Taylor, J. (2000). An introduction to support vector machines. Cambridge, UK: CUP.

Digital Library

[6]

Fan, R.-E., Chen, P.-H., & Lin, C.-J. (2005). Working set selection using second order information for training svm. Journal of Machine Learning Research, 6, 1889--1918.

Digital Library

[7]

Fawcett, T. (2003). Roc graphs: Notes and practical considerations for data mining researchers. Technical Report HPL-2003-4). HP Laboratories, Palo Alto, CA, USA.

[8]

Franc, V., & Sonnenburg, S. (2007). Optimized cutting plane algorithm for SVMs. Research Report; Electronic Publication 1). Fraunhofer Institute FIRST.

[9]

Joachims, T. (1999). Making large-scale SVM learning practical. Advances in Kernel Methods --- Support Vector Learning (pp. 169--184). Cambridge, MA, USA: MIT Press.

Digital Library

[10]

Joachims, T. (2006). Training linear svms in linear time. KDD'06.

Digital Library

[11]

Lin, C.-J., Weng, R. C., & Keerthi, S. S. (2007). Trust region newton methods for large-scale logistic regression. ICML '07 (pp. 561--568). ACM New York.

Digital Library

[12]

Shwartz, S.-S., Singer, Y., & Srebro, N. (2007). Pegasos: Primal estimated sub-gradient solver for svm. ICML '07 (pp. 807--814). ACM Press.

Digital Library

[13]

Sindhwani, V., & Keerthi, S.-S. (2007). Newton methods for fast solution of semi-supervised linear svms. In Large scale kernel machines. MIT Press.

[14]

Teo, C. H., Le, Q., Smola, A., & Vishwanathan, S. (2007). A scalable modular convex solver for regularized risk minimization. KDD'07.

Digital Library

[15]

Zanni, L., Serafini, T., & Zanghirati, G. (2006). Parallel software for training. JMLR, 7, 1467--1492.

Digital Library

Cited By

Menon RChakrabarti I(2023)Low complexity VLSI architecture for improved primal–dual support vector machine learning coreMicroprocessors and Microsystems10.1016/j.micpro.2023.10480698(104806)Online publication date: Apr-2023
https://doi.org/10.1016/j.micpro.2023.104806
Piccialli VSciandrone M(2022)Nonlinear optimization and support vector machinesAnnals of Operations Research10.1007/s10479-022-04655-x314:1(15-47)Online publication date: 14-Apr-2022
https://doi.org/10.1007/s10479-022-04655-x
Ju XYan ZWang T(2021)Overview of Optimization Algorithms for Large-scale Support Vector Machines2021 International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW53433.2021.00119(909-916)Online publication date: Dec-2021
https://doi.org/10.1109/ICDMW53433.2021.00119
Show More Cited By

Index Terms

Optimized cutting plane algorithm for support vector machines

Recommendations

Wavelet twin support vector machines based on glowworm swarm optimization

Twin support vector machine is a machine learning algorithm developing from standard support vector machine. The performance of twin support vector machine is always better than support vector machine on datasets that have cross regions. Recently ...
PAC-Bayes bounds for twin support vector machines

Twin support vector machines are regarded as a milestone in the development of support vector machines. Compared to standard support vector machines, they learn two nonparallel hyperplanes rather than one as in standard support vector machines for ...
Multitask centroid twin support vector machines

Twin support vector machines are a recently proposed learning method for binary classification. They learn two hyperplanes rather than one as in conventional support vector machines and often bring performance improvements. However, an inherent shortage ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '08: Proceedings of the 25th international conference on Machine learning

July 2008

1310 pages

ISBN:9781605582054

DOI:10.1145/1390156

General Chair:
William Cohen
Carnegie Mellon University
,
Program Chairs:
Andrew McCallum
University of Massachusetts Amherst
,
Sam Roweis
University of Toronto and Google

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Pascal
University of Helsinki
Xerox
Federation of Finnish Learned Societies
Google Inc.
NSF
Machine Learning Journal/Springer
Microsoft Research: Microsoft Research
Intel: Intel
Yahoo!
Helsinki Institute for Information Technology
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Sixth Framework Programme

Conference

ICML '08

Sponsor:

Microsoft Research
Intel
IBM

ICML '08: The 25th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

July 5 - 9, 2008

Helsinki, Finland

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
486
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Menon RChakrabarti I(2023)Low complexity VLSI architecture for improved primal–dual support vector machine learning coreMicroprocessors and Microsystems10.1016/j.micpro.2023.10480698(104806)Online publication date: Apr-2023
https://doi.org/10.1016/j.micpro.2023.104806
Piccialli VSciandrone M(2022)Nonlinear optimization and support vector machinesAnnals of Operations Research10.1007/s10479-022-04655-x314:1(15-47)Online publication date: 14-Apr-2022
https://doi.org/10.1007/s10479-022-04655-x
Ju XYan ZWang T(2021)Overview of Optimization Algorithms for Large-scale Support Vector Machines2021 International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW53433.2021.00119(909-916)Online publication date: Dec-2021
https://doi.org/10.1109/ICDMW53433.2021.00119
Fogler KGuron GWind LKeenum IHession WKrometis LStrawn LPruden APonder M(2019)Microbiota and Antibiotic Resistome of Lettuce Leaves and Radishes Grown in Soils Receiving Manure-Based Amendments Derived From Antibiotic-Treated CowsFrontiers in Sustainable Food Systems10.3389/fsufs.2019.000223Online publication date: 10-Apr-2019
https://doi.org/10.3389/fsufs.2019.00022
Lu MQiao LFeng DLi DLu X(2019)Mini-batch cutting plane method for regularized risk minimizationFrontiers of Information Technology & Electronic Engineering10.1631/FITEE.180059620:11(1551-1563)Online publication date: 16-Dec-2019
https://doi.org/10.1631/FITEE.1800596
Chauhan VDahiya KSharma A(2019)Problem formulations and solvers in linear SVMArtificial Intelligence Review10.1007/s10462-018-9614-652:2(803-855)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10462-018-9614-6
Piccialli VSciandrone M(2018)Nonlinear optimization and support vector machines4OR10.1007/s10288-018-0378-216:2(111-149)Online publication date: 23-May-2018
https://doi.org/10.1007/s10288-018-0378-2
Ju XTian Y(2018)A divide-and-conquer method for large scale ź-nonparallel support vector machinesNeural Computing and Applications10.1007/s00521-016-2574-329:9(497-509)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00521-016-2574-3
Dong YDu BZhang LZhang L(2017)Exploring Locally Adaptive Dimensionality Reduction for Hyperspectral Image Classification: A Maximum Margin Metric Learning AspectIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2016.258774710:3(1136-1150)Online publication date: Mar-2017
https://doi.org/10.1109/JSTARS.2016.2587747
(2017)LAM3LNeurocomputing10.1016/j.neucom.2016.12.008235:C(1-9)Online publication date: 26-Apr-2017
https://dl.acm.org/doi/10.1016/j.neucom.2016.12.008
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents