Characterizations of Learnability for Classes of {0, ..., n)-Valued Functions

✍ Scribed by S. Bendavid; N. Cesabianchi; D. Haussler; P.M. Long

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 885 KB
• Volume: 50
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1995.1008

✦ Synopsis

We investigate the PAC learnability of classes of ({0, \ldots, n})-valued functions ((n<\infty)). For (n=1) it is known that the finiteness of the Vapnik-Chervonenkis dimension is necessary and sulficient 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 (V C)-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. 1995 Academic Press, Inc.