Decentralized Online Big Data Classification - a Bandit Framework

Cem Tekin, Mihaela van der SchaararXiv 2013 · OpenReview

Abstract

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.

Introduction

In modern Big Data scenarios—such as network security, sensor networks, or stock market monitoring—data is often generated at the "edge" across many distributed locations. Centralizing this data for analysis is frequently impossible due to massive bandwidth requirements, latency constraints, or privacy concerns. This paper addresses three primary challenges in this domain: heterogeneity of learners, decentralization of information, and the inherent tradeoff between classification accuracy and communication costs.

Comparison of the proposed framework with existing literature across key dimensions such as regret bounds and data partitioning.

As shown in the comparison above, this work distinguishes itself by providing a sublinear regret bound and supporting both horizontal and vertical data partitioning, features often absent in prior non-cooperative or cooperative offline models.

Methodology and System Architecture

The researchers model the system as a Contextual Multi-Armed Bandit (MAB) problem. Each learner treats its own local classifiers and its neighboring learners as "arms" that can be pulled. The system operates in a decentralized manner where learners "learn how to learn" from each other, discovering which peers are experts for specific types of data (contexts) without any a priori knowledge.

The system model illustrating the interaction between distributed learners, including data arrival, action selection, and feedback loops.

Key components of the framework include:

  • Context-Awareness: Learners use context (e.g., source IP or data features) to partition the problem, allowing them to identify specific expertise (e.g., Learner A is better at detecting malware during specific time windows).
  • Distributed Context Zooming Algorithm (DCZA): An advanced approach that adaptively partitions the context space, "zooming in" on areas where data arrivals are frequent to allow for more granular expertise.
  • Three-Phase Learning: The algorithms utilize a Training phase (to learn about other nodes), an Exploration phase (to test local functions), and an Exploitation phase (to pick the best-known option).
  • Theoretical Rigor: The authors prove that their algorithms achieve sublinear regret, meaning the performance gap between the algorithm and an optimal theoretical strategy shrinks to zero over time.

Experimental Evaluation

The framework was evaluated using the KDD Cup 1999 network security dataset, simulating four local learners with different base classifiers (e.g., Naive Bayes, Decision Trees). The task was to predict whether a network connection was an "attack" or "normal" using features like srcbytes and time as context.

Key Results

  • Superiority over Ensembles: In non-stationary environments with concept drift, the proposed bandit algorithms outperformed established ensemble methods like AdaBoost. While AdaBoost combines all classifiers, the bandit approach learns to select the single best expert for a specific context.
  • Error Reduction: In simulations, the decentralized learning framework reduced error rates from 47% (best individual classifier) to approximately 38-39%. When using previous labels as context, the error rate dropped as low as 0.7%.
  • Efficiency: DCZA proved significantly more efficient than baseline algorithms by avoiding resource waste in regions of the context space where data rarely appears.

Discussion and Future Work

While the framework provides robust theoretical guarantees and handles concept drift effectively, it faces challenges regarding the "curse of dimensionality," as regret bounds scale exponentially with context dimensions. Future research directions include moving from selecting the single best learner to weighting an ensemble of learners within the bandit framework and dynamically learning network topology and link costs. Additionally, while the model accounts for the cost of sending data, further exploration of physical network protocol overhead is required for real-world deployment.

Summary updated

Abstract

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.
BibTeX
@misc{tekin2013decentralized,
  author = {Cem Tekin and Mihaela van der Schaar},
  title = {{Decentralized Online Big Data Classification - a Bandit Framework}},
  year = {2013},
  eprint = {1308.4565},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1308.4565},
}
Figure