Covering vs. Divide-and-Conquer for Top-Down Induction of Logic Programs

Henrik Boström

Introduction

Inductive Logic Programming (ILP) aims to automate the discovery of logic programs from sets of positive and negative examples. Historically, two primary search strategies have dominated the field: Covering and Divide-and-Conquer (D&C). While the Covering approach—exemplified by algorithms like FOIL—has become the industry standard for logic programming, Divide-and-Conquer remains the backbone of decision tree induction in propositional learning. This paper formalizes the D&C strategy for ILP and provides a rigorous comparative analysis against the Covering approach.

Methodology: Formalizing Search Strategies

The core of this comparison lies in how each strategy explores the hypothesis space using Goal Reduction (or Unfolding).

  • The Covering Approach: This strategy builds a program one clause at a time. It specializes a general clause until it covers no negative examples, "saves" that clause, removes the covered positive examples, and repeats the process.
  • The Divide-and-Conquer Approach: D&C recursively splits the dataset into purer subsets. By "unfolding" a general clause—replacing a goal with its definitions from background knowledge—the algorithm branches into more specific rules. Rules covering only positives are retained, while those covering only negatives are discarded. Mixed rules are further unfolded.

Experimental Evaluation

The strategies were tested across three distinct domains: Chess Endgames (King+Rook vs. King+Pawn), Tic-Tac-Toe, and Natural Language Parsing (DCG).

Computational Efficiency

A major finding is the inherent redundancy of the Covering approach. Because it restarts its search for every new rule, it frequently re-evaluates identical search paths. In contrast, the D&C approach partitions the search space, ensuring that no alternative is considered more than once.

Comparison of computational effort measured in coverage checks.

As shown in the figure above, the number of coverage checks required by the Covering strategy grows significantly faster than that of D&C as the training set size increases. In the Chess and DCG domains, Covering performed between 3.3 and 30 times more work (measured in coverage checks) than D&C to reach the same result.

Accuracy and Domain Sensitivity

The performance of each strategy is highly dependent on the target domain. D&C prioritizes discrimination (separating positives from negatives), whereas Covering prioritizes coverage (maximizing the number of positives explained by a single rule).

Accuracy comparison in the Chess Endgame domain.

In the Chess domain, the discriminative focus of D&C resulted in consistently higher accuracy across various training set sizes. However, this trend reversed in the Tic-Tac-Toe domain, where the Covering approach proved more effective, suggesting that the "best" algorithm is highly domain-dependent.

Discussion: The Recursion and Compactness Trade-off

Despite the efficiency gains of D&C, the Covering approach remains the standard for ILP for two critical reasons:

  1. Recursion: D&C struggles with recursive definitions because local "splits" in the decision tree can inadvertently break the global recursive structure. While recursive problems can be transformed to use D&C, this often prevents the algorithm from finding the actual recursive structure.
  2. Compactness: Covering searches a less constrained hypothesis space, often yielding more elegant and compact programs than the tree-structured output of D&C.

Conclusion

Divide-and-Conquer offers a significantly more efficient alternative to the standard Covering approach in ILP, particularly in domains where discrimination is key. While Covering remains superior for learning recursive and compact programs, the formalization of D&C through goal reduction opens new avenues for hybrid algorithms that could combine the efficiency of splitting with the expressive power of covering.

Summary updated

Abstract

Covering and divide-and-conquer are two well-established search techniques for top-down induction of propositional theories. However, for top-down induction of logic programs, only covering has been formalized and used extensively. In this work, the divide-and-conquer technique is formalized as well and compared to the covering technique in a logic programming framework Covering works by repeatedly specializing an overly general hypothesis, on each iteration focusing on finding a clause with a high coverage of positive examples. Divide-and-conquer works by specializing an overly general hypothesis once, focusing on discriminating positive from negative examples. Experimental results are presented demonstrating that there are cases when more accurate hypotheses can be found by divide-and-conquer than by covering. Moreover, since covering considers the same alternatives repeatedly it tends to be less efficient than divide-and-conquer, which never considers the same alternative twice. On the other hand, covering searches a larger hypothesis space, which may result in that more compact hypotheses are found by this technique than by divide-and-conquer. Furthermore, divide-and-conquer is, in contrast to covering, not applicable to learning recursive definitions.
BibTeX
@inproceedings{bostrom1995covering,
  author = {Henrik Boström},
  title = {{Covering vs. Divide-and-Conquer for Top-Down Induction of Logic Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure