Learning Higher-Order Logic Programs From Failures

Stanislaw J. Purgal, David M. Cerna, Cezary KaliszykIJCAI 2022 · DOI

TL;DR

This paper introduces "Hopper," a novel Inductive Logic Programming (ILP) system that significantly enhances learning performance by effectively incorporating higher-order (HO) logic definitions. By extending the "Learning From Failures" paradigm, Hopper learns more concise and accurate programs, outperforming existing state-of-the-art HO-ILP systems, particularly on complex tasks.

What Problem Does This Paper Address?

Inductive Logic Programming (ILP) aims to learn logic programs from examples, but learning complex programs remains a significant challenge. While higher-order (HO) logic can lead to more compact and expressive programs, existing HO-ILP systems often require substantial human guidance in the form of metarules, which can be difficult to design. Furthermore, some HO-ILP systems struggle with certain types of HO definitions, like those involving ternary predicates or negation. This paper addresses the need for an ILP system that can effectively leverage HO definitions with minimal human intervention and handle a broader range of HO constructs.

Methods

The core contribution is the development of "Hopper," an extension of the "Learning From Failures" (LFF) system, Popper. Hopper integrates higher-order definitions into the LFF framework. Instead of directly using HO definitions, Hopper uses FO instances of these definitions, associating them with unique predicate symbols. This approach allows the LFF pruning mechanism to work soundly, as it operates on programs with matching structures. The theoretical framework developed by the authors defines a class of HO definitions that are monotone with respect to subsumption and entailment, preserving the soundness of existing pruning methods. Hopper also incorporates improvements for processing HO predicates, including generating context-passing versions and ensuring all generated code is used.

Datasets

The paper evaluates Hopper on a suite of tasks, including 7 tasks from previous work by Cropper and Morel (2021a), 2 tasks from Cropper et al. (2020), and 16 newly introduced tasks involving list manipulation, tree manipulation, and arithmetic. These new tasks are described as significantly harder than those previously evaluated. The experimental setup for each task, including background knowledge and parameters, is detailed in the appendices.

Key Insights and Ideas

  • HO definitions simplify complex programs: The paper demonstrates that incorporating HO definitions, even if they increase the search space, can lead to significantly shorter and more efficient solutions, especially for complex tasks.
  • Learning from Failures is key for HO: The LFF paradigm, with its generate-test-constrain loop, is shown to be a robust framework for learning with HO definitions, effectively pruning the search space and finding optimal solutions.
  • Indirect HO integration preserves soundness: By using FO instances of HO definitions, Hopper maintains the soundness of the LFF pruning mechanism, avoiding issues that arise with direct HO integration.
  • Reduced human guidance: Hopper requires less human intervention compared to systems like MetagolHO, which rely heavily on carefully crafted metarules.

Key Results

Hopper significantly outperforms its predecessor, Popper, on most tasks, especially the harder ones introduced in this work. It also demonstrates superior performance compared to the state-of-the-art HO-enabled ILP system, MetagolHO, particularly when MetagolHO is given minimal guidance. For instance, on tasks like allSeqN, Hopper (optimized) finds solutions much faster than Popper, and on many tasks, it achieves comparable or better performance than MetagolHO with optimal settings. The paper highlights that Hopper's optimized settings often lead to substantial speedups.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • HO Negation: Handling negation of HO literals is currently not fully supported and is left as future work.
  • Predicate Invention: While the framework allows for the invention of HO predicates, successfully automating this process remains an open and challenging problem.
  • Search Mechanism and Optimality: The current LFF implementation's bias towards longer clauses might hinder performance on certain tasks. Investigating alternative search mechanisms and optimality conditions beyond literal count is suggested.
  • Metarule Design for MetagolHO: The performance of MetagolHO is highly sensitive to the choice of metarules, making it difficult to compare fairly without extensive human effort in designing these rules.

Summary updated

BibTeX
@inproceedings{purgal2022learning,
  author = {Stanislaw J. Purgal and David M. Cerna and Cezary Kaliszyk},
  title = {{Learning Higher-Order Logic Programs From Failures}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/378},
}
Figure