UCSC-CRL-98-12: TRACKING A DRIFTING CONCEPT IN A CHANGING ENVIRONMENT

03/01/1998 09:00 AM
Computer Engineering
We consider the problem of predicting the labels of randomly chosen points, when both the probability distribution generating the points and the target concept are allowed to change slowly. More precisely, we assume that the total variation distance between consecutive probability distributions is small, and that the probability (under the current distribution) of disagreement between consecutive target concepts is small. We describe a general- purpose algorithm that can cope with combined distribution and concept drift, and has asymptotic prediction error within a log factor of the best that can be achieved by any algorithm, even when either the distribution or the concept is held constant. In addition, we give upper bounds on the cumulative prediction error of a related algorithm when we assume that there is a bound on the average drift over a sequence of trials. We also consider learning in an agnostic setting, with a slowly changing joint probability distribution on the domain and the output space {0,1}, and give bounds on the excess mistake probability of a tracking strategy in this setting.

UCSC-CRL-98-12