Decentralized Online Big Data Classification - a Bandit Framework
This work addresses the challenge of efficient real-time data mining in distributed systems for applications handling large-scale, dynamic data streams, though it is incremental by building on prior distributed online learning methods.
The paper tackles the problem of decentralized online classification of big data from multiple distributed sources by proposing a framework where heterogeneous learners collaborate to classify data streams, balancing classification benefits against communication costs, and achieves sublinear regret with analytic performance guarantees.
Distributed, online data mining systems have emerged as a result of applications requiring analysis of large amounts of correlated and high-dimensional data produced by multiple distributed data sources. We propose a distributed online data classification framework where data is gathered by distributed data sources and processed by a heterogeneous set of distributed learners which learn online, at run-time, how to classify the different data streams either by using their locally available classification functions or by helping each other by classifying each other's data. Importantly, since the data is gathered at different locations, sending the data to another learner to process incurs additional costs such as delays, and hence this will be only beneficial if the benefits obtained from a better classification will exceed the costs. We assume that the classification functions available to each processing element are fixed, but their prediction accuracy for various types of incoming data are unknown and can change dynamically over time, and thus they need to be learned online. We model the problem of joint classification by the distributed and heterogeneous learners from multiple data sources as a distributed contextual bandit problem where each data is characterized by a specific context. We develop distributed online learning algorithms for which we can prove that they have sublinear regret. Compared to prior work in distributed online data mining, our work is the first to provide analytic regret results characterizing the performance of the proposed algorithms.