Inductive Logic Programming as Abductive Search

Domenico Corapi, Alessandra Russo, Emil Lupu

TL;DR

This paper introduces TAL, a novel top-down Inductive Logic Programming (ILP) system that frames ILP problems as Abductive Logic Programming (ALP) tasks. This approach allows for more expressive language biases, handles non-monotonicity, and offers a principled search space for learning complex logic programs.

What Problem Does This Paper Address?

Inductive Logic Programming (ILP) aims to learn logic theories from examples, but it faces challenges with computational complexity and expressiveness. Existing top-down ILP systems often limit the language used for hypotheses or struggle with non-monotonic reasoning (e.g., negation). While Abductive Logic Programming (ALP) offers a way to handle incomplete theories and negation, integrating it effectively into top-down ILP has been an open problem. This paper addresses the need for an ILP system that is both expressive and capable of handling non-monotonicity by leveraging the strengths of ALP.

Methods

The core contribution is the mapping of an ILP problem into an equivalent ALP problem. This is achieved by:

  • Hypothesis Representation: Inductive hypotheses (sets of rules) are represented as abducible facts in the ALP framework. This allows rules to be constructed incrementally and checked for consistency.
  • Top Theory Generation: A "top theory" is automatically generated from a set of mode declarations (which define the language bias). This top theory acts as a constraint on the search space, effectively bounding the generality of the learned rules.
  • Abductive Search: An abductive proof procedure is then instantiated on this top theory and the background knowledge. The abductive derivation identifies the heads of the rules and the necessary conditions to cover positive examples while excluding negative ones.
  • TAL System: The implemented system, called TAL (Top-directed Abductive Learning), uses this mapping to perform a top-down search. It explores candidate solutions, backtracking when a partial hypothesis leads to failure. This approach allows for non-observational learning (learning predicates not present in the examples) and multi-predicate learning.

Datasets

The paper uses a modified version of a well-known example from [Yam97] involving learning even and odd predicates. It also presents a case study from [Ray09a] involving metabolic regulation in E. coli, which includes axioms from the Event Calculus. No new benchmarks are introduced.

Key Insights and Ideas

  • ILP as ALP: Framing ILP as an ALP problem provides a principled way to manage the search space and handle complex logical constructs like negation.
  • Top Theory as Bias: The automatic generation of a top theory from mode declarations offers a powerful and flexible way to specify language bias, going beyond traditional mode declarations.
  • Interleaved Rule Construction: The abductive approach allows for the heads and bodies of rules to be constructed concurrently, enabling partial hypotheses to be tested and refined during the derivation process. This contrasts with some other systems where rule heads are determined first, then bodies.
  • Non-Monotonicity and Non-Observational Learning: The system naturally handles non-monotonic reasoning and can learn predicates that are not explicitly present in the training examples, which is a significant advantage over many existing ILP systems.

Key Results

The paper demonstrates that TAL can solve ILP problems that are challenging for other systems, including learning connected theories and handling non-monotonicity. The authors claim that TAL can find solutions that are not found by Inverse Entailment (IE) based systems like PROGOL or ALECTO. They also highlight that TAL can learn base cases for recursion and handle non-observational learning. While specific quantitative results are not the primary focus, the case studies illustrate the system's capabilities in learning complex rules.

Limitations and Future Work

  • Scalability: The authors acknowledge that while promising, the current implementation is a prototype. They plan to investigate the use of heuristics and informed search techniques to improve scalability for larger datasets and theories.
  • Empirical Comparison: A full empirical comparison with other state-of-the-art systems like XHAIL is limited due to the unavailability of XHAIL.
  • Future Directions: The authors intend to explore the properties of the mapping and its relationship to the search spaces of other ILP techniques. They also plan to investigate the use of partial hypotheses for informed search strategies.

Summary updated

Abstract

We present a novel approach to non-monotonic ILP and its implementation called TAL (Top-directed Abductive Learning). TAL overcomes some of the completeness problems of ILP systems based on Inverse Entailment and is the first top-down ILP system that allows background theories and hypotheses to be normal logic programs. The approach relies on mapping an ILP problem into an equivalent ALP one. This enables the use of established ALP proof procedures and the specification of richer language bias with integrity constraints. The mapping provides a principled search space for an ILP problem, over which an abductive search is used to compute inductive solutions.
BibTeX
@inproceedings{corapi2010inductive,
  author = {Domenico Corapi and Alessandra Russo and Emil Lupu},
  title = {{Inductive Logic Programming as Abductive Search}},
  booktitle = {Iclp (technical Communications)},
  year = {2010},
  doi = {10.4230/lipics.iclp.2010.54},
}
Figure