Scale-sensitive dimensions, uniform convergence, and learnability

ABSTRACT

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or “agnostic”) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.

REFERENCES

• 1: ALON, N., AND MILMAN, V. 1983. Embedding of 1k in finite dimension Banach spaces. Israel J. Math. 45, 265-280.
• 2: ASSOUAD, P., AND DUDLEY, R. 1989. Minimax nonparametric estimation over classes of sets. Preprint.
• 3: Peter L. Bartlett , Philip M. Long, More theorems about scale-sensitive dimensions and learning, Proceedings of the eighth annual conference on Computational learning theory, p.392-401, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225346]
• 4: Peter L. Bartlett , Philip M. Long , Robert C. Williamson, Fat-shattering and the learnability of real-valued functions, Journal of Computer and System Sciences, v.52 n.3, p.434-452, June 1996 [doi>10.1006/jcss.1996.0033]
• 5: Shai Ben-David , Nicolò Cesa-Bianchi , David Haussler , Philip M. Long, Characterizations of learnability for classes of {0, …, n}-valued functions, Journal of Computer and System Sciences, v.50 n.1, p.74-86, Feb. 1995 [doi>10.1006/jcss.1995.1008]
• 6: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 7: K. L. Collins , P. W. Shor , J. R. Stembridge, A lower bound for 0,1, * tournament codes, Discrete Mathematics, v.63 n.1, p.15-19, Jan. 1987 [doi>10.1016/0012-365X(87)90147-6]
• 8: DUDLEY, R. 1984. A course on empirical processes. In Lecture Notes in Mathematics, vol. 1097. Springer-Verlag, New York, pp. 2-142.
• 9: DUDLEY, R., GIN#, E., AND ZINN, J. 1991. Uniform and universal Glivenko-Cantelli classes. J. Theoret. Prob. 4, 485-510.
• 10: GINI#, E., AND ZINN, J. 1984. Some limit theorems for empirical processes. Ann. Prob. 12, 929-989.
• 11: GUYON, I., VAPNIK, g., BOSER, B., BOTTOU, L., AND SOLLA, S. 1991. Structural risk minimization for character recognition. In Proceedings of the 1991 Conference on Advances in Neural Information Processing Systems. pp. 471-479.
• 12: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 13: David Haussler , Philip M. Long, A generalization of Sauer's lemma, Journal of Combinatorial Theory Series A, v.71 n.2, p.219-240, Aug. 1995 [doi>10.1016/0097-3165(95)90001-2]
• 14: Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
• 15: MILMAN, g. 1982. Some remarks about embedding of 1k in finite dimensional spaces. Israel J. Math. 43, 129-138.
• 16: POLLARD, D. 1990. Empirical Processes: Theory and Applications, Volume 2 of NSF-CBMS Regional Conference Series in Probability and Statistics. Institute of Mathematical Statistics and American Statistical Association.
• 17: RISSANEN, J. 1978. Modeling by shortest data description. Automatica 14, 465-471.
• 18: SAUER, N. 1972. On the density of families of sets. J. Combin. Theory, Ser. A 13, 145-147.
• 19: SHELAH, S. 1972. A combinatorial problem: Stability and order for models and theories in infinitary languages. Pac. J. Math. 41, 247-261.
• 20: Hans Ulrich Simon, Bounds on the number of examples needed for learning functions, Proceedings of the first European conference on Computational learning theory, p.83-94, October 1994, Royal Holloway, Univ. of London, United Kingdom
• 21: VAN LINT, J. 1985. {0, 1, *} distance problems in combinatorics. In Lecture Notes of London Mathematical Society, vol. 103, Cambridge University Press, Cambridge, England, pp. 113-135.
• 22: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 23: V. N. Vapnik, Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures), Proceedings of the second annual workshop on Computational learning theory, p.3-21, December 1989, Santa Cruz, California, United States
• 24: VAPNIK, g., AND CHERVONENKIS, A. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Prob. Its Applic. 16, 2, 264-280.
• 25: VAPNIK, g., AND CHERVONENKIS, A. 1981. Necessary and sufficient conditions for uniform convergence of means to mathematical expectations. Theory Prob. Applic. 26, 3, 532-553.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Theory

Keywords:
PAC learning, Vapnik-Chervonenkis dimension, uniform laws of large numbers