# zbMATH — the first resource for mathematics

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.

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