Free Access

A Space-Efficient One-Pass Online SVM Algorithm

Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, New York 14260, USA

Department of Computer Science and Software Engineering, Penn State Erie, The Behrend College, Erie, Pennsylvania 16509, USA

E-mail Address: zxh201@psu.edu

Corresponding author.

Search for more papers by this author

, and

Jinhui Xu

https://orcid.org/0000-0001-5730-9429

Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, New York 14260, USA

E-mail Address: jinhui@buffalo.edu

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218195924500043Cited by:0 (Source: Crossref)

Abstract

In this paper we consider the problem of training a Support Vector Machine (SVM) online using a stream of data in random order. We provide a fast online training algorithm for general SVM on very large datasets. Based on the geometric interpretation of SVM known as the polytope distance, our algorithm uses a gradient descent procedure to solve the problem. With high probability our algorithm outputs an $(ϵ, δ)$ $(𝜖, δ)$ -approximation result in constant time and space, which is independent of the size of the dataset, where $(ϵ, δ)$ $(𝜖, δ)$ -approximation means that the separating margin of the classifier is almost optimal (with error $\leq ϵ$ $\leq 𝜖$ ), and the number of misclassified training points is very small (with error $\leq δ$ $\leq δ$ ). Experimental results show that our algorithm outperforms most of existing online algorithms, especially in the space requirement aspect, while maintaining high accuracy.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

1. R. M. Karp , On-line algorithms versus off-line algorithms: How much is it worth to know the future?, in Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information (1992). Google Scholar
2. C. Cortes and V. Vapnik, Support vector networks, Machine Learning. Google Scholar
3. A. Bordes, S. Ertekin, J. Weston and L. Bottou, Fast kernel classifiers with online and active learning, Journal of Machine Learning Research. Google Scholar
4. J. Zheng, H. Yu, F. Shen and J. Zhao, An online incremental learning support vector machine for large-scale data, (2010), ICANN’10. Google Scholar
5. P. Rai, H. D. III and S. Venkatasubramanian , Streamed learning: One-pass svms, in Proceedings of the 20th International Conference on Artificial Neural Networks: Part II (2009). Google Scholar
6. S. Matsushima, S. Vishwanathan and A. J. Smola , Linear support vector machines via dual cached loops, in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2012), KDD ’12. Crossref, Google Scholar
7. O. Dekel, S. Shalev-shwartz and Y. Singer , The forgetron: A kernel-based perceptron on a fixed budget, in In Advances in Neural Information Processing Systems 18 (2005). Google Scholar
8. Z. Wang, K. Crammer and S. Vucetic, Breaking the curse of kernelization: Budgeted stochastic gradient descent for large-scale svm training, J. Mach. Learn. Res. Google Scholar
9. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz and Y. Singer, Online passive-aggressive algorithms, J. Mach. Learn. Res. Google Scholar
10. M. Dredze, K. Crammer and F. Pereira , Confidence-weighted linear classification, in Proceedings of the 25th International Conference on Machine Learning (2008), ICML ’08. Crossref, Google Scholar
11. K.-W. Chang and D. Roth , Selective block minimization for faster convergence of limited memory large-scale linear models, in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2011), KDD ’11. Crossref, Google Scholar
12. E. Romero, I. Barrio and L. Belanche , Incremental and decremental learning for linear support vector machines, in Artificial Neural Networks - ICANN 2007 (2007). Crossref, Google Scholar
13. P. Laskov, C. Gehl, S. Kruger and K. Muller, Incremental support vector learning: Analysis, implementation and applications, Journal of Machine Learning Research. Google Scholar
14. P. L. Bartlett, E. Hazan and A. Rakhlin, Adaptive online gradient descent, Proc. of Neural Info. Processing Systems Conf. Google Scholar
15. G. Gärtner and M. Jaggi , Coresets for polytope distance, Symposium on Computational Geometry, 2009. Crossref, Google Scholar
16. K. L. Clarkson, E. Hazan and D. P. Woodruff, Sublinear optimization for machine learning, J. ACM. Google Scholar
17. K. L. Clarkson, Coresets, sparse greedy approximation, and the frank-wolfe algorithm, ACM Trans. Algorithms. Google Scholar
18. M. Mavroforakis, M. Sdralis and S. Theodoridis , A novel svm geometric algorithm based on reduced convex hulls, in Pattern Recognition, 2006. ICPR 2006. 18th International Conference on (2006). Crossref, Google Scholar
19. E. G. Gilbert, An iterative procedure for computing the minimum of a quadratic form on a convex set, SIAM Journal on Control. Google Scholar
20. H. Ding and J. Xu, Random gradient descent tree: A combinatorial approach for svm with outliers, Association for the Advanced of Artificial Intelligence Conf. 2015. Google Scholar
21. Z. Wang and S. Vucetic , Online passive-aggressive algorithms on a budget, in International Conference on Artificial Intelligence and Statistics (2010). Google Scholar