TY - JOUR

T1 - Learning changing concepts by exploiting the structure of change

AU - Bartlett, Peter L.

AU - Ben-David, Shai

AU - Kulkarni, Sanjeev R.

PY - 2000/11/1

Y1 - 2000/11/1

N2 - This paper examines learning problems in which the target function is allowed to change. The learner sees a sequence of random examples, labelled according to a sequence of functions, and must provide an accurate estimate of the target function sequence. We consider a variety of restrictions on how the target function is allowed to change, including infrequent but arbitrary changes, sequences that correspond to slow walks on a graph whose nodes are functions, and changes that are small on average, as measured by the probability of disagreements between consecutive functions. We first study estimation, in which the learner sees a batch of examples and is then required to give an accurate estimate of the function sequence. Our results provide bounds on the sample complexity and allowable drift rate for these problems. We also study prediction, in which the learner must produce online a hypothesis after each labelled example and the average misclassification probability over this hypothesis sequence should be small. Using a deterministic analysis in a general metric space setting, we provide a technique for constructing a successful prediction algorithm, given a successful estimation algorithm. This leads to sample complexity and drift rate bounds for the prediction of changing concepts.

AB - This paper examines learning problems in which the target function is allowed to change. The learner sees a sequence of random examples, labelled according to a sequence of functions, and must provide an accurate estimate of the target function sequence. We consider a variety of restrictions on how the target function is allowed to change, including infrequent but arbitrary changes, sequences that correspond to slow walks on a graph whose nodes are functions, and changes that are small on average, as measured by the probability of disagreements between consecutive functions. We first study estimation, in which the learner sees a batch of examples and is then required to give an accurate estimate of the function sequence. Our results provide bounds on the sample complexity and allowable drift rate for these problems. We also study prediction, in which the learner must produce online a hypothesis after each labelled example and the average misclassification probability over this hypothesis sequence should be small. Using a deterministic analysis in a general metric space setting, we provide a technique for constructing a successful prediction algorithm, given a successful estimation algorithm. This leads to sample complexity and drift rate bounds for the prediction of changing concepts.

UR - http://www.scopus.com/inward/record.url?scp=0034320912&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034320912&partnerID=8YFLogxK

U2 - 10.1023/A:1007604202679

DO - 10.1023/A:1007604202679

M3 - Article

AN - SCOPUS:0034320912

VL - 41

SP - 153

EP - 174

JO - Machine Learning

JF - Machine Learning

SN - 0885-6125

IS - 2

ER -