Please use this identifier to cite or link to this item:
|Title:||Fat-shattering and the learnability of real-valued functions|
|Citation:||Bartlett, P.L., Long, P.M., Williamson, R.C. (1996-06). Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences 52 (3) : 434-452. ScholarBank@NUS Repository. https://doi.org/10.1006/jcss.1996.0033|
|Abstract:||We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide characterizations of the learnability of a real-valued function class in terms of a generalization of the Vapnik-Chervonenkis dimension, the fat-shattering function, introduced by Kearns and Schapire. We show that, given some restrictions on the noise, a function class is learnable in our model if an only if its fat-shattering function is finite. With different (also quite mild) restrictions, satisfied for example by guassion noise, we show that a function class is learnable from polynomially many examples if and only if its fat-shattering function grows polynomially. We prove analogous results in an agnostic setting, where there is no assumption of an underlying function class. © 1996 Academic Press, Inc.|
|Source Title:||Journal of Computer and System Sciences|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 25, 2018
WEB OF SCIENCETM
checked on Sep 17, 2018
checked on Sep 21, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.