Learning Large Logic Programs By Going Beyond Entailment

Andrew Cropper, Sebastijan DumancicIJCAI 2020 · DOI

TL;DR

This paper introduces Brute, a novel Inductive Logic Programming (ILP) system that moves beyond traditional entailment-based search to guide hypothesis generation. By employing example-dependent loss functions, Brute can learn significantly larger and more complex logic programs than existing state-of-the-art systems, demonstrating improved performance across various program synthesis domains.

What Problem Does This Paper Address?

The core challenge this paper tackles is the difficulty of learning "large" logic programs in the field of Inductive Logic Programming (ILP). Existing ILP systems primarily rely on "entailment" to guide their search for hypotheses. Entailment is a binary concept: a hypothesis either perfectly explains an example or it doesn't. This strict requirement creates a significant limitation, especially when learning complex programs where intermediate, imperfect solutions are crucial steps. Imagine trying to learn a program that transforms an image – a system relying solely on entailment would struggle to differentiate between a hypothesis that's "almost right" and one that's completely wrong, hindering its ability to incrementally build a correct program. This limitation becomes particularly pronounced when learning programs that are large in terms of clauses or literals, as is often the case in program synthesis tasks like robot planning or string manipulation.

Methods

The paper introduces Brute, a new ILP system designed to overcome the limitations of entailment-based search. Brute's core innovation lies in its use of example-dependent loss functions. Instead of a binary entailment check, these functions provide a graded measure of how "close" a hypothesis's output is to the desired output for a given example. This allows Brute to prioritize hypotheses that are partially correct, mirroring how humans often learn by trial and error.

Brute operates in two main stages:

  1. Invent Stage: Brute first generates a "library" of potential new predicates. It does this by composing existing primitive predicates (provided in the background knowledge) using Answer Set Programming (ASP) encodings. This stage is crucial for creating the building blocks for larger, recursive programs. Brute employs constraints to prune the search space and avoid generating redundant or pointless predicates.
  2. Search Stage: Brute then performs a best-first search to construct a hypothesis program. This search is guided by the chosen example-dependent loss function. It iteratively applies predicates from the invented library to the current set of examples, generating new intermediate states (specifications and hypotheses). The system prioritizes states with lower loss, effectively exploring promising paths towards a solution. When a hypothesis achieves zero loss (meaning it perfectly explains all positive examples and doesn't contradict negative ones), the search terminates.

Datasets

The paper evaluates Brute on three diverse program synthesis domains:

  • Robot Planning: Tasks involve learning plans for a robot to navigate a grid and manipulate objects.
  • String Transformations: Real-world tasks requiring manipulation of strings and cursor positions.
  • ASCII Art Generation: A newly introduced benchmark where the goal is to learn programs that generate ASCII art representations of strings.

The experiments utilize positive training examples and measure performance on unseen test examples.

Key Insights and Ideas

  • Beyond Binary Entailment: The most significant insight is that moving beyond strict entailment to graded loss functions is critical for learning complex, large programs. This allows for more nuanced guidance during the search process.
  • Human-like Learning: Brute's approach of "build, execute, evaluate, revise" closely mimics how humans learn to program, suggesting a more intuitive and effective learning paradigm.
  • Inventing Building Blocks: The ability to automatically invent new, potentially recursive, library predicates is a key enabler for learning large programs. This is a departure from systems that rely solely on a fixed set of background predicates.
  • Domain-Specific Loss Functions: The effectiveness of Brute hinges on the use of domain-specific loss functions (e.g., Hamming distance for images, Levenshtein distance for strings), highlighting the importance of incorporating domain knowledge into the learning process.

Key Results

Brute demonstrates substantial improvements over existing ILP systems, particularly in learning large programs:

  • Program Size: Brute can learn programs up to 20 times larger than state-of-the-art systems like Metagol. For instance, in the ASCII art experiment, Brute learned a program with 79 clauses and 294 literals, while Metagol struggled to learn any solutions.
  • Performance: In the robot planning domain, Brute significantly outperformed Metagol as grid sizes increased, solving 67% of tasks for a 10x10 grid compared to Metagol's 8% for a 6x6 grid.
  • Learning Speed: Brute learns programs substantially quicker than other systems, often completing tasks in seconds on a standard computer, whereas other methods can take days.
  • Outperforming Entailment: Experiments comparing Brute with a variant using an entailment-based loss function showed that Brute's example-dependent loss approach yielded better results.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Generality: Brute is currently designed for learning recursive programs from dyadic input/output examples. It cannot directly handle classical ILP problems like Mutagenesis, which involve non-dyadic examples. The authors propose representing classification tasks as program synthesis tasks to address this.
  • Search Efficiency: The current "brute-force" invention of library predicates and the simple best-first search can be inefficient. Future work aims to dynamically invent library predicates during the search and explore more advanced search techniques like A* or iterative budgeted exponential search.
  • Loss Function Learning: While Brute uses pre-defined example-dependent loss functions, future work could explore learning suitable loss functions through meta-learning, further bridging the gap between domain-specific knowledge and general learning capabilities.

Summary updated

BibTeX
@inproceedings{cropper2020learning,
  author = {Andrew Cropper and Sebastijan Dumancic},
  title = {{Learning Large Logic Programs By Going Beyond Entailment}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/287},
}
Figure