Abstract
We propose a novel online kernel classifier algorithm that converges to the Hard Margin SVM solution. The same update rule is used to both add and remove support vectors from the current classifier. Experiments suggest that this algorithm matches the SVM accuracies after a single pass over the training examples. This algorithm is attractive when one seeks a competitive classifier with large datasets and limited computing resources.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Vapnik, V.N.: The Nature of Statistical Learning Theory. Springer, New York (1995)
Aizerman, M.A., Braverman, É.M., Rozonoér, L.I.: Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control 25, 821–837 (1964)
Vapnik, V., Lerner, A.: Pattern recognition using generalized portrait method. Automation and Remote Control 24, 774–780 (1963)
Rosenblatt, F.: The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review 65, 386–408 (1958)
Freund, Y., Schapire, R.E.: Large margin classification using the perceptron algorithm. In: Shavlik, J. (ed.) Machine Learning: Proceedings of the Fifteenth International Conference. Morgan Kaufmann, San Francisco (1998)
Frieß, T.T., Cristianini, N., Campbell, C.: The kernel Adatron algorithm: a fast and simple learning procedure for support vector machines. In: Shavlik, J. (ed.) 15th International Conf. Machine Learning, pp. 188–196. Morgan Kaufmann Publishers, San Francisco (1998)
Gentile, C.: A new approximate maximal margin classification algorithm. Journal of Machine Learning Research 2, 213–242 (2001)
Li, Y., Long, P.: The relaxed online maximum margin algorithm. Machine Learning 46, 361–387 (2002)
Crammer, K., Singer, Y.: Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research 3, 951–991 (2003)
Crammer, K., Kandola, J., Singer, Y.: Online classification on a budget. In: Thrun, S., Saul, L., Schölkopf, B. (eds.) Advances in Neural Information Processing Systems 16, MIT Press, Cambridge (2004)
Keerthi, S.S., Shevade, S.K., Bhattacharyya, C., Murthy, K.R.K.: A fast iterative nearest point algorithm for support vector machine classifier design. Technical Report Technical Report TR-ISL-99-03, Indian Institute of Science, Bangalore (1999), http://guppy.mpe.nus.edu.sg/~mpessk/npa_tr.ps.gz
Bennett, K.P., Bredensteiner, E.J.: Duality and geometry in SVM classifiers. In: Langley, P. (ed.) Proceedings of the 17th International Conference on Machine Learning, pp. 57–64. Morgan Kaufmann, San Francisco (2000)
Crisp, D.J., Burges, C.J.C.: A geometric interpretation of ν-SVM classifiers. In: Solla, S.A., Leen, T.K., Müller, K.R. (eds.) Advances in Neural Information Processing Systems 12. MIT Press, Cambridge (2000)
Gilbert, E.G.: Minimizing the quadratic form on a convex set. SIAM J. Control 4, 61–79 (1966)
Haffner, P.: Escaping the convex hull with extrapolated vector machines. In: Dietterich, T., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing Systems 14, pp. 753–760. MIT Press, Cambridge (2002)
Cortes, C., Vapnik, V.: Support vector networks. Machine Learning 20, 273–297 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bordes, A., Bottou, L. (2005). The Huller: A Simple and Efficient Online SVM. In: Gama, J., Camacho, R., Brazdil, P.B., Jorge, A.M., Torgo, L. (eds) Machine Learning: ECML 2005. ECML 2005. Lecture Notes in Computer Science(), vol 3720. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564096_48
Download citation
DOI: https://doi.org/10.1007/11564096_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29243-2
Online ISBN: 978-3-540-31692-3
eBook Packages: Computer ScienceComputer Science (R0)