Efficient Specialization of Relational Concepts
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF PSYCHOLOGY
Pagination or Media Count:
This research note presents an algorithm for a common induction problem, the specialization of overly general concepts. A concept is too general when it matches a negative example. The particular case addressed here assumes that concepts are represented as conjunctions of predicates, that specialization is performed by conjoining predicates to the overly general concept, and that the resulting specializations are to be as general as possible. It is shown that the problem is simple if the concept representation language is propositional, but NP-complete if the language is first-order i.e., relational. Nonetheless, there exists an algorithm, based on manipulator of bit vectors, that provides good average-case performance. Keywords Machine learning Artificial intelligence Version spaces Concept induction.