Using additive expert ensembles to cope with concept drift

ABSTRACT

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.

REFERENCES

• 1: Avrim Blum, Empirical Support for Winnow and Weighted-MajorityAlgorithms: Results on a Calendar Scheduling Domain, Machine Learning, v.26 n.1, p.5-23, Jan. 1997 [doi>10.1023/A:1007335615132]
• 2: Olivier Bousquet , Manfred K. Warmuth, Tracking a small set of experts by mixing past posteriors, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 4: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 5: Haussler, D., Kivinen, J., & Warmuth, M. (1998). Sequential predictions of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44, 1906--1925.
• 6: David P. Helmbold , Philip M. Long, Tracking Drifting Concepts By Minimizing Disagreements, Machine Learning, v.14 n.1, p.27-45, Jan. 1994 [doi>10.1023/A:1022694620923]
• 7: Mark Herbster , Manfred K. Warmuth, Tracking the Best Expert, Machine Learning, v.32 n.2, p.151-178, Aug. 1998 [doi>10.1023/A:1007424614876]
• 8: Jeremy Z. Kolter , Marcus A. Maloof, Dynamic Weighted Majority: A New Ensemble Method for Tracking Concept Drift, Proceedings of the Third IEEE International Conference on Data Mining, p.123, November 19-22, 2003
• 9: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 10: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 11: Monteleoni, C., & Jaakkola, T. S. (2004). Online learning of non-stationary sequences. Proceedings of the 16th NIPS Conference. MIT Press.
• 12: Schlimmer, J., & Granger, R. (1986). Beyond incremental processing: Tracking concept drift. Proceedings of the 5th AAAI Conference (pp. 502--507). AAAI Press.
• 13: W. Nick Street , YongSeog Kim, A streaming ensemble algorithm (SEA) for large-scale classification, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.377-382, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502568]
• 14: Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
• 15: V. Vovk, A game of prediction with expert advice, Journal of Computer and System Sciences, v.56 n.2, p.153-173, April 1998 [doi>10.1006/jcss.1997.1556]
• 16: Gerhard Widmer , Miroslav Kubat, Learning in the presence of concept drift and hidden contexts, Machine Learning, v.23 n.1, p.69-101, April 1996 [doi>10.1023/A:1018046501280]