S. Ben-David, N. Cesa-Bianchi, D. Haussler and P. M. Long.
Characterizations of the learnability of {0,...,n}-valued
functions. Journal
of Computer and System Sciences, 50(1):74-86, 1995.
(Available in Postscript and PDF formats.)
Abstract
We investigate the PAC learnability of classes of
{0,...n}-valued functions (n <> 1). For
n = 1 it is known that the finiteness
of the VapnikChervonenkis dimension is necessary and
sufficient for learning. For n > 1
several generalizations of the VCdimension, 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 VCdimension, 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.