Space-Bounded Learning and the Vapnik-Chervonenkis Dimension

Abstract

This paper explores algorithms that learn a concept from a concept class of Vapnik-Chervonenkis (VC) dimension d by saving at most d examples at a time. The framework is the model of learning introduced by Valiant [V84]. A maximum concept class of VC dimension d is defined. For a maximum class C of VC dimension d, we give an algorithm for representing a finite set of positive and negative examples of a concept by a subset of d labeled examples of that set. This data compression scheme of size d is used to construct a space-bounded algorithm that learns a concept from the class C by saving at most d examples at a time. These d examples represent the current hypothesis of the learning algorithm. A space-bounded learning algorithm is called acyclic if a hypothesis that has been rejected as incorrect is never reinstated. We give a sufficient condition for this algorithm to be acyclic on a maximum class C. Classes for which this algorithm is acyclic include positive half-spaces in Euclidean space En , balls in En , and arbitrary rectangles in the plane. This algorithm is also acyclic on positive sets in the plane where each positive set is defined by a polynomial of degree at most n. The algorithm can be thought of as learning a boundary between the positive and the negative examples.