Learning Relations by Pathfinding

Bradley L. Richards, Raymond J. MooneyAAAI 1992

Abstract

This paper introduces relational pathfinding, a technique designed to help Inductive Logic Programming (ILP) systems escape "local plateaus" where single-step improvements are not immediately visible to greedy search algorithms. By treating relational data as a graph and searching for paths between constants in positive examples, the proposed algorithm can discover complex multi-literal rules that traditional hill-climbing methods typically miss.

Introduction: The Local Plateau Problem

Most first-order learning systems, such as FOIL or FORTE, employ a "top-down" hill-climbing approach to construct rules. These systems add one literal (a relationship) at a time, retaining it only if it yields an immediate statistical improvement in the rule's accuracy.

However, many relational concepts reside on "local plateaus." In these scenarios, adding a single literal provides no immediate benefit, even if it is a necessary component of a perfect rule. For instance, defining a grandparent(x, y) requires two parent relations: parent(x, z) and parent(z, y). Adding only the first literal does not help distinguish a grandparent from a random individual, causing greedy algorithms to stall.

Figure 1: A visual representation of a local plateau in a search space, where a greedy search might get stuck because no single step leads to an immediate improvement.

Methodology: Relational Pathfinding

The authors propose viewing the domain as a graph where constants (e.g., people, objects) are nodes and relations are edges. The pathfinding process follows these steps:

  1. Spreading Activation: When the learner encounters a plateau, it selects a positive example and performs a breadth-first search starting from the constants involved.
  2. Finding Intersections: Paths are expanded one relation at a time until paths from different constants intersect.
  3. Rule Generation: Upon intersection, the sequence of relations is converted into a set of literals.
  4. Variable Substitution: Specific constants are replaced with variables to generalize the rule.
  5. Hybrid Refinement: If the resulting rule is overly general, the system reverts to standard hill-climbing to add non-relational constraints, such as male(x).

This approach is more flexible than "relational clichés" and more general than "determinate literals," as it does not require pre-defined templates or 1-to-1 mappings.

Evaluation and Datasets

The method was evaluated across three distinct domains:

  • Hinton’s Family Domain: A benchmark involving 112 positive and 272 "near-miss" negative instances across two 12-member families.
  • Qualitative Modeling (QSIM): Behavioral data from cascaded water tanks where some variables (e.g., "net-flow") are unobserved.
  • Logic Programming: Synthesizing the merge_sort algorithm, which requires learning recursive clauses.

Key Results

The relational pathfinding method demonstrated significant improvements in both efficiency and discovery capabilities:

  • Learning Efficiency: In the family domain, the system achieved 100% accuracy with only 120 training instances. As shown in Figure 5, the "Relation-path" method significantly outperforms the "Normal" greedy approach in terms of learning rate and final accuracy.
  • Model Discovery: The system successfully reconstructed qualitative physical models for cascaded tanks, even when critical variables were omitted from the input data, by identifying them as intersection points in the relational graph.
  • Recursive Synthesis: The algorithm successfully learned the complex merge_sort rule, including its recursive structure, by finding paths through list-processing relations.
Figure 5: Learning curves comparing the accuracy of the Relation-path method against a standard (Normal) ILP approach as a function of training instances.

Limitations and Future Work

While effective, breadth-first search from multiple nodes can be computationally expensive. The authors mitigate this using resource bounds (depth limits). Future work includes refining these bounds and integrating the technique into larger knowledge-base revision tasks. Relational pathfinding serves as a "heavy lifter" for complex domains where simpler, greedy methods fail to find a path to the correct hypothesis.

Summary updated

BibTeX
@inproceedings{richards1992learning,
  author = {Bradley L. Richards and Raymond J. Mooney},
  title = {{Learning Relations by Pathfinding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure