Article

Free access

A training algorithm for optimal margin classifiers

Authors:

Bernhard E. Boser,

Isabelle M. Guyon,

Vladimir N. VapnikAuthors Info & Claims

COLT '92: Proceedings of the fifth annual workshop on Computational learning theory

Pages 144 - 152

https://doi.org/10.1145/130385.130401

Published: 01 July 1992 Publication History

Abstract

A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented. The technique is applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions. The effective number of parameters is adjusted automatically to match the complexity of the problem. The solution is expressed as a linear combination of supporting patterns. These are the subset of training patterns that are closest to the decision boundary. Bounds on the generalization performance based on the leave-one-out method and the VC-dimension are given. Experimental results on optical character recognition problems demonstrate the good generalization obtained when compared with other learning algorithms.

References

[1]

M.A. Aizerman, E.M. Braverman, and L.I. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821-837, 1964.

[2]

E.B. Baum and D. Haussler. What size net gives valid generalization? Neural Computation, 1(1):151-160, 1989.

Digital Library

[3]

D.S. Broomhead and D. Lowe. Multivariate functional interpolation and adaptive networks. Complex Systems, 2:321 - 355, 1988.

[4]

Yann Le Cun, Bernhard Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne Hubbard, and Larry D. Jackel. Handwritten digit recognition with a back-propagation network. In David S. Touretzky, editor, Neural Information Processing Systems, volume 2, pages 396-404. Morgan Kaufmann Publishers, San Mateo, CA, 1990.

Digital Library

[5]

R. Courant and D. Hilbert. Methods of mathematical physics. Interscience, New York, 1953.

[6]

R.O. Duda and P.E. Hart. Pattern Classification And Scene Analysis. Wiley and Son, 1973.

[7]

S. Geman, E. Bienenstock, and R. Doursat. Neural networks and the bias/variance dilemma. Neural Computation, 4 (1):1 - 58, 1992.

Digital Library

[8]

I. Guyon, I. Poujaud, L. Personnaz, G. Dreyfus, J. Denker, and Y. LeCun. Comparing different neural network architectures for classifying handwritten digits. In Proc. Int. Joint Conf. Neural Networks. Int. Joint Conference on Neural Networks, 1989.

[9]

Isabelle Guyon, Vladimir Vapnik, Bernhard Boser, Leon Bottou, and Sara Solla. Structural risk minimization for character recognition. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufmann Publishers, San Mateo, CA, 1992. To appear.

[10]

David Haussler, Nick Littlestone, and Manfred Warmuth. Predicting 0,1-functions on randomly drawn points. In Proceedings of the 29th Annual Symposium on the Foundations of Computer Science, pages 100-109. IEEE, 1988.

[11]

W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. Phys. A: Math. gen., 20:L745, 1987.

[12]

F.A. Lootsma, editor. Numerical Methods for Non-linear Optimization. Academic Press, London, 1972.

[13]

David Luenberger. Linear and Nonlinear Programming. Addison-Wesley, 1984.

[14]

D. MacKay. A practical bayesian framework for backprop networks. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufmann Publishers, San Mateo, CA, 1992. To appear.

[15]

J. Moody and C. Darken. Fast learning in networks of locally tuned processing units. Neural Computation, i (2):281 - 294, 1989.

[16]

N. Matte, I. Guyon, L. Bottou, J. Denker, and V. Vapnik. Computer-aided cleaning of large databases for character recognition. In Digest ICPR. ICPR, Amsterdam, August 1992.

[17]

J. Moody. Generalization, weight decay, and architecture selection for nonlinear learning systems. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufrnann Publishers, San Mateo, CA, 1992. To appear.

[18]

A.S. Nemirovsky and D. Do Yudin. Problem Complexzty and Method Efficiency in Optimization. Wiley, New York, 1983.

[19]

S.M. Omohundro. Bumptrees for efficient function, constraint and classification learning. In R.P. Lippmann and et al., editors, NIPS-90, San Mateo CA, 1991. IEEE, Morgan Kaufmann.

Digital Library

[20]

T. Poggio and F. Girosi. Regularization algorithms for learning that are equivalent to nmltilayer networks. Science, 247:978 - 982, February 1990.

[21]

T. Poggio. On optimal nonlinear associative recall. Biol. Cybernetics, Vol. 19:201-209, 1975.

[22]

F. Rosenblatt. Princzples of neurodynamics. Spartan Books, New York, 1962.

[23]

P. Simard, Y. LeCun, and J. Denker. Tangent prop--a formalism for specifying selected invariances in an adaptive network. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufmann Publishers, San Mateo, CA, 1992. To appear.

[24]

N. Tishby, E. Levin, and S. A. Solla. Consistent inference of probabilities in layered networks: Predictions and generalization. In Proceedings of the International Joint Conference on Neural Networks, Washington DC, 1989.

[25]

Vladimir Vapnik. Estimation of Dependences Based on Empirical Data. Springer Verlag, New York, 1982.

Digital Library

[26]

V.N. Vapnik and A.Ya. Chervonenkis. The theory of pattern recognition. Nauka, Moscow, 1974.

Cited By

Mosavi NGolalizadeh M(2024)A New Approach in Using Random Support Vector Machine Cluster in Analyzing Prostate Cancer Gene Expression DataJournal of Statistical Sciences10.61186/jss.17.2.417:2(0-0)Online publication date: 1-Feb-2024
https://doi.org/10.61186/jss.17.2.4
Anwer ZAbdalrada A(2024)Assessing Institutional Performance using Machine Learning on Arabic Facebook CommentsEngineering, Technology & Applied Science Research10.48084/etasr.807914:4(16025-16031)Online publication date: 2-Aug-2024
https://doi.org/10.48084/etasr.8079
SHABESTANI SGEÇİKLİ M(2024)Machine learning use for English texts’ classification (A mini-review)İngilizce Metinlerin Sınıflandırması İçin Makine Öğrenimi KullanımıOsmaniye Korkut Ata Üniversitesi Fen Bilimleri Enstitüsü Dergisi10.47495/okufbed.12598687:1(414-423)Online publication date: 22-Jan-2024
https://doi.org/10.47495/okufbed.1259868
Show More Cited By

Index Terms

A training algorithm for optimal margin classifiers
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
    2. Machine learning approaches
      1. Classification and regression trees

Recommendations

Convex large margin training techniques: unsupervised, semi-supervised, and robust support vector machines
Bootstrapped training of event extraction classifiers
EACL '12: Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics

Most event extraction systems are trained with supervised learning and rely on a collection of annotated documents. Due to the domain-specificity of this task, event extraction systems must be retrained with new annotated data for each domain. In this ...
Maximum margin partial label learning

Partial label learning aims to learn from training examples each associated with a set of candidate labels, among which only one label is valid for the training example. The basic strategy to learn from partial label examples is disambiguation, i.e. by ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

COLT '92: Proceedings of the fifth annual workshop on Computational learning theory

July 1992

452 pages

ISBN:089791497X

DOI:10.1145/130385

Chairman:
David Haussler

Copyright © 1992 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COLT92

Sponsor:

COLT92: 5th Annual Workshop on Computational Learning Theory

July 27 - 29, 1992

Pennsylvania, Pittsburgh, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6,621
Total Citations
View Citations
14,070
Total Downloads

Downloads (Last 12 months)4,455
Downloads (Last 6 weeks)427

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mosavi NGolalizadeh M(2024)A New Approach in Using Random Support Vector Machine Cluster in Analyzing Prostate Cancer Gene Expression DataJournal of Statistical Sciences10.61186/jss.17.2.417:2(0-0)Online publication date: 1-Feb-2024
https://doi.org/10.61186/jss.17.2.4
Anwer ZAbdalrada A(2024)Assessing Institutional Performance using Machine Learning on Arabic Facebook CommentsEngineering, Technology & Applied Science Research10.48084/etasr.807914:4(16025-16031)Online publication date: 2-Aug-2024
https://doi.org/10.48084/etasr.8079
SHABESTANI SGEÇİKLİ M(2024)Machine learning use for English texts’ classification (A mini-review)İngilizce Metinlerin Sınıflandırması İçin Makine Öğrenimi KullanımıOsmaniye Korkut Ata Üniversitesi Fen Bilimleri Enstitüsü Dergisi10.47495/okufbed.12598687:1(414-423)Online publication date: 22-Jan-2024
https://doi.org/10.47495/okufbed.1259868
Althunibat AAlsawareah BMaidin SHawashin BJebril IZaqaibeh BAl-khawaja H(2024)Detecting Ambiguities in Requirement Documents Written in Arabic Using Machine Learning AlgorithmsInternational Journal of Cloud Applications and Computing10.4018/IJCAC.33956314:1(1-19)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.4018/IJCAC.339563
Jayaswal VRani RKaur J(2024)A Deep Learning-Based Efficient Image Captioning Approach for Hindi LanguageDevelopments Towards Next Generation Intelligent Systems for Sustainable Development10.4018/979-8-3693-5643-2.ch009(225-246)Online publication date: 5-Apr-2024
https://doi.org/10.4018/979-8-3693-5643-2.ch009
Motadi M(2024)Harnessing AI for Ethical Digital Consumer Behavior AnalysisEnhancing and Predicting Digital Consumer Behavior with AI10.4018/979-8-3693-4453-8.ch012(211-237)Online publication date: 12-Apr-2024
https://doi.org/10.4018/979-8-3693-4453-8.ch012
Wada NAwaya YYoshida NUnome SYamaguchi A(2024)Tree Species Classification in Private Forests in the Suzuka Mountains of Japan Using Airborne LiDAR Data Including Three Wavelengths3波長の航空機LiDARデータを用いた樹種分類の検討Journal of the Japanese Forest Society10.4005/jjfs.106.57106:3(57-67)Online publication date: 1-Mar-2024
https://doi.org/10.4005/jjfs.106.57
Çokaj EGustad HLeone AMoe PMoldestad L(2024)Supervised time series classification for anomaly detection in subsea engineeringJournal of Computational Dynamics10.3934/jcd.2024019(0-0)Online publication date: 2024
https://doi.org/10.3934/jcd.2024019
Salas EKumaran SBennett RWillis LMitchell K(2024)Machine Learning-Based Classification of Small-Sized Wetlands Using Sentinel-2 ImagesAIMS Geosciences10.3934/geosci.202400510:1(62-79)Online publication date: 2024
https://doi.org/10.3934/geosci.2024005
Park NCho JPark J(2024)Assessing crash severity of urban roads with data mining techniques using big data from in-vehicle dashcamElectronic Research Archive10.3934/era.202402932:1(584-607)Online publication date: 2024
https://doi.org/10.3934/era.2024029
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents