期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
