Can I read On the Complexity of Learning from Drifting Distributions on EtoBox?

On the Complexity of Learning from Drifting Distributions by Rakesh D. Barve; Philip M. Long is a scholarly article available to read on EtoBox.

What is On the Complexity of Learning from Drifting Distributions about?

We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in total variation distance by at most O(C3 / (d log(l/e))) between trials, then an algorithm can achieve a probability of a mistake at most c worse than the best function in a class of VC-dimension d. We prove a corresponding necessary condition of 0(c3 /d). Finally, in the case that a fixed function is to be learned from noise-free examples, we show that if the distributions on the domain generating the examples change by at most 0(c2 / (d log(l/e) ) ), then any consistent algorithm learns to within accuracy c. both introduced by Bartlett [3]. In the first model, the pairs (x1,1 h), (z2, y2), . . . are generated independently from a sequence PI, P2, . . . of distributions on X x {O, 1}, and it is assumed that pairs of consecutive distributions are close. If, for a class F of functions from X to {O, 1}, there is a learning algorithm that, for large enough t, whenever the distribution changes by at most -y in total variation distance between trials, the algorithm achievesPermission to make di

Author

Rakesh D. Barve; Philip M. Long

Publisher

ACM Press

Published

1996

Language

EN