Complete Bottom-Up Predicate Invention in Meta-Interpretive Learning

Céline Hocquette, Stephen H. MuggletonIJCAI 2020 · DOI

TL;DR

This paper introduces a novel bottom-up approach to predicate invention within Meta-Interpretive Learning (MIL). By generalizing background knowledge, this method effectively discovers new predicates, reducing the complexity for subsequent top-down learning and improving overall performance in tasks like chess endgame strategy and string transformations.

What Problem Does This Paper Address?

Meta-Interpretive Learning (MIL) is a powerful technique for program synthesis, but predicate invention – the creation of new, meaningful symbols to represent concepts – has traditionally relied on a top-down approach. This can be inefficient, requiring extensive search and potentially leading to complex hypotheses. The challenge is to find a more efficient way to discover these essential building blocks (predicates) that can significantly simplify the learning process and improve accuracy, especially when dealing with limited training data.

Methods

The core contribution is a new bottom-up predicate invention method. This approach augments existing top-down MIL systems by first generalizing the background knowledge. It achieves this by extending the "immediate consequence operator" (T_P) to second-order logic programs.

Here's how it works:

  1. Bottom-up Generalization: The T_P operator is iteratively applied to the initial background knowledge. This process generates new ground atoms.
  2. Predicate Invention: When new atoms are generated, Skolem constants are introduced to represent new predicate symbols. These, along with their corresponding metasubstitutions (definitions), form the "substrate" predicates.
  3. Redundancy Elimination: To keep the background knowledge clean, an equivalence relation for predicates is defined. Predicates that cover the exact same set of ground atoms are considered redundant and pruned.
  4. Top-down Learning: The learned "substrate" predicates are then added to the background knowledge. A standard top-down MIL learner (like Metagol) uses these new predicates to construct the final "surface" hypothesis.

This hybrid approach aims to reduce the number of clauses the top-down learner needs to find, thereby decreasing sample complexity and learning time.

Datasets

The paper evaluates the proposed method on two domains:

  • Chess Endgame KRK: A dataset focused on learning the strategy of protecting a rook with a king in a King-and-Rook vs. King endgame. The data is generated by creating board states and labeling them based on whether the white rook is protected.
  • String Transformations: A collection of 94 real-world string transformation problems, similar to those used in prior work. Each problem consists of 10 positive examples of input-output string pairs.

Key Insights and Ideas

  • Bottom-up is Better for Invention: Shifting predicate invention to a bottom-up phase, driven by generalizing background knowledge, is more effective than solely relying on top-down search.
  • Reduced Hypothesis Complexity: Inventing predicates upfront significantly simplifies the hypothesis space for the top-down learner, leading to fewer clauses in the final program.
  • Sample Complexity Gains: By reducing the number of clauses needed to represent a target theory, the method requires fewer training examples to achieve comparable or better accuracy.
  • Equivalence Relation is Crucial: A formal definition of predicate equivalence is essential for pruning redundant invented predicates, preventing the background knowledge from becoming overly bloated.

Key Results

The experimental results strongly support the effectiveness of the proposed bottom-up predicate invention method:

  • Improved Accuracy: In the KRK chess endgame experiment, the augmented MIL system showed statistically significant improvements in accuracy compared to the standard top-down approach, especially with limited training data.
  • Reduced Sample Complexity: For both KRK and string transformation tasks, the bottom-up approach significantly reduced the number of training examples required to learn the target theory. For instance, in KRK, learning a hypothesis with 3 clauses using bottom-up iterations required fewer training examples than learning a 5-clause hypothesis without it.
  • Faster Learning Times: The bottom-up augmented system consistently demonstrated faster learning times across experiments.
  • Predicate Reuse: Learned hypotheses in the string transformation tasks showed a high usage of the bottom-up invented predicates, indicating their utility.

Limitations and Future Work

  • Scope of Metarules: The current work is restricted to second-order metarules. The authors suggest exploring higher-order metarules to learn disjunctions or recursions in the bottom-up phase.
  • Theoretical Characterization: Further theoretical work is needed to characterize target theories for which this method is most effective, particularly concerning the structure of the calling diagram and predicate density.
  • Optimal Iterations: Determining the optimal number of bottom-up iterations for a given search space is an open question.
  • Scalability: While a theoretical condition for sample complexity gain is provided, devising more discriminative predicate selection methods is needed to improve scalability.

Summary updated

BibTeX
@inproceedings{hocquette2020complete,
  author = {Céline Hocquette and Stephen H. Muggleton},
  title = {{Complete Bottom-Up Predicate Invention in Meta-Interpretive Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/320},
}

Loading related content...

Figure