__
TR00-063 | 13th July 2000 00:00
__

#### On-line Learning of Rectangles in Noisy Environments

TR00-063
Authors:

Peter Auer
Publication: 26th August 2000 17:51

Downloads: 2863

Keywords:

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