Please use this identifier to cite or link to this item:
|Title:||On the Complexity of Learning from Drifting Distributions||Authors:||Barve, R.D.
|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||URI:||http://scholarbank.nus.edu.sg/handle/10635/99361||ISSN:||08905401|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 7, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.