Characterizations of Learnability for Classes of {O, ..., n}-Valued Functions

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

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.
BibTeX
@inproceedings{bendavid1992characterizations,
  author = {Shai Ben-David and Nicolò Cesa-Bianchi and Philip M. Long},
  title = {{Characterizations of Learnability for Classes of \{O, ..., n\}-Valued Functions}},
  booktitle = {Conference on Learning Theory},
  year = {1992},
  doi = {10.1145/130385.130423},
}

Loading related content...

Figure