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 ≤ ε), and the number of misclassified training points is very small (with error ≤ δ). Experimental results show that our algorithm outperforms most of existing online algorithms, especially in the space requirement aspect, while maintaining high accuracy.
Original language | English (US) |
---|---|
Pages (from-to) | 63-79 |
Number of pages | 17 |
Journal | International Journal of Computational Geometry and Applications |
Volume | 34 |
Issue number | 1-2 |
DOIs | |
State | Published - Jun 1 2024 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics