Version spaces: an approach to concept learning.

The version space approach has been implemented as one component of the Meta-DENDRAL program for learning production rules in the domain of chemical spectroscopy and proofs are given for the correctness of the method for representing version spaces, and of the associated concept learning algorithm, for any countably infinite concept description language.

Abstract

A method is presented for learning general descriptions of concepts from a sequence of positive and negative training instances. This method involves examining a predetermined space or language of possible concept descriptions, finding those which are consistent with the observed training instances. Rather than use heuristic search techniques to examine this concept description space, the subspace (version space) of all plausible concept descriptions is represented and updated with each training instance. This version space approach determines all concept descriptions consistent with the training instances, without backtracking to reexamine past training instances or previously rejected concept descriptions. Proofs are given for the correctness of the method for representing version spaces, and of the associated concept learning algorithm, for any countably infinite concept description language. Empirical results obtained from computer implementations in two domains are presented. The version space approach has been implemented as one component of the Meta-DENDRAL program for learning production rules in the domain of chemical spectroscopy. Its implementation in this program is described in detail.