The projectron: a bounded kernel-based Perceptron

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.
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).
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.
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.
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.
11. Engel, Y., Mannor, S., & Meir, R. (2002). Sparse online greedy support vector regression. Proceedings 13th European Conference on Machine Learning.
12. Kivinen, J., Smola, A., & Williamson, R. (2004). Online learning with kernels. IEEE Trans. on Signal Processing, 52, 2165--2176.
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).
17. Weston, J., Bordes, A., & Bottou, L. (2005). Online (and offline) on an even tighter budget. Proceedings of AISTATS 2005 (pp. 413--420).

Index Terms

• Computing methodologies

  • Machine learning

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

      • Modeling methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

  • Models of computation

    • Interactive computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory