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

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.


68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI