Streamed Learning: One-Pass SVMs

Abstract

We present a streaming model for large-scale classification (in the context of 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 2-SVM is known to have an equivalent formulation in terms of theminimumenclosing ball (MEB) problem, and an efficient algorithm based on the idea of core sets exists (CVM) [Tsang et al., 2005]. CVM learns a (1+ε)-approximateMEB for a set of points and yields an approximate solution to corresponding SVM instance. However CVM works in batch mode requiringmultiple 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 stateof- the-art SVM solvers (batch and online). We also give an analysis of the algorithm, and discuss some open issues and possible extensions.Piyush Rai, Hal Daume, Suresh Venkatasubramanian