Please use this identifier to cite or link to this item:
https://doi.org/10.1006/jcss.1996.0033
Title: | Fat-shattering and the learnability of real-valued functions | Authors: | Bartlett, P.L. Long, P.M. Williamson, R.C. |
Issue Date: | Jun-1996 | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/99288 | ISSN: | 00220000 | DOI: | 10.1006/jcss.1996.0033 |
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.