Characterizations of learnability for classes of {O, …, n}-valued functions

ABSTRACT

We investigate the PAC learnability of classes of {0,…,n}-valued functions. For n = 1, it is known that the finiteness of the Vapnik-Chervonenkis dimension is necessary and sufficient for learning. In this paper we present a general scheme for extending the VC-dimension to the case n > 1. Our scheme defines a wide variety of notions of dimension in which several variants of the VC-dimension, previously introduced in the context of learning, appear as special cases. Our main result is a simple condition characterizing the set of notions of dimension whose finiteness is necessary and sufficient for learning. This provides a variety of new tools for determining the learnability of a class of multi-valued functions. Our characterization is also shown to hold in the “robust” variant of PAC model.

REFERENCES

• Alo83: N. Alon. On the density of sets of vectors. Discrete Mathematics, 24:177-184, 1983.
• BEHW89: 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]
• Dud87: R.M. Dudley. Universal donsker classes and metric entropy. Ann. Prob., 15(4):1306- 1326, 1987.
• EHKV89: Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
• Hau91: David Haussler, DECISION THEORETIC GENERALIZATIONS OF THE PAC MODEL FORNEURAL NET AND OTHER LEARNING APPLICATIONS, University of California at Santa Cruz, Santa Cruz, CA, 1990
• HL90: David Haussler , Phil Long, A GENERALIZATION OF SAUER''S LEMMA, University of California at Santa Cruz, Santa Cruz, CA, 1990
• Nat89: B. K. Natarajan, On Learning Sets and Functions, Machine Learning, v.4 n.1, p.67-97, October 1989 [doi>10.1023/A:1022605311895]
• Pol84: D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984.
• Pol90: D. Pollard. Empirical Processes: Theory and Applications. Institute of Mathematical Statistics, 1990.
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Vap89: 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
• VC71: V.N. Vapnik and A.Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory, Verification