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.
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).
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:
- 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.
- 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