BEXA - A COVERING ALGORITHM FOR LEARNING PROPOSITIONAL CONCEPT DESCRIPTIONS

BEXA is a new covering algorithm for inducing propositional concept de scriptions. Existing covering algorithms such as AQ15 and CN2 place ri gid constraints on the search process to reduce the learning time. The se restrictions may allow useless specializations while at the same ti me ignoring potentially useful specializations. in contrast BEXA emplo ys three dynamic search constraints that enable it to find simple and accurate concept descriptions efficiently. This paper describes the BE XA algorithm and its relationship to the covering algorithms AQ15, CN2 , GREEDY3, PRISM, and an algorithm proposed by Gray. The specializatio n models of these algorithms are described in the uniform framework of specialization by exclusion of values. BEXA is compared empirically t o state-of-the-art concept learners CN2 and C4.5. It produces rules of comparable accuracy, but with greater simplicity.