Meta Expert Learning and Efficient Pruning for Evolving Data Streams

摘要

Researchers have proposed several ensemble methods for the data stream environments including online bagging and boosting. These studies show that bagging methods perform better than boosting methods although the opposite is known to be true in the batch setting environments. The reason behind the weaker performance of boosting methods in the streaming environments is not clear. We have taken advantage of the algorithmic procedure of meta expert learnings for the sake of our study. The expert learning differs from the classic expert learning methods in that each expert starts to predict from a different point in the history. Moreover, maintaining a collection of base learners follows an procedure. The focus of this paper is on studying the pruning function for maintaining the appropriate set of experts rather than proposing a competitive algorithm for selecting the experts. It shows how a well-structured pruning method leads to a better prediction accuracy without necessary higher memory consumption. Next, it is shown how pruning the set of base learners in the meta expert learning (in order to avoid memory exhaustion) affects the prediction accuracy for different types of drifts. In the case of time-locality drifts, the prediction accuracy is highly tied to the mathematical structure of the pruning algorithms. This observation may explain the main reason behind the weak performance of previously studied boosting methods in the streaming environments. It shows that the boosting algorithms should be designed with respect to the suitable notion of the regret metrics.