Learnability and the Vapnik-Chervonenkis dimension

In this paper we extend Valiant's model to learning concepts defined by regions in Euclidean n-dimensional space E", n 2 1. The general techniques we develop lead to new results in Boolean domains as well. Our methods are based on the pioneering work of Vapnik and Chervonenkis [6 I-631 on the distribution-free convergence of empirical probability estimates and its application to the theory of pattern recognition. These methods provide a unified treatment of some of Valiant's results, and extend previous results of Pearl [50, 5 I] and Devroye and Wagner ([ 151, see also [ 141) along with our results from [lo]. In learning a class C of concepts (e.g., subsets of E") from examples, a single target concept is selected from C and we are given a finite sequence of points in E", each labeled " 1" if it is in the target concept (a positive example) and "0" if it is not (a negative example). This set is called a sample of the target concept. A learning function for C is a function that, given a large enough randoml:y drawn sample of any target concept in C, returns a region in E" (a hypothesis) that is with high probability a good approximation to the target concept. More precisely: (1) We let P be a fixed probability distribution on E" and assume that examples are created by drawing points independently at random according to P. (2) The error of a hypothesis is taken to be the probability that it disagrees with the target concept on a randomly drawn example, that is, the error is just the probability (according to P) of the symmetric difference between the hypothesis and the target concept.