Constructive Inductive Logic Programming

Abstract

Constructive learning, the capacity to extend a fixed initial representation by adding new nonobservational terms, is an active research topic in machine learning. We show how the very notion of constructiveness has evolved, and define with some precision the sort of learning which should be considered constructive in the context of Inductive Logic Programming. We begin by investigating the differing extent to which two classes of new terms, useful or necessary predicates, enrich a representation. We then characterize two situations, partial utilization and zero utilization of a new necessary predicate, in which learning methods based on inverse resolution lack a sufficiently representative set of instances to allow a concept to be learned. In the absence of a more representative set we conclude that efforts must move from inverse resolution towards a more powerful technique, that is, inverse implication. The notion of sub-unification allows us to invert implication with a small number of examples. These ideas are expressed in a Constructive Inductive Logic Programming algorithm CILP, based on inverting implication. CILP learns some natural classes of Hom clauses with partially- and zero-utilized terms not learnable by methods based on inverse resolution.