Approximating hyper-rectangles
Peter L. Auer, Philip M. Long, Aravind Srinivasan · ACM Symposium on Theory of Computing (STOC) · 1997
The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for severaf applied learning problems.Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subpmblem common to the derandomization of depth-2 (DIW) circuits and derandotnizing Randomized Logspace, and (ii) they approximate the distribution of n independent multivalued random variables.We present improved upper bounds for a class of such problems of "approximating" highdlmensional rectangles that arise in PAC learning and pseudorandomness.Key words and phrases.Rectangles, machine learning, PAC learning,
Cited by 49 works. doi:10.1145/258533.258611 Open-access PDF
Authors
References
- A Theory of the Learnable
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Universal classes of hash functions
- The Probabilistic Method
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Learnability and the Vapnik-Chervonenkis dimension
- Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
- Convergence of Stochastic Processes.
- Solving the multiple instance problem with axis-parallel rectangles
- Computational limitations on learning from examples