|
NeuroCOLT
Technical Report NC-TR-96-019
Learning Nested
Differences in the Presence of Malicious Noise
Peter
Auer
Institute for Theoretical Computer Science
Technische Universitaet Graz
Austria
Abstract
We investigate the learnability of nested differences of intersection-closed
classes in the presence of malicious noise. Examples of intersection-closed
classes include axis-parallel rectangles, monomials, linear sub-spaces,
and so forth. We present an on-line algorithm whose mistake bound
is optimal in the sense that there are concept classes for which each
learning algorithm (using nested differences as hypotheses) can be
forced to make at least that many mistakes. We also present an algorithm
for learning in the PAC model with malicious noise. Surprisingly enough,
the noise rate tolerable by these algorithms does not depend on the
complexity of the target class but depends only on the complexity
of the underlying intersection-closed class.
Download Compressed
Postscript
|