1992/07/01 by Shai Ben-David, Nicolò Cesa‐Bianchi, Philip M. Long · 1 citation
Computer Science · Mathematics · #Machine Learning and Algorithms #Computability, Logic, AI Algorithms #Optimization and Search Problems #Learnability #VC dimension #Dimension (graph theory) #Variety (cybernetics) #Context (archaeology) #Concept class #Class (philosophy) #Mathematics #Set (abstract data type) #Theoretical computer science #Computer science #Simple (philosophy) #Discrete mathematics #Scheme (mathematics) #Artificial intelligence #Combinatorics #Programming language
paper · doi:10.1145/130385.130423
openalex publication_date 1992/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.