Computer Science – Learning
Scientific paper
2009-08-05
IJCAI 2009
Computer Science
Learning
Scientific paper
We present a streaming model for large-scale classification (in the context of $\ell_2$-SVM) by leveraging connections between learning and computational geometry. The streaming model imposes the constraint that only a single pass over the data is allowed. The $\ell_2$-SVM is known to have an equivalent formulation in terms of the minimum enclosing ball (MEB) problem, and an efficient algorithm based on the idea of \emph{core sets} exists (Core Vector Machine, CVM). CVM learns a $(1+\varepsilon)$-approximate MEB for a set of points and yields an approximate solution to corresponding SVM instance. However CVM works in batch mode requiring multiple passes over the data. This paper presents a single-pass SVM which is based on the minimum enclosing ball of streaming data. We show that the MEB updates for the streaming case can be easily adapted to learn the SVM weight vector in a way similar to using online stochastic gradient updates. Our algorithm performs polylogarithmic computation at each example, and requires very small and constant storage. Experimental results show that, even in such restrictive settings, we can learn efficiently in just one pass and get accuracies comparable to other state-of-the-art SVM solvers (batch and online). We also give an analysis of the algorithm, and discuss some open issues and possible extensions.
III Hal Daume
Rai Piyush
Venkatasubramanian Suresh
No associations
LandOfFree
Streamed Learning: One-Pass SVMs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Streamed Learning: One-Pass SVMs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Streamed Learning: One-Pass SVMs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-254177