Version Spaces: A Candidate Elimination Approach to Rule Learning

Abstract

An important research problem in artificial intelligence is the study of methods for learning general concepts or rules from a set of training instances. An approach to this problem is presented which is guaranteed to find, without backtracing, all versions consistent with a set of positive and negative training instances. The algorithm put forth uses a representation of the of those rules consistent with the observed training data. This rule version space is modified in response to new training instances by eliminating candidate versions found to conflict with each new instance. The use of version spaces is discussed in the context of Meta-DENDRAL, a program which learns rules in the domain of chemical spectroscopy.