Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions. (English) Zbl 0827.68095

Ben-David, Shai; Cesa-Bianchi, Nicolò; Haussler, David; Long, Philip M.

J. Comput. Syst. Sci. 50, No. 1, 74-86 (1995).

Summary: We investigate the PAC learnability of classes of \(\{0, \dots, n\}\)- valued functions \((n < \infty)\). For \(n = 1\) it is known that the finiteness of the Vapnik-Chervonenkis dimension is necessary and sufficient for learning. For \(n > 1\) several generalizations of the VC- dimension, each yielding distinct characterization of learnability, have been proposed by a number of researchers. 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 all these 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 and for any “reasonable” loss function.

MSC:

68T05

Learning and adaptive systems in artificial intelligence

Keywords:

PAC learnability; Vapnik-Chervonenkis dimension; VC-dimension