On the complexity of learning from counterexamples

Abstract

The complexity of learning concepts belonging to various concrete concept classes C contained in 2/sup X/ over a finite domain X is analyzed in terms of the number of counterexamples that are needed in the worst case. It turns out that for many interesting concept classes there exist exponential differences between the number of counterexamples that are required by a 'naive' learning algorithm for C (e.g. one that always outputs the minimal consistent hypothesis) and a 'smart' learning algorithm for C, which attempts to make a more sophisticated prediction. theta (log n) bounds are given for the number of counterexamples that are required for learning boxes, balls, and halfspaces in a d-dimensional discrete space X=(1, . . ., n)/sup d/ (for every finite dimension d). Also given are an upper bound of O(d/sup 3/) and a lower bound of Omega (d/sup 2/) for the complexity of learning a threshold function with d input bits (i.e. X=(0, 1)/sup d/). For each of these concept classes one can give learning algorithms that are both optimal (or close to optimal in the case of threshold functions) with regard to the number of counterexamples which they require and computationally feasible. The complexity of learning the concept classes on several variations of the learning model considered is determined. The relationship between these learning models and some related combinatorial invariants is clarified.