ECCC-Report TR00-063https://eccc.weizmann.ac.il/report/2000/063Comments and Revisions published for TR00-063en-usSat, 26 Aug 2000 17:51:55 +0300
Paper TR00-063
| On-line Learning of Rectangles in Noisy Environments |
Peter Auer
https://eccc.weizmann.ac.il/report/2000/063We 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.
Sat, 26 Aug 2000 17:51:55 +0300https://eccc.weizmann.ac.il/report/2000/063