Learning nested differences in the presence of malicious noise

Author: Peter Auer.
Email: pauer@igi.tu-graz.ac.at

Source: Theoretical Computer Science Vol. 185, No. 1, 1997, 159-175.

Abstract. 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.