Concept Learning and the Problem of Small Disjuncts

Abstract

Ideally, de nitions induced from examples should consist of all, and only, disjuncts that are meaningful (e.g., as measured by a statistical signi cance test) and have alowerror rate. Existing inductive systems create de nitions that are ideal with regard to large disjuncts, but far from ideal with regard to small disjuncts, where a small (large) disjunct is one that correctly classi es few (many) training examples. The problem with small disjuncts is that many ofthemhavehigh rates of misclassi cation, and it is di cult to eliminate the error-prone small disjuncts from a de nition without adversely a ecting other disjuncts in the de nition. Various approaches to this problem are evaluated, including the novel approach ofusing a bias di erent than the \\maximum generality " bias. This approach, and some others, prove partly successful, but the problem of small disjuncts remains open. Support for this researchwas provided by the Army Research O Science Foundation under grant IRI-8620052. ce under grantARO-DAAG29-84-K-0060 and the National 1 The Problem of Small Disjuncts Systems that learn from examples do not usually succeed in creating a purely conjunctive