Article

Approximate maximum margin algorithms with rules controlled by the number of mistakes

Authors:

Petroula Tsampouka,

John Shawe-TaylorAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 903 - 910

https://doi.org/10.1145/1273496.1273610

Published: 20 June 2007 Publication History

Get Access

Abstract

We present a family of incremental Perceptron-like algorithms (PLAs) with margin in which both the "effective" learning rate, defined as the ratio of the learning rate to the length of the weight vector, and the misclassification condition are entirely controlled by rules involving (powers of) the number of mistakes. We examine the convergence of such algorithms in a finite number of steps and show that under some rather mild conditions there exists a limit of the parameters involved in which convergence leads to classification with maximum margin. An experimental comparison of algorithms belonging to this family with other large margin PLAs and decomposition SVMs is also presented.

References

[1]

Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.

Google Scholar

[2]

Cristianini, N., & Shawe-Taylor, J. (2000). An introduction to support vector machines. Cambridge University Press.

Digital Library

Google Scholar

[3]

Duda, R. O., & Hart, P. E. (1973). Pattern classification and scene analysis. Wiley.

Google Scholar

[4]

Gentile, C. (2001). A new approximate maximal margin classification algorithm. Machine Learning Research, 2, 213--242.

Digital Library

Google Scholar

[5]

Joachims, T. (1999). Making large-scale svm learning practical. In Advances in kernel methods-support vector learning. MIT Press.

Digital Library

Google Scholar

[6]

Joachims, T. (2006). Training linear svms in linear time. KDD'06 (pp. 217--226). ACM Press.

Digital Library

Google Scholar

[7]

Li, Y., & Long, Y. (2002). The relaxed online maximum margin algorithm. Machine Learning, 46, 361--387.

Digital Library

Google Scholar

[8]

Platt, J. C. (1998). Sequential minimal optimization: A fast algorithm for training support vector machines (Technical Report MSR-TR-98-14). Microsoft Research.

Google Scholar

[9]

Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65 (6), 386--408.

Crossref

Google Scholar

[10]

Tsampouka, P., & Shawe-Taylor, J. (2005). Analysis of generic perceptron-like large margin classifiers. ECML 2005 (pp. 750--758). Springer-Verlag.

Digital Library

Google Scholar

[11]

Tsampouka, P., & Shawe-Taylor, J. (2006). Constant rate approximate maximum margin algorithms. ECML 2006 (pp. 437--448). Springer-Verlag.

Digital Library

Google Scholar

[12]

Vapnik, V. (1998). Statistical learning theory. Wiley.

Google Scholar

Cited By

View all

Panagiotakopoulos CTsampouka P(2011)The perceptron with dynamic marginProceedings of the 22nd international conference on Algorithmic learning theory10.5555/2050345.2050368(204-218)Online publication date: 5-Oct-2011
https://dl.acm.org/doi/10.5555/2050345.2050368
Panagiotakopoulos CTsampouka P(2011)The MargitronIEEE Transactions on Neural Networks10.1109/TNN.2010.209923822:3(395-407)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1109/TNN.2010.2099238
Panagiotakopoulos CTsampouka P(2011)The Perceptron with Dynamic MarginAlgorithmic Learning Theory10.1007/978-3-642-24412-4_18(204-218)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24412-4_18
Show More Cited By

Approximate maximum margin algorithms with rules controlled by the number of mistakes
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
2. Theory of computation

Recommendations

New support vector algorithms with parametric insensitive/margin model

In this paper, a modification of v-support vector machines (v-SVM) for regression and classification is described, and the use of a parametric insensitive/margin model with an arbitrary shape is demonstrated. This can be useful in many cases, especially ...
The Relaxed Online Maximum Margin Algorithm

We describe a new incremental algorithm for training linear threshold functions: the Relaxed Online Maximum Margin Algorithm, or ROMMA. ROMMA can be viewed as an approximation to the algorithm that repeatedly chooses the hyperplane that classifies ...
A new approximate maximal margin classification algorithm

A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ≥ 2 for a set of linearly separable data. Our algorithm, called ALMA_p (Approximate Large Margin algorithm w.r.t. norm p), takes O( (p-1) / (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
145
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Panagiotakopoulos CTsampouka P(2011)The perceptron with dynamic marginProceedings of the 22nd international conference on Algorithmic learning theory10.5555/2050345.2050368(204-218)Online publication date: 5-Oct-2011
https://dl.acm.org/doi/10.5555/2050345.2050368
Panagiotakopoulos CTsampouka P(2011)The MargitronIEEE Transactions on Neural Networks10.1109/TNN.2010.209923822:3(395-407)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1109/TNN.2010.2099238
Panagiotakopoulos CTsampouka P(2011)The Perceptron with Dynamic MarginAlgorithmic Learning Theory10.1007/978-3-642-24412-4_18(204-218)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24412-4_18
Panagiotakopoulos CTsampouka P(2010)The margin perceptron with unlearningProceedings of the 27th International Conference on International Conference on Machine Learning10.5555/3104322.3104431(855-862)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/3104322.3104431
Loza Mencía EPark SFürnkranz J(2010)Efficient voting prediction for pairwise multilabel classificationNeurocomputing10.1016/j.neucom.2009.11.02473:7-9(1164-1176)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.neucom.2009.11.024
Mencia EFurnkranz J(2008)Pairwise learning of multilabel classifications with perceptrons2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence)10.1109/IJCNN.2008.4634206(2899-2906)Online publication date: Jun-2008
https://doi.org/10.1109/IJCNN.2008.4634206

View Options

Login options

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

Cited By

Recommendations

New support vector algorithms with parametric insensitive/margin model

The Relaxed Online Maximum Margin Algorithm

A new approximate maximal margin classification algorithm