Introduction
Presented at AAAI-93, William W. Cohen's work serves as a critical "reality check" for the field of Inductive Logic Programming (ILP). While early research celebrated the learnability of simple logic programs, Cohen utilizes computational complexity and cryptographic theory to demonstrate that even modest increases in program complexity render learning computationally intractable.
The Challenge of Inductive Logic Programming
The primary objective of ILP is to induce logic programs—specifically Horn clauses—from sets of examples. A significant milestone in the field was the proof that a single constant-depth determinate clause is learnable within the Probably Approximately Correct (PAC) model.
In this context, "determinate" implies that for any given input, there exists a unique binding for the variables in the logic program. "Constant-depth" refers to a reasoning chain whose length remains fixed regardless of the problem's scale. However, practical applications often demand greater expressivity. Cohen investigates whether extending these parameters—allowing deeper reasoning, indeterminate variable choices, or recursion—preserves efficient learnability.
Methodology: Emulating Circuits with Logic Programs
To establish these limitations, Cohen employs prediction-preserving reducibility. Rather than proving the non-existence of a learning algorithm from first principles, he demonstrates that if these logic programs were learnable, one could solve problems widely considered impossible, such as breaking standard cryptographic systems.
The core of this approach involves mapping logic learning problems to known hard classes:
- Boolean Circuits ($NC^1$): Hard to learn under cryptographic assumptions.
- DNF (Disjunctive Normal Form) Formulas: A long-standing open problem in learning theory.
- Deterministic Log-Space Turing Machines (DLOG): Protected by cryptographic hardness.
As shown in Figure 2, a Boolean circuit can be directly translated into a logic program. By defining predicates that mimic standard logic gates (AND, OR, NOT), a single Horn clause can evaluate the output of a complex circuit.
Figure 4 illustrates the underlying truth table facts required for this emulation. With these definitions, the logic program effectively "simulates" the circuit's behavior.
Key Insights and Theoretical "Speed Limits"
Cohen’s analysis reveals several fundamental barriers to efficient learning:
- The Log-Depth Wall: Moving from constant depth to logarithmic depth (where reasoning length grows slowly with input size) allows a clause to emulate an $NC^1$ Boolean circuit. Consequently, log-depth clauses are cryptographically hard to learn.
- Indeterminacy and DNF: Introducing "free" or indeterminate variables—where a variable can take multiple possible values—makes the learning problem equivalent to learning DNF formulas. Given that DNF learning remains an unsolved challenge in computational learning theory, indeterminate ILP is likely intractable.
- The Power of Recursion: Even constant-depth determinate clauses become cryptographically hard to learn when recursion is added. Recursion allows a clause to emulate a Turing machine, significantly elevating its complexity.
- Representation Independence: These results are "representation-independent," meaning no algorithm—regardless of its internal knowledge representation—can learn these programs in polynomial time.
Key Results
The paper formalizes these insights through several key theorems:
- Theorem 2: Learning determinate clauses of logarithmic depth is as hard as learning $NC^1$ circuits.
- Theorem 4: Learning indeterminate clauses with $k$ free variables is equivalent to the difficulty of learning DNF.
- Theorem 5: Learning a single recursive determinate clause is as hard as learning DLOG-space Turing machines.
Conclusion and Future Directions
While these results are primarily negative, they provide a vital roadmap by identifying the boundaries of general-purpose learning algorithms. Cohen notes that while general recursion is hard, "linearly recursive" clauses might remain learnable. Furthermore, while these programs are hard to learn for any distribution, they may be tractable for specific, natural data distributions. Finally, the work explains why practical ILP systems like FOIL or GOLEM must rely on heuristics rather than guaranteed efficient algorithms to navigate these complex search spaces.
Summary updated