Please use this identifier to cite or link to this item:
Title: On the Complexity of Learning from Drifting Distributions
Authors: Barve, R.D.
Long, P.M. 
Issue Date: 1-Nov-1997
Citation: Barve, R.D.,Long, P.M. (1997-11-01). On the Complexity of Learning from Drifting Distributions. Information and Computation 138 (2) : 170-193. ScholarBank@NUS Repository.
Abstract: 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(∈3/(d log(1/∈))) between trials, then an algorithm can achieve a probability of a mistake at most ∈ worse than the best function in a class of VC-dimension d. We prove a corresponding necessary condition of O(∈3/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 O(∈2/(d log(1/∈))), then any consistent algorithm learns to within accuracy ∈. © 1997 Academic Press.
Source Title: Information and Computation
ISSN: 08905401
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Sep 7, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.