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.

SCOPUSTM   
Citations

49
checked on Dec 3, 2018

WEB OF SCIENCETM
Citations

36
checked on Nov 26, 2018

Page view(s)

40
checked on Dec 7, 2018

Google ScholarTM

Check

Altmetric


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