Resource limitations have played an important role in the development and verification of theories about intelligent behaviour. This paper is a step towards answering the question of what effect limited memory has on the ability of intelligent machines to learn from data. Our analysis is applicable to many existing learning methods, especially those that incrementally construct a generalization by making repeated passes through a set of training data (e.g. some implementations of perceptrons, neural nets, and decision trees). Most of these methods do not store the entire training set, since they allow themselves only limited storage, a restriction that forces them to produce a compressed representation. The question we address is, how much (if any) additional processing time is required for methods with limited storage ? We measure processing time for learning algorithms by the number of passes through a data set necessary to obtain a correct generalization. Researchers have observed that for some learning methods (e.g. neural nets) the number of passes through a data set gets smaller as the size of the network is increased ; however, no analytical study that explains this behaviour has been published. We examine limited storage algorithms for a particular concept class, nested hyperrectangles. We prove bounds that illustrate the fundamental trade-off between storage requirements and processing time required to learn an optimal structure. It turns out that our lower bounds apply to other algorithms and concept classes as well (e.g. decision trees). We discuss applications of our analysis to learning and to problems in human perception. We also briefly discuss parallel learning algorithms.

Proposes a theoretical model for analysis of classification methods, in which the teacher knows the classification algorithm and chooses examples in the best way possible. The authors apply this model using the nearest-neighbor learning algorithm, and develop upper and lower bounds on sample complexity for several different concept classes. For some concept classes, the sample complexity turns out to be exponential even using this best-case model, which implies that the concept class is inherently difficult for the NN algorithm. The authors identify several geometric properties that make learning certain concepts relatively easy. Finally the authors discuss the relation of their work to helpful teacher models, its application to decision tree learning algorithms, and some of its implications for experimental work.>

Our goal in this paper is to examine the application of Voronoi diagrams, a fundamental concept of computational geometry, to the nearest neighbor algorithm used in machine learning. We consider the question “Given a planar polygonal tessellation T and an integer k, is there a set of k points whose Voronoi diagram contains every edge in T?” We show that this question is NP-hard. We encountered this problem while studying a learning model in which we seek the minimum sized set of training examples needed to teach a given geometric concept to a nearest neighbor learning program. That is, given a concept which can be described by a planar tessellation, we are seeking to construct the smallest set of points whose Voronoi diagram is consistent with the given tessellation. In a sense, this question captures the difficulty of teaching the nearest neighbor algorithm a simple structure, using a minimal number of examples. In addition, we consider the natural inverse to the problem of computing Voronoi diagrams. Given a planar polygonal tessellation T, we describe an algorithm to find a set of points whose Voronoi diagram is T, if such a set exists.