Machine Invention of First Order Predicates by Inverting Resolution

Abstract

It has often been noted that the performance of existing learning systems is strongly biased by the vocabulary provided in the problem description language. An ideal system should be capable of overcoming this restriction by defining its own vocabulary. Such a system would be less reliant on the teacher's ingenuity in supplying an appropriate problem representation. For this purpose we present a mechanism for automatically inventing and generalising first-order Horn clause predicates. The method is based on inverting the mechanism of resolution. The approach has its roots in the Duce system for induction of propositional Horn clauses. We have implemented the new mechanism in a system called CIGOL. CIGOL uses incremental induction to augment incomplete clausal theories. A single, uniform knowledge representation allows existing clauses to be used as background knowledge in the construction of new predicates. Given examples of a high-level predicate CIGOL generates related sub-concepts which it then asks its human teacher to name. Generalisations of predicates are tested by asking questions of the human teacher. CIGOL generates new concepts and generalisations with a preference for simplicity. We illustrate the operation of CIGOL by way of various sessions in which auxiliary predicates are automatically introduced and generalised.