Synthesizing Recursive Logic Programs by Inverting General Resolution

Abstract

A fundamental scalability restriction of most Inductive Logic Programming (ILP) systems is that they search syntactically defined program spaces and cannot utilize relations in data. While semantic search methods that directly explain examples by inductive inference rules may utilize data relations to effectively prune the search space, in general logic programs, the compactness of the search space is often outweighed by the high complexity of inductive inference algorithms. In this study, we designed MPL, an inductive inference system based on two key ideas. First, MPL contains rules with at most four literals of dyadic predicates, which allow efficient and complete abduction without losing too much expressivity. Second, MPL uses the general resolution as the deduction model, which is inverted by two inductive rules: abduction and split. The general resolution allows MPL to inductively transform non-recursive sentences with invented predicates into recursive sentences. We analyze MPL language’s expressivity and implement a search algorithm, which shows performance advantages over existing syntactical search methods for several tasks.

Keywords

• Inductive logic programming
• inverse resolution
• predicate invention