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.