Learning under Concept Drift: an Overview

Concept drift refers to a non stationary learning problem over time. The training and the application data often mismatch in real life problems [61]. In this report we present a context of concept drift problem 1. We focus on the issues relevant to adaptive training set formation. We present the framework and terminology, and formulate a global picture of concept drift learners design. We start with formalizing the framework for the concept drifting data in Section 1. In Section 2 we discuss the adaptivity mechanisms of the concept drift learners. In Section 3 we overview the principle mechanisms of concept drift learners. In this chapter we give a general picture of the available algorithms and categorize them based on their properties. Section 5 discusses the related research fields and Section 5 groups and presents major concept drift applications. This report is intended to give a bird’s view of concept drift research field, provide a context of the research and position it within broad spectrum of research fields and applications. 1 Framework and Terminology For analyzing the problem of training set formation under concept drift, we adopt the following framework. A sequence of instances is observed, one instance at a time, not necessarily in equally spaced time intervals. Let Xt ∈ <p is a vector in p-dimensional feature space observed at time t and yt is the corresponding label. For classification yt ∈ Z1, for prediction yt ∈ <1. We call Xt an instance and a pair (Xt,yt) a labeled instance. We refer to instances (X1,...,Xt) as historical data and instance Xt+1 as target (or testing) instance. 1.1 Incremental Learning with Concept Drift We use incremental learning framework. At every time step t we have historical data (labeled) available XH = (X1,...,Xt). A target instance Xt+1 arrives. The task is to predict a label yt+1. For that we build a learner Lt, using all or a selection from the available historical data XH. We 1This is a working version, the categorization is in progress. The latest version of the report is available online