We present a distributed online learning scheme to classify data captured from distributed and dynamic data sources. Our scheme consists of multiple distributed local learners, which analyze different streams of data that are correlated to a common event that needs to be classified. Each learner uses a local classifier to make a local prediction. The local predictions are then collected by each learner and combined using a weighted majority rule to output the final prediction. We propose a novel online ensemble learning algorithm to update the aggregation rule in order to adapt to the underlying data dynamics. We rigorously determine an upper bound for the worst-case mis-classification probability of our algorithm, which tends asymptotically to 0 if the misclassification probability of the best (unknown) static aggregation rule is 0. Then we extend our algorithm to address challenges specific to the distributed implementation and prove new bounds that apply to these settings. Finally, we test our scheme by performing an evaluation study on several data sets. Index Terms-Big data, classification, concept drift, distributed learning, dynamic streams, ensemble of classifiers, machine learning, online learning. DYN: Dynamic data streams. Many existing ensemble schemes [7]- [11] assume that the data are generated from a stationary distribution, i.e., that the concept is stable [5] . Our scheme is developed and evaluated, both analytically and experimentally, considering the possibility that the data streams are dynamic, i.e., they may experience concept drift [5] . ONL: Online learning. To deal with dynamic data streams our scheme must learn the aggregation rule "on-the-fly". In this way the learners maintain an up-to-date aggregation rule and are able to track the concept drifts. COM: Low complexity. Some online ensemble learning schemes, such as [11]-[13], [18], need to collect and store chunks of data, which are later processed to update the aggregation model of the system. This requires a large memory and high computational capabilities, thereby resulting in high implementation cost. Different from these approaches, in our scheme each data is processed only once "on-arrival", thus data are not stored in the system. Only the up-to-date aggregation model is kept in the memory. The local prediction of each learner, which is the only information that must be exchanged, consists of a binary value. Moreover, our scheme is scalable to a large number of sources and learners and the learners can be chained in any hierarchical structure. IND: Independence from local classifiers. Different from [15], [16] , [19] , our scheme is general and can be applied to different types of local classifiers, such as support vector machine, decision tree, neural networks, offline/online classifiers, etc. This feature is important, because the different learners can be managed by different entities, willing to cooperate in exchanging information but not to modify their own local classifiers. Also, our algorithm does not need any a priori knowledge about the performance of the local classifiers, it automatically adapts the configuration of the distributed system to the current performance of the local classifiers. DEL: Delayed labels, missing labels, and asynchronous learners. In distributed environments there are many factors that may impact the performance of the learning system. First, because obtaining the information about the label may be both costly and time consuming, one cannot expect that all the learners always observe the label in a timely manner. Some learners can receive the label with delay, or not receive it at all. Second, the learners can be asynchronous, i.e., they can observe data at different time instants. In this paper we first propose a basic algorithm, considering an idealized scenario in which the above issues are not present, and then we extend our scheme to deal with the above issues. The rest of this paper is organized as follows. Section II reviews the existing literature in ensemble learning techniques. Section III presents our formalism, framework, and algorithm for distributed online learning. Section IV proves a bound for the mis-classification probability of our scheme which depends on the mis-classification probabilities of the best (unknown) static aggregation rule, and of the best (unknown) local classifier. Section V discusses several extensions to our learning algorithm to deal with practical issues associated to the distributed implementation of the ensemble of learners, and proves new bounds that apply to these settings. Section VI presents the empirical evaluation of our algorithm on several data sets. Section VII concludes the paper. Luca Canzian received the B.Sc., M.Sc., and Ph.D. degrees in electrical engineering from
Canzian et al. REF obtained the final classification decision by collecting the local predictions of all learners and combining them using a perceptron weighted majority.
Ensemble of distributed learners for online classification of dynamic data streams
IEEE Transactions on Signal and Information Processing over Networks
IEEE Transactions on Signal and Information Processing over Networks
Mathematics Computer Science