Tracking Drifting Concepts Using Random Examples

Abstract

In this paper we consider the problem of tracking a subset of the domain (called the target) which changes gradually over time. A single (unknown) probability distribution over the domain is used to generate random examples for the learning algorithm, measure the speed at which the target changes, and measure the error of the algorithm's hypothesis. Clearly, the more rapidly the target moves, the harder it is for the algorithm to maintain a good approximation of the target. Therefore we evaluate algorithms based on how much movement of the target can be tolerated between examples while predicting with accuracy e. Furthermore, the complexity of the class of possible targets, as measured by d, its VC-dimension, also effects the difficulty of tracking the target concept. Our results include: bounds for the classes of axis-aligned halfspaces and hyperrectangles showing that for all d and e, no algorithm can tolerate target movement greater than c 1 e 2/d for some constant c 1; a generalpurpose (computationally inefficient) algorithm which tolerates target movement rates up to c 2 e2 /(d ln 1/e); and a second general purpose algorithm which tolerates target movement rates of up to c 3 e 3/(dln 1/e). The latter algorithm is computationally efficient whenever a hypothesis which approximately minimizes the observed error on a given sample can be found efficiently.