UCSC-CRL-93-31: CHARACTERIZATIONS OF LEARNABILITY FOR CLASSES OF {0,...,N}-VALUED FUNCTIONS

08/01/1993 09:00 AM
Computer Science
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 and for any \"reasonable\" loss function.

UCSC-CRL-93-31