Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-069 | 14th July 2000 00:00

Learning Nested Differences in the Presence of Malicious Noise


Authors: Peter Auer
Publication: 12th September 2000 20:19
Downloads: 1172


We present a PAC-learning algorithm and an on-line learning algorithm
for nested differences of intersection-closed classes. Examples of
intersection-closed classes include axis-parallel rectangles,
monomials, and linear sub-spaces. Our PAC-learning algorithm uses a
pruning technique that we rigorously proof correct. As a result we
show that the tolerable noise rate for this algorithm does not
depend on the complexity (VC-dimension) of the target class but only
on the VC-dimension of the underlying intersection-closed class. For
our on-line algorithm we show an optimal mistake bound in the sense
that there are concept classes for which each on-line learning
algorithm (using nested differences as hypotheses) can be forced to
make at least that many mistakes.

ISSN 1433-8092 | Imprint