Beam search in attribute-based concept induction

Abstract

Thi spaper investigates the issues of specializing only a single best conjunction to employing a beam search when learning attribute-based concept descriptions using the GCA algorithm. We describe GCA, a recently introduced generic learning algorithm which generalizes a number of well-known learning algorithms like CN2 and AQ. It is shown, using ten test domains, that concept descriptions found by a beam search are seldom more accurate than those found by specializing only a single best conjunction. In addition, the former descriptions are usually more complex than the latter and in some cases even considerably more so. This result holds even when more stringent pruning is applied during a beam search. Since specializing only one conjunction is computationally much less demanding than specializing a set of alternative best conjunctions, the result is that GCA need not employ a beam search in order to find good descriptions.