Detecting and Adapting to Concept Drift in Continually Evolving Stochastic Processes

ABSTRACT

Many real world stochastic processes are non-stationary, which means that the probability distribution that generates data samples is time-varying. In the context of machine learning, this phenomenon is known as concept drift. It is important that machine learning models are able to adapt to concept drift in order to prevent degradation in accuracy. In this paper, we present two algorithms for drift detection and adaptation.

Drift is measured by continuously tracking a difference metric between probability distributions estimated from two sample windows preceding a time point. High values for the difference metric indicates that concept drift has occurred, and the model must be adapted. Adaptation is done by training a new model for the drifted process, and adding it to an ensemble of models. Previously trained models are retained, and their weights in the ensemble are adjusted to reflect similarity with the current probability distribution of the process. Experiments on simulated drift scenarios as well as real world datasets show that our algorithms detect drift with high accuracy, and adaptation results in improved model accuracy.

References

1. Webb, Geoffrey I., et al. "Understanding Concept Drift." arXiv preprint arXiv:1704.00362 (2017).
2. Gama, Joao, et al. "Learning with drift detection." Brazilian Symposium on Artificial Intelligence. Springer, Berlin, Heidelberg, 2004.
3. Žliobaitė, Indrė. "Learning under concept drift: an overview." arXiv preprint arXiv:1010.4784 (2010).
4. Tsymbal, Alexey. "The problem of concept drift: definitions and related work." Computer Science Department, Trinity College Dublin 106.2 (2004).
5. Street, W. Nick, and 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. ACM, 2001.
6. Wang, Haixun, et al. "Mining concept-drifting data streams using ensemble classifiers." Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. AcM, 2003.
7. I. Koychev. Koychev, Ivan. "Gradual forgetting for adaptation to concept drift." Proceedings of ECAI 2000 Workshop on Current Issues in Spatio-Temporal Reasoning, 2000.
8. Zhang, Peng, Xingquan Zhu, and Yong Shi. "Categorizing and mining concept drifting data streams." Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008.
9. Scholz, Martin, and Ralf Klinkenberg. "An ensemble classifier for drifting concepts." Proceedings of the Second International Workshop on Knowledge Discovery in Data Streams. Porto, Portugal, 2005.
10. Royer, Amelie, and Christoph H. Lampert. "Classifier adaptation at prediction time." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2015.
11. Hoffman, Judy, Trevor Darrell, and Kate Saenko. "Continuous manifold based adaptation for evolving visual domains." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014.
12. Levinkov, Evgeny, and Mario Fritz. "Sequential Bayesian model update under structured scene prior for semantic road scenes labeling." Proceedings of the IEEE International Conference on Computer Vision. 2013.
13. Levin, David Asher, Yuval Peres, and Elizabeth Lee Wilmer. Markov chains and mixing times. American Mathematical Soc., 2009.
14. Michael Harries. Splice-2 comparative evaluation: Electricity pricing. Technical report
15. Bifet, Albert, and Ricard Gavalda. "Learning from time-changing data with adaptive windowing." Proceedings of the 2007 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2007.
16. Raykar, Vikas C., Ramani Duraiswami, and Linda H. Zhao. "Fast computation of kernel estimators." Journal of Computational and Graphical Statistics 19.1 (2010): 205--220.
17. Elgammal, Ahmed, Ramani Duraiswami, and Larry S. Davis. "Efficient kernel density estimation using the fast gauss transform with applications to color modeling and tracking." IEEE transactions on pattern analysis and machine intelligence 25.11 (2003): 1499--1504.

Index Terms

• Computing methodologies

  • Machine learning