Please use this identifier to cite or link to this item:
https://doi.org/10.1023/A:1007666507971
Title: | Complexity of learning according to two models of a drifting environment | Authors: | Long, P.M. | Issue Date: | 1999 | Citation: | Long, P.M. (1999). Complexity of learning according to two models of a drifting environment. Machine Learning 37 (3) : 337-354. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1007666507971 | Abstract: | We show that a cε3/VC dim(F) bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy ε, where c>0 is a constant; this matches a known necessary condition to within a constant factor. We establish a cε2/VC dim (F) sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor . We provide a relatively simple proof of a bound of O(1/ε2(VC dim (F)+log 1/δ)) on the sample complexity of agnostic learning in a fixed environment. | Source Title: | Machine Learning | URI: | http://scholarbank.nus.edu.sg/handle/10635/39144 | ISSN: | 08856125 | DOI: | 10.1023/A:1007666507971 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.