Technical Summary: Honey, I Shrunk the Hypothesis Space (Through Logical Preprocessing)

Problem Statement

Inductive Logic Programming (ILP) is a form of logical machine learning that searches a hypothesis space for a rule-based hypothesis generalizing training examples and background knowledge (BK). A primary challenge in ILP is the combinatorial explosion of the hypothesis space. Even with simple constraints on rule size and variable count, the number of possible rules can reach millions, leading to a hypothesis space (the powerset of rules) that is computationally intractable to search.

While most existing research focuses on developing efficient search algorithms to navigate these vast spaces, this paper addresses the problem from a different angle: Hypothesis Space Reduction. The goal is to identify and remove "pointless rules"—rules that cannot exist in an optimal hypothesis regardless of the specific training examples—before the search begins. An optimal hypothesis is defined as one that minimizes a cost function, typically prioritizing the minimization of misclassified examples followed by the minimization of hypothesis size (description length).

Methodology

The authors introduce shrinker, a preprocessing system that analyzes the Background Knowledge (BK) to discover logical constraints and prune the hypothesis space. The approach is system-agnostic but is implemented to bootstrap the constraint-based ILP system Popper.

The methodology relies on identifying four distinct types of "pointless rules" that can be soundly removed without eliminating any optimal hypotheses:

1. Unsatisfiable Rules: Rules whose bodies can never be true given the BK.
   • Mechanism: Using Answer Set Programming (ASP), the system checks if a rule template (e.g., containing tail(A,A)) has any grounding that satisfies the BK. If the BK implies properties like irreflexivity or antitransitivity, rules violating these are removed.
2. Implication Reducible Rules: Rules containing a literal that is logically implied by other literals in the body.
   • Mechanism: The system identifies "captured literals" (where all variables appear elsewhere in the rule) and checks if the presence of one literal implies another (e.g., odd(A) implies int(A)). If so, the rule with both literals is redundant. The paper proves that specializations of implication reducible rules are also reducible.
3. Recall Reducible Rules: Rules containing redundant literals determined by the functional dependencies or recall limits of the BK.
   • Mechanism: The system calculates the maximum number of answer substitutions (recall) for subsets of arguments in background relations. If a relation is functional (e.g., succ(A,B) implies a unique B for a given A), a rule containing succ(A,B) and succ(A,C) is reducible because B must equal C.
4. Singleton Reducible Rules: Rules containing a literal that is always true (total) for the domain, where the variables in that literal appear only once in the rule.
   • Mechanism: The system determines if a relation is "total" (e.g., every list has a length) and checks if the literal's variables are "singleton" (appear nowhere else). Such literals provide no discriminatory power and can be removed.

Implementation Details:

• Unsatisfiable/Implication: Implemented via ASP. The system builds templates of second-order literals and uses ASP solvers (clingo) to find counter-examples. If no counter-example exists, the template is deemed pointless.
• Recall: Implemented via a bottom-up approach similar to database dependency discovery. It iterates over BK atoms and argument subsets to compute maximum recall values.
• Singleton: Implemented via ASP to determine if relations are partial or total with respect to specific argument positions.
• Integration: The discovered pointless rules are converted into ASP constraints that are fed into Popper's generate-test-constrain loop, effectively pruning the search space before hypothesis generation begins.

Key Contributions

The paper makes the following specific contributions:

• Problem Definition: It formally defines the Hypothesis Space Reduction Problem, aiming to find a subset of the hypothesis space that retains all optimal hypotheses.
• Theoretical Framework: It defines the four types of pointless rules and provides formal proofs (Propositions 1, 3, 5, and 8) demonstrating that any hypothesis containing these rules is non-optimal and can be safely pruned.
• System Implementation: It introduces shrinker, a system that automatically discovers these constraints from BK without user intervention.
• Correctness Guarantee: It proves (Proposition 9) that shrinker is sound: it never removes an optimal hypothesis.
• Empirical Validation: It demonstrates that shrinker can drastically reduce learning times across diverse domains (visual reasoning, game playing, drug design) while maintaining predictive accuracy.

Experimental Results

The authors evaluated shrinker by comparing Popper's performance with and without the preprocessing step across 419 tasks from seven datasets (including 1D-ARC, IGGP, IMDB, and Zendo).

• Learning Time Reduction: Shrinker significantly reduced learning times. On average, it decreased learning time by 81.1% (a 5.3x speedup). In specific cases, such as the iggp-duikoshi-next_control task, learning time dropped from over 10 hours to just 2 seconds.
• Impact of Rule Types: Removing implication reducible rules had the most significant impact (73.1% average reduction), followed by recall reducible, singleton reducible, and unsatisfiable rules.
• Preprocessing Overhead: The preprocessing step itself is fast. With a 10-second timeout, shrinker successfully identified constraints that led to massive downstream savings. Increasing the timeout to 100 seconds yielded diminishing returns, suggesting 10 seconds is often sufficient.
• Accuracy: Predictive accuracy was generally maintained. In a small fraction of cases (3.6%), accuracy improved because the reduced search space allowed Popper to find better hypotheses within the time limit. In rare cases (5.7%), accuracy decreased due to specific implementation constraints in Popper regarding variable usage, not the logic of shrinker itself.

Significance and Claims

The paper claims that shrinker represents a paradigm shift from "searching efficiently" to "searching less." By leveraging the logical structure of the Background Knowledge, the system discovers where not to search before the ILP system even begins.

The authors emphasize that this approach is:

1. System-Agnostic: The constraints can theoretically be used by any ILP system (e.g., Aleph, ASP-based solvers).
2. Task-Independent: The constraints are derived solely from BK, meaning they can be precomputed and reused across multiple learning tasks that share the same background knowledge.
3. Complementary: It does not replace search algorithms but optimizes the input space for them.

The paper concludes that logical preprocessing is a powerful, underutilized strategy in ILP that can transform intractable learning problems into tractable ones, often reducing learning times from hours to seconds without sacrificing the quality of the learned hypotheses. The authors acknowledge limitations regarding infinite BK (requiring finite grounding for ASP), the closed-world assumption, and non-monotonic ILP, identifying these as areas for future work.