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.

Google ScholarTM

Check

Altmetric


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