|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-99-035
Sample-efficient
Strategies for Learning in the Presence of Noise
Cesa-Bianchi, Dichterman, Fischer, Shamir & Simon
Abstract
In this paper we prove various results about PAC learning in the presence
of malicious noise. Our main interest is the sample size behaviour
of learning algorithms. We prove the first nontrivial sample complexity
lower bound in this model by showing that order of e /D 2 + d/D (up
to logarithmic factors) examples are necessary for PAC learning any
target class of {0,1} valued functions of VC dimension d, where e
is the desired accuracy and h = e /(1+e ) - D the malicious noise
rate (it is well known that any nontrivial target class cannot be
PAC learned with accuracy e and malicious noise rate h= e /(1+e ),
this irrespective to sample complexity). We also show that this result
cannot be significantly improved in general by presenting efficient
learning algorithms for the class of all subsets of d elements and
the class of unions of at most d intervals on the real line. This
is especially interesting as we can also show that the popular minimum
disagreement strategy needs samples of size de /D 2, hence is not
optimal with respect to sample size. We then discuss the use of randomized
hypotheses. For these the bound e /(1+e ) on the noise rate is no
longer true and is replaced by 2e /(1+2e ). In fact, we present a
generic algorithm using randomized hypotheses which can tolerate noise
rates slightly larger than e /(1+e ) while using samples of size d/e
as in the noise-free case. Again one observes a quadratic powerlaw
(in this case de /D 2, D = 2e /(1+2e ) -h ) as D goes to zero. We
show upper and lower bounds of this order.
Download Compressed Postscript
|