Using additive expert ensembles to cope with concept drift

Jeremy Z. Kolter and Marcus A. Maloof

We consider online learning where the target concept can change over time. Previous work on expert prediction algorithms has bounded the worst-case performance on any subsequence of the training data relative to the performance of the best expert. However, because these "experts" may be difficult to implement, we take a more general approach and bound performance relative to the actual performance of any online learner on this single subsequence. We present the additive expert ensemble algorithm AddExp, a new, general method for using any online learner for drifting concepts. We adapt techniques for analyzing expert prediction algorithms to prove mistake and loss bounds for a discrete and a continuous version of AddExp. Finally, we present pruning methods and empirical results for data sets with concept drift.

Paper available in PDF.

Kolter, J. Z., & Maloof, M. A. (2005). Using additive expert ensembles to cope with concept drift. In Proceedings of the Twenty-second International Conference on Machine Learning, 449–456. New York, NY: ACM Press.

@inproceedings{kolter.icml.05,
  author = "Jeremy Z. Kolter and Marcus A. Maloof",
  title = "Using additive expert ensembles to cope with concept drift",
  booktitle = "{Proceedings of the Twenty-second International Conference
    on Machine Learning}",
  year = 2005,
  pages = "449--456",
  publisher = "ACM Press",
  address = "New York, NY",
  annote = {
  }}