research-article

The projectron: a bounded kernel-based Perceptron

Authors:

Francesco Orabona,

Barbara CaputoAuthors Info & Claims

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

Pages 720 - 727

https://doi.org/10.1145/1390156.1390247

Published: 05 July 2008 Publication History

Abstract

We present a discriminative online algorithm with a bounded memory growth, which is based on the kernel-based Perceptron. Generally, the required memory of the kernel-based Perceptron for storing the online hypothesis is not bounded. Previous work has been focused on discarding part of the instances in order to keep the memory bounded. In the proposed algorithm the instances are not discarded, but projected onto the space spanned by the previous online hypothesis. We derive a relative mistake bound and compare our algorithm both analytically and empirically to the state-of-the-art Forgetron algorithm (Dekel et al, 2007). The first variant of our algorithm, called Projectron, outperforms the Forgetron. The second variant, called Projectron++, outperforms even the Perceptron.

References

[1]

Cauwenberghs, G., & Poggio, T. (2000). Incremental and decremental support vector machine learning. Advances in Neural Information Processing Systems 14.

[2]

Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Trans. on Information Theory, 50, 2050--2057.

Digital Library

[3]

Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2006). Tracking the best hyperplane with a simple budget Perceptron. Proc. of the 19th Conference on Learning Theory (pp. 483--498).

Digital Library

[4]

Cheng, L., Vishwanathan, S. V. N., Schuurmans, D., Wang, S., & Caelli, T. (2007). Implicit online learning with kernels. Advances in Neural Information Processing Systems 19.

[5]

Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., & Singer, Y. (2006). Online passive-aggressive algorithms. Journal of Machine Learning Research, 7, 551--585.

Digital Library

[6]

Crammer, K., Kandola, J., & Singer, Y. (2003). Online classification on a budget. Advances in Neural Information Processing Systems 16.

[7]

Csató, L., & Opper, M. (2001). Sparse representation for gaussian process models. Advances in Neural Information Processing Systems 13.

[8]

Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2007). The Forgetron: A kernel-based perceptron on a budget. SIAM Journal on Computing, 37, 1342--1372.

Digital Library

[9]

Dekel, O., & Singer, Y. (2005). Data-driven online to batch conversions. Advances in Neural Information Processing Systems 18.

[10]

Downs, T., Gates, K. E., & Masters, A. (2001). Exact simplification of support vectors solutions. Journal of Machine Learning Research, 2, 293--297.

Digital Library

[11]

Engel, Y., Mannor, S., & Meir, R. (2002). Sparse online greedy support vector regression. Proceedings 13th European Conference on Machine Learning.

Digital Library

[12]

Kivinen, J., Smola, A., & Williamson, R. (2004). Online learning with kernels. IEEE Trans. on Signal Processing, 52, 2165--2176.

Digital Library

[13]

Orabona, F., Castellini, C., Caputo, B., Luo, J., & Sandini, G. (2007). Indoor place recognition using online independent support vector machines. Proc. of the British Machine Vision Conference 2007 (pp. 1090--1099).

[14]

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

[15]

Schölkopf, B., Herbrich, R., Smola, A., & Williamson, R. (2000). A generalized representer theorem. Proc. of the 13th Conference on Computational Learning Theory.

[16]

Shalev-Shwartz, S., & Singer, Y. (2005). A new perspective on an old perceptron algorithm. Proc. of the 18th Conference on Learning Theory (pp. 264--278).

Digital Library

[17]

Weston, J., Bordes, A., & Bottou, L. (2005). Online (and offline) on an even tighter budget. Proceedings of AISTATS 2005 (pp. 413--420).

Cited By

Su CZhang LZhao L(2023)Online local fisher risk minimization: a new online kernel method for online classificationApplied Intelligence10.1007/s10489-022-04400-853:14(17662-17678)Online publication date: 10-Jan-2023
https://doi.org/10.1007/s10489-022-04400-8
Su CZhang LZhao L(2023)FFTRL: A Sparse Online Kernel Classification Algorithm for Large Scale DataArtificial Neural Networks and Machine Learning – ICANN 202310.1007/978-3-031-44207-0_17(195-206)Online publication date: 22-Sep-2023
https://doi.org/10.1007/978-3-031-44207-0_17
Wang HLi QLiu Y(2023)Adaptive supervised learning on data streams in reproducing kernel Hilbert spaces with data sparsity constraintStat10.1002/sta4.51412:1Online publication date: 2-Jan-2023
https://doi.org/10.1002/sta4.514
Show More Cited By

Index Terms

The projectron: a bounded kernel-based Perceptron
1. Computing methodologies
  1. Machine learning
  2. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
      2. Modeling methodologies
2. Theory of computation

Recommendations

WOM-Code Solutions for Low Latency and High Endurance in Phase Change Memory
This paper describes a write-once-memory-code phase change memory (WOM-code PCM) architecture for next-generation non-volatile memory applications. Specifically, we address the long latency of the write operation in PCM—attributed to PCM SET—...
A Novel Memory Block Management Scheme for PCM Using WOM-Code
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems

Phase Change Memory (PCM) is a promising DRAM replacement in embedded systems due to its attractive characteristics including low static power consumption and high density. However, long write latency is one of the major drawbacks in current PCM ...
Mellow writes: extending lifetime in resistive memories through selective slow write backs
ISCA'16

Emerging resistive memory technologies, such as PCRAM and ReRAM, have been proposed as promising replacements for DRAM-based main memory, due to their better scalability, low standby power, and non-volatility. However, limited write endurance is a major ...

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

74
Total Citations
View Citations
253
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Su CZhang LZhao L(2023)Online local fisher risk minimization: a new online kernel method for online classificationApplied Intelligence10.1007/s10489-022-04400-853:14(17662-17678)Online publication date: 10-Jan-2023
https://doi.org/10.1007/s10489-022-04400-8
Su CZhang LZhao L(2023)FFTRL: A Sparse Online Kernel Classification Algorithm for Large Scale DataArtificial Neural Networks and Machine Learning – ICANN 202310.1007/978-3-031-44207-0_17(195-206)Online publication date: 22-Sep-2023
https://doi.org/10.1007/978-3-031-44207-0_17
Wang HLi QLiu Y(2023)Adaptive supervised learning on data streams in reproducing kernel Hilbert spaces with data sparsity constraintStat10.1002/sta4.51412:1Online publication date: 2-Jan-2023
https://doi.org/10.1002/sta4.514
Wang WLiang JLiu RSong YZhang M(2022)A Robust Variable Selection Method for Sparse Online Regression via the Elastic Net PenaltyMathematics10.3390/math1016298510:16(2985)Online publication date: 18-Aug-2022
https://doi.org/10.3390/math10162985
Guo JRaj RLove DBrinton C(2022)Nonparametric Decentralized Detection and Sparse Sensor Selection via Multi-Sensor Online Kernel Scalar QuantizationIEEE Transactions on Signal Processing10.1109/TSP.2022.317610970(2593-2608)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1109/TSP.2022.3176109
S AR NB CRafi MR S(2022)Online feature Selection using Pearson Correlation Technique2022 IEEE 7th International Conference on Recent Advances and Innovations in Engineering (ICRAIE)10.1109/ICRAIE56454.2022.10054267(172-177)Online publication date: 1-Dec-2022
https://doi.org/10.1109/ICRAIE56454.2022.10054267
Yamauchi K(2022)Quick continual kernel learning on bounded memory space based on balancing between adaptation and forgettingEvolving Systems10.1007/s12530-022-09476-814:3(437-460)Online publication date: 30-Dec-2022
https://doi.org/10.1007/s12530-022-09476-8
Yang PLi PDemartini GZuccon GCulpepper JHuang ZTong H(2021)Adversarial Kernel Sampling on Class-imbalanced Data StreamsProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482227(2352-2362)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482227
Shen YKarimi-Bidhendi SJafarkhani H(2021)Distributed and Quantized Online Multi-Kernel LearningIEEE Transactions on Signal Processing10.1109/TSP.2021.311535769(5496-5511)Online publication date: 2021
https://doi.org/10.1109/TSP.2021.3115357
Yang PLi XLi P(2021)Graph-based Adversarial Online Kernel Learning with Adaptive Embedding2021 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM51629.2021.00091(797-806)Online publication date: Dec-2021
https://doi.org/10.1109/ICDM51629.2021.00091
Show More Cited By

View Options

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