TL;DR
This paper formalizes and compares two top-down inductive learning strategies, "covering" and "divide-and-conquer," within the context of logic programming. It demonstrates that while divide-and-conquer can be more efficient and produce more accurate hypotheses in certain scenarios, it struggles with learning recursive definitions, a limitation that covering does not share.
What Problem Does This Paper Address?
Inductive logic programming (ILP) aims to learn logic programs from data. A key challenge in ILP is developing efficient and effective search strategies for discovering these programs. Traditionally, propositional learning has utilized two main top-down search techniques: covering and divide-and-conquer. While covering has been extensively adapted for ILP, divide-and-conquer has seen less formalization and application in this domain. This paper addresses this gap by formalizing divide-and-conquer for logic programs and conducting an empirical comparison with the covering approach to understand their respective strengths and weaknesses.
Methods
The paper formalizes both the covering and divide-and-conquer algorithms for top-down induction of logic programs.
- Covering: This approach iteratively specializes an overly general hypothesis. In each step, it selects a clause that covers a subset of positive examples and no negative examples, refining it until all positive examples are covered. The specialization operator used is "goal reduction," which involves resolving a literal in a clause's body with a background clause.
- Divide-and-Conquer: This strategy also starts with an overly general hypothesis. If a clause covers both positive and negative examples, it is "unfolded" into multiple clauses. These new clauses are then recursively processed. Clauses covering only positive examples are added to the hypothesis, while those covering only negative examples are discarded. This approach is also formalized using goal reduction for specialization.
A key distinction highlighted is the hypothesis space explored by each method. The paper argues that divide-and-conquer's hypothesis space is a subset of covering's, potentially leading to more compact hypotheses with covering.
Datasets
The paper evaluates the algorithms on three domains:
- King-Rook vs. King-Pawn (UCI repository): This domain involves learning to distinguish between king-rook and king-pawn positions in chess.
- Tic-Tac-Toe (UCI repository): This domain focuses on learning to predict the winner in Tic-Tac-Toe games.
- Natural Language Parsing (from Bratko, 1990): This domain involves learning a definite clause grammar for sentence parsing.
For the UCI datasets, attribute vectors were transformed into atoms. The paper also discusses the construction of overly general hypotheses for these domains, including the use of intermediate predicates to potentially improve accuracy.
Key Insights and Ideas
- Divide-and-Conquer's Efficiency: Divide-and-conquer generally performs fewer "checks" (evaluating if a clause covers an example) than covering, suggesting it is more computationally efficient. This is attributed to divide-and-conquer never considering the same alternative twice, whereas covering can revisit alternatives.
- Accuracy Trade-offs: Divide-and-conquer can sometimes produce more accurate hypotheses, particularly when focusing on discriminating positive from negative examples. However, covering's larger hypothesis space might lead to more compact hypotheses.
- Recursive Definition Limitation: A significant drawback of divide-and-conquer is its inapplicability to learning recursive definitions. This is because decisions made for one subset of examples can affect others in a recursive context, which the divide-and-conquer algorithm, as formalized here, cannot handle. Covering, on the other hand, can be extended to handle recursive predicates.
- Importance of Background Knowledge: The experiments suggest that the use of background knowledge (e.g., intermediate predicates) can have a more substantial impact on hypothesis accuracy than the choice of search technique itself.
Key Results
- Efficiency: In the King-Rook vs. King-Pawn domain, covering performed up to 3.3 times more checks than divide-and-conquer for the largest training set size. Similar trends were observed in other domains, with covering performing significantly more checks (e.g., 30.3 times more in the DCG domain without intermediate predicates).
- Accuracy: Divide-and-conquer generally produced more accurate hypotheses than covering in the King-Rook vs. King-Pawn domain across various training set sizes. In the Tic-Tac-Toe domain, covering performed better than divide-and-conquer, both with and without intermediate predicates. The DCG domain showed that covering and divide-and-conquer produced identical hypotheses when intermediate predicates were not used.
- CPU Time: While not the primary measure, CPU times generally correlated with the number of checks, with covering taking longer in most scenarios.
Limitations and Future Work
- Recursive Definitions: The paper explicitly states that divide-and-conquer, as formalized, is not applicable to learning recursive definitions. While a transformation to non-recursive hypotheses is mentioned as a workaround, it prevents learning recursive definitions directly. The authors note that techniques exist to handle recursive definitions with unfolding and clause removal, suggesting future work in this area.
- Termination Conditions: The paper suggests that termination conditions could be relaxed to allow for a broader range of valid hypotheses.
- Specialization Operator: The authors used "goal reduction" as the specialization operator but note that "literal addition" could also have been used, potentially leading to different results or formalizations.
- Hypothesis Space: The paper highlights that covering explores a larger hypothesis space, which can lead to more compact hypotheses. However, the experiments don't explicitly quantify this difference in compactness.
Summary updated