|
NeuroCOLT
Technical Report NC-TR-95-032
Characterizations
of Learnability for Classes
of {0,...,n}-valued Functions
Shai
Ben-David
Technion, Israel
Nicolò
Cesa-Bianchi
Università di Milano, Italy
David
Haussler
University of California at Santa Cruz, USA
Philip
M. Long
Duke University, USA
Abstract
We investigate the PAC learnability of classes of $\sn$-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
a 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.
Download Compressed
Postscript
|