ECCC-Report TR00-069https://eccc.weizmann.ac.il/report/2000/069Comments and Revisions published for TR00-069en-usTue, 12 Sep 2000 20:19:35 +0300
Paper TR00-069
| Learning Nested Differences in the Presence of Malicious Noise |
Peter Auer
https://eccc.weizmann.ac.il/report/2000/069We 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.
Tue, 12 Sep 2000 20:19:35 +0300https://eccc.weizmann.ac.il/report/2000/069