Pac-Learning Nondeterminate Clauses

William W. CohenAAAI 1994

Introduction

Inductive Logic Programming (ILP) seeks to automatically induce logic programs, such as Prolog, from examples and background knowledge. Historically, the field has relied heavily on the concept of determinate clauses to ensure theoretical learnability. In a determinate clause, every variable introduced in the body has a unique, unambiguous binding based on the variables preceding it. While this restriction makes clauses PAC-learnable (Probably Approximately Correct), it is often too rigid for complex, real-world logic where variables may map to multiple possible values.

This paper introduces "locality," a new structural restriction that allows for nondeterministic variables while maintaining computational tractability. By shifting the focus from variable uniqueness to variable independence, the author provides a theoretical bridge to learning more expressive logic programs.

The Problem with Determinacy

While determinate clauses are the "gold standard" for learnable logic, they are highly restrictive. Most natural generalizations—such as allowing recursion, deeper variable nesting, or nondeterminate variables—typically hit computational walls built by cryptographic assumptions, making them "hard" to learn. The central challenge addressed here is whether the determinacy requirement can be relaxed without making the learning problem intractable.

The Concept of Locality

Instead of requiring unique bindings, the author proposes locality, which measures the "scope of influence" of a variable. This is defined through three key concepts:

  1. Touching: Two variables are said to "touch" if they appear together in the same literal.
  2. Influence: This is the transitive closure of the touching relationship. If variable A touches B, and B touches C, then A influences C.
  3. Locale: A variable’s locale is the set of all literals containing that variable or any variable it influences.

Locality ($k$) is defined as the size of the largest locale in a clause. In essence, while determinacy is about uniqueness (there is only one right value), locality is about independence (a variable choice only affects a small, local neighborhood of literals).

The Learning Algorithm

The paper proves that $k$-local clauses, where $k$ is a constant, are PAC-learnable. The proposed algorithm is a variation of Leslie Valiant’s classic technique for learning Boolean monomials.

The process begins with the "most specific" possible $k$-local clause—a conjunction of all possible locales. The learner then prunes away any locale that is inconsistent with a positive example. Because locales are independent and do not share free variables, they do not interact during evaluation. This decomposition allows the complex logic program to be treated as a set of independent components, enabling an efficient pruning strategy.

Key Theoretical Results

The paper establishes two primary theorems that redefine the boundaries of ILP:

  • Theorem 1 (Learnability): For any fixed locality $k$ and maximum literal arity $a$, the language of $k$-local clauses is uniformly PAC-learnable. The algorithm runs in time polynomial to the size of the database and the number of examples.
  • Theorem 2 (Expressiveness): Constant-locality clauses are strictly more expressive than constant-depth determinate clauses. The author proves that a depth-$d$ determinate clause with arity $a$ can be represented as a $k$-local clause where $k = a^{d+1}$.

Limitations and Future Work

Despite the theoretical success, there are practical considerations for implementation. The "top-down" pruning approach (starting with everything and removing) is often less efficient in practice than the "bottom-up" approaches (building up from empty) used in established systems like GOLEM or FOIL.

Additionally, the current framework focuses on nonrecursive clauses. While arbitrary recursion is known to be unlearnable, the author identifies the learnability of "linear recursive" $k$-local clauses as a significant open question. Finally, while $k$-local clauses are more expressive, the constant $k$ can grow exponentially with the depth of the determinate clause it replaces, suggesting a potential "doubly exponential" complexity regarding depth in certain applications.

Conclusion

This work provides a vital semantic generalization for ILP. By moving away from purely syntactic restrictions and focusing on the independent behavior of variables during evaluation, the author demonstrates that nondeterminism does not inherently preclude efficient learning. The next step for the field is to determine how frequently "highly local" structures appear in real-world datasets and to develop practical learners that can exploit this new bias.

Summary updated

BibTeX
@inproceedings{cohen1994pac,
  author = {William W. Cohen},
  title = {{Pac-Learning Nondeterminate Clauses}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure