Specialization by exclusion

Abstract

This paper presents a theoretical analysis of the search schemes employed by AQ, CN2 and the recently introduced BEXA algorithm. These covering algorithms induce disjunctive concept descriptions, and employ a general-to-specific search when constructing the conjunctions in these expressions. BEXA specializes a conjunction by excluding values from it, while CN2 and AQ specialize a conjunction by appending atoms to it. It is shown that the latter two algorithms' search process can also be viewed as one of excluding values. This makes it possible to show that the three algorithms' search schemes differ only with respect to the number of values excluded at each specialization step, and the number of different specializations that are constructed. We show that the search for accurate and simple conjunctions can be restricted to find elements of the set CM of most general and consistent conjunctions. CM is characterized precisely. BEXA exploits this characterization to induce simple and accurate concept descriptions efficiently.