Pac-Learning Recursive Logic Programs: Efficient Algorithms

William W. Cohen

TL;DR

This paper introduces efficient algorithms for learning restricted classes of recursive logic programs (specifically, Datalog programs) in polynomial time using equivalence queries. It establishes theoretical boundaries for what can be learned efficiently, showing that while simple recursive programs are learnable, even minor generalizations lead to computationally intractable problems.

What Problem Does This Paper Address?

The paper tackles the challenge of learning recursive logic programs, a key problem in inductive logic programming (ILP) and automatic programming. While much research in ILP focuses on learning relational concepts from noisy data, this work addresses the "automatic logic programming" problem: learning noise-free recursive programs that implement common functions (like list processing or arithmetic). The core difficulty lies in the recursive nature of these programs, which makes traditional learning techniques challenging. The authors aim to formally analyze the learnability of specific, restricted classes of recursive logic programs within a well-defined theoretical framework.

Methods

The paper introduces and utilizes a technique called forced simulation for generalizing logic clauses. This method is an alternative to existing generalization techniques and is described as analytically tractable. The learning algorithms are developed within the identification from equivalence queries model, which is a stronger learning model than PAC-learnability. This model requires a learner to exactly identify a target concept by asking an oracle whether its current hypothesis is correct, receiving either "yes" or a counterexample. The algorithms build upon a concept called a "bottom clause", which is a highly specific clause that is then generalized. For recursive programs, a modified forced simulation handles recursive calls by recursively simulating the hypothesis on subgoals, with a depth bound to ensure termination.

Datasets

Not discussed in the paper. The paper focuses on theoretical learnability and does not present experimental results on specific datasets.

Key Insights and Ideas

  • Forced Simulation as a Generalization Tool: The paper highlights forced simulation as an effective and theoretically sound method for generalizing logic clauses, particularly for recursive programs. It's presented as a key algorithmic component.
  • Delineating Learnable Boundaries: The research establishes that while very specific classes of recursive logic programs are efficiently learnable, even slight relaxations of these constraints lead to computationally hard learning problems. This work, combined with a companion paper, defines a boundary for efficient learnability.
  • Equivalence Queries are Powerful: The use of the equivalence query model allows for strong theoretical guarantees, demonstrating that certain recursive program classes can be learned exactly and efficiently.
  • The Importance of "Hints": The paper shows that learning more complex recursive programs (like two-clause programs) can be made efficient by providing additional "hints," such as a basecase oracle, which helps the learner distinguish between base and recursive cases.

Key Results

  • Learnability of Single Recursive Clauses: A single k-ary recursive, constant-depth, determinate clause is shown to be learnable in polynomial time from equivalence queries.
  • Learnability of Two-Clause Programs: A program consisting of one learnable recursive clause and one constant-depth determinate non-recursive clause is learnable if an additional "basecase" oracle is available.
  • Efficiency Guarantees: The learning algorithms presented are proven to run in polynomial time with respect to the size of the declaration and background knowledge, and a polynomial number of equivalence queries.

Limitations and Future Work

  • Highly Restricted Program Classes: The paper acknowledges that the learnable classes of recursive programs are "very constrained." The companion paper demonstrates that generalizing these classes in natural ways leads to computationally difficult learning problems.
  • Need for Oracles/Hints: For learning more complex programs (like two-clause programs), additional oracles (e.g., basecase oracle) or specific assumptions (like equality predicates) are required for efficient learnability.
  • Future Work: The paper suggests extending the learning algorithm to handle more general cases, such as allowing function symbols, non-ground background knowledge, and k-ary recursive clauses. It also explores the necessity of the basecase oracle and the possibility of replacing it with other forms of "hints." The authors also point to their companion paper for negative results that further delineate the boundaries of learnability.

Summary updated

Abstract

We present algorithms that learn certain classes of function-free recursive logic programs in polynomial time from equivalence queries. In particular, we show that a single k-ary recursive constant-depth determinate clause is learnable. Two-clause programs consisting of one learnable recursive clause and one constant-depth determinate non-recursive clause are also learnable, if an additional ``basecase'' oracle is assumed. These results immediately imply the pac-learnability of these classes. Although these classes of learnable recursive programs are very constrained, it is shown in a companion paper that they are maximally general, in that generalizing either class in any natural way leads to a computationally difficult learning problem. Thus, taken together with its companion paper, this paper establishes a boundary of efficient learnability for recursive logic programs.
BibTeX
@article{cohen1995pac,
  author = {William W. Cohen},
  title = {{Pac-Learning Recursive Logic Programs: Efficient Algorithms}},
  journal = {J. Artif. Intell. Res.},
  year = {1995},
  url = {https://openreview.net/forum?id=yg-VpCr5fVW},
}
Figure