An ILP Method Based on Instance Graph

Runqi ZhangAAAI 2000

Introduction

Inductive Logic Programming (ILP) is a machine learning paradigm that learns logical rules from examples and background knowledge. A persistent challenge in ILP is the management of recursion. When learning recursive rules, systems must prevent infinite loops, such as $Ancestor(X, Y) \leftarrow Ancestor(X, Y)$. Traditional systems like FOIL (First-Order Inductive Learner) address this by imposing a strict "Literal Order" on constants. However, this approach suffers from significant limitations: it struggles with Multiple Predicate Learning (MPL), often requires manual constant ordering, and depends heavily on "strong hints" from ground clauses.

The Instance Graph Framework

To overcome these limitations, this paper introduces the Instance Graph ($H_{(R,E)}$), a directed hypergraph representation. In this framework, every vertex represents a specific example of a target predicate. Relationships between examples are modeled using hyperarcs, which represent clause instances.

Hyperarc Representation

The graph distinguishes between non-recursive and recursive clauses:

  • Non-recursive clauses: A hyperarc connects an example vertex ($v_i$) to a special terminal vertex labeled "true". This signifies that the example is grounded in base facts.
Non-recursive hyperarc
  • Recursive clauses: A hyperarc connects a "head" example vertex ($v_k$) to a set of vertices ($v_{j1}, v_{j2}, \dots, v_{jt}$) corresponding to the examples in the rule's body.
Recursive hyperarc

Intensional Coverage

A key concept in this framework is intensional coverage. An example is considered covered by a ruleset only if a hyper-path exists from the "true" vertex back to the example's vertex. This topological requirement replaces the traditional temporal ordering of literals, ensuring that any learned ruleset is inherently executable and free of infinite recursion.

The FOILBIG Algorithm

Building on the Instance Graph, the authors developed FOILBIG (First-Order Inductive Learner Based on Instance Graph). FOILBIG maintains the graph structure dynamically during the learning process. By ensuring that every newly added rule contributes to a valid hyper-path, the algorithm guarantees the executability of the final ruleset.

A significant advantage of FOILBIG is its handling of "hung" examples—those that are extensionally covered by a rule but lack a path to the "true" vertex. Tracking these examples allows the learner to monitor progress more precisely during the search. Furthermore, because the graph tracks relationships across all examples, FOILBIG is naturally suited for Multiple Predicate Learning (MPL), where mutual recursion between different predicates may occur.

Results and Discussion

Preliminary experiments on recursive learning tasks demonstrate that FOILBIG can solve complex problems that were previously beyond the reach of the original FOIL algorithm. Key benefits include:

  • Guaranteed Executability: The system provides a theoretical guarantee that covered examples are reachable through executable logic.
  • Efficiency: Maintaining the instance graph does not significantly increase computational overhead compared to standard FOIL.
  • Flexibility: By removing the need for pre-defined constant orders, FOILBIG offers a more general and automated approach to ILP.

While the current implementation of FOILBIG is a proof-of-concept, future work will focus on optimizing the system, fully evaluating its MPL capabilities, and developing more sophisticated search heuristics enabled by the Instance Graph structure.

Summary updated

BibTeX
@inproceedings{zhang2000ilp,
  author = {Runqi Zhang},
  title = {{An ILP Method Based on Instance Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}

Loading related content...

Figure