Authors: Peter Auer and Nicolò Cesa-Bianchi.
Email: wiehagen@informatik.uni-kl.de
Source: Annals of Mathematics and Artificial Intelligence Vol. 23, No. 1-2, 1998, 83-99.
Abstract. We investigate a variant of the on-line learning model for classes of {0,1}-valued functions (concepts) in which the labels of a certain amount of the input instances are corrupted by adversarial noise. We propose an extension of a general learning strategy, known as ``Closure Algorithm'', to this noise model, and show a worst-case mistake bound of m + (d+1)K for learning an arbitrary intersection-closed concept class C, where K is the number of noisy labels, d is a combinatorial parameter measuring C's complexity, and m is the worst-case mistake bound of the Closure Algorithm for learning C in the noise-free model. For several concept classes our extended Closure Algorithm is efficient and can tolerate a noise rate up to the information-theoretic upper bound. Finally, we show how to efficiently turn any algorithm for the on-line noise model into a learning algorithm for the PAC model with malicious noise.
©Copyright 1998 Baltzer Science Publishers