Learning nonrecursive definitions of relations with LINUS

Many successful inductive learning systems use a propositional attribute-value language to represent both training examples and induced hypotheses. Recent developments are concerned with systems that induce concept descriptions in first-order logic. The deductive hierarchical database (DHDB) formalism is a restricted form of Horn clause logic in which nonrecursive logical definitions of relations can be expressed. Having variables, compound terms and predicates, the DHDB formalism allows for more compact descriptions of concepts than an attribute-value language. Our inductive learning system LINUS uses the DHDB formalism to represent concepts as definitions of relations. The paper gives a description of LINUS and presents the results of its successful application to several inductive learning tasks taken from the machine learning literature. A comparison with the results of other first-order …