Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-063 | 13th July 2000 00:00

On-line Learning of Rectangles in Noisy Environments


Authors: Peter Auer
Publication: 26th August 2000 17:51
Downloads: 3361


We investigate the implications of noise in the equivalence query
model. Besides some results for general target and hypotheses
classes, we prove bounds on the learning complexity of d-dimensional
discretized rectangles in the case where only rectangles are allowed
as hypotheses.
Our noise model assumes that a certain fraction of the examples is
noisy. We show that d-dimensional rectangles are learnable if and
only if the fraction of noisy examples is less than 1/(d+1), where
learnable means that the learner can learn the target by a finite
number of examples.
Besides this structural result we present an algorithm which learns
rectangles in polynomial time if the fraction of noise r is less
than 1/(2d+1).
As a related result we prove for the noise-free case that the number
of examples necessary to learn is at most a factor 1/(log d) less
than the best known upper bound on the learning complexity.

ISSN 1433-8092 | Imprint