Preliminary versionA preliminary version of these results was presented in: Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. In 34th Annual Symposium on Foundations of Computer Science, pages 292-301, Palo Alto, California, 3-5 November 1993. IEEE.
Categories and Subject Descriptors: I.2.6 [Artificial Intelligence]: Learning -- concept learning
General Terms: Theory
Additional Key Words and Phrases: PAC learning, uniform laws of large numbers, Vapnik-Chervonenkis dimension
Selected references
- Peter L. Bartlett, Philip M. Long, and Robert C. Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434-452, June 1996.
- Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, ..., n}-valued functions. Journal of Computer and System Sciences, 50(1):74-86, February 1995.
- Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, October 1989.
- David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-150, September 1992.
- Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464-497, June 1994.