Inverse subsumption for complete explanatory induction

Yoshitaka Yamamoto, Katsumi Inoue, Koji IwanumaMachine Learning 2012 · DOI

Abstract

In Inductive Logic Programming (ILP), a fundamental trade-off exists between the computational efficiency of Inverse Subsumption (IS) and the logical completeness of Inverse Entailment (IE). While IS offers a structured search space via subsumption lattices, it has historically been viewed as incomplete. This paper demonstrates that IS can be transformed into a complete induction procedure. By utilizing "minimal complements" and the strategic inclusion of tautologies, the authors prove that the search for valid hypotheses can be reduced to navigating a bounded subsumption lattice without sacrificing the ability to find any potential solution.

Introduction

The central objective of Inductive Logic Programming (ILP) is to derive a hypothesis $H$ that, when combined with background knowledge $B$, explains a set of observed examples $E$ (formally expressed as $B \wedge H \models E$). Traditionally, researchers have relied on two primary methods for this task: Inverse Entailment (IE) and Inverse Subsumption (IS).

Inverse Entailment is considered the gold standard because it is logically complete; it is capable of finding any valid hypothesis. However, IE relies on complex, non-deterministic operators such as inverse resolution, which results in a disorganized and computationally expensive search space. Conversely, Inverse Subsumption searches a cleaner, hierarchical "subsumption lattice" that is significantly easier to prune and optimize. The drawback has been the long-held belief that IS is inherently incomplete. This research addresses a critical question: Can the efficiency of Inverse Subsumption be harnessed without losing the completeness of Inverse Entailment?

Bridging the Gap: Minimal Complements and Tautologies

The authors bridge the theoretical gap between entailment and subsumption through two primary mathematical innovations:

1. Residue and Minimal Complements

When negating a "bridge theory"—the intermediate logical step between examples and hypotheses—there are various ways to represent the negation in Clausal Normal Form. The authors define "residue" ($R(S)$) and "minimal complements" ($M(S)$) as specific structural representations of this negation. These constructs allow for a more precise mapping of the hypothesis space.

2. The Tautology Trick

The core innovation of the paper is the realization that the perceived incompleteness of IS is not a flaw of the relation itself, but of the starting representation. By adding language-specific tautologies (logical statements that are always true, such as $P \vee \neg P$) to the bridge theory, the subsumption relation can "capture" hypotheses that previously required complex entailment steps. These tautologies effectively provide the "missing rungs" in the subsumption ladder.

By employing these complements, the authors demonstrate that the induction process can be simplified into a search over a bounded subsumption lattice. This replaces the unstructured search of inverse resolution with a systematic, hierarchical exploration using well-studied refinement operators.

Theoretical Results and Implications

The paper provides a formal proof that inverse subsumption, when combined with minimal complements, ensures the completeness of generalization for explanatory induction. This finding has significant implications for existing ILP tools:

  • Unified Framework: The paper offers a framework to evaluate systems like Progol, HAIL, and CF-induction. It proves that while Progol and HAIL are "partially complete" (guaranteed to find at least one version of a hypothesis), they are not "fully complete" in their standard implementations.
  • Algorithm Optimization: The authors show that CF-induction, a powerful but complex method, can be logically simplified and made more efficient by adopting this new form of inverse subsumption.

Evaluation

As a theoretical breakthrough, the paper validates its claims using several illustrative problems rather than large-scale benchmarks. These include:

  • Market Basket Analysis: Demonstrating the method's utility in identifying customer buying patterns.
  • Biological Pathway Completion: A case study on finding missing links in metabolic or signaling pathways, such as cellular regulation in yeast.
  • Logic Puzzles: Small-scale examples where traditional systems like Progol fail to identify valid hypotheses that the proposed method successfully recovers.

Limitations and Future Work

While the search space is more structured, the authors acknowledge that the "tautology trick" introduces computational challenges. The number of tautologies can grow significantly, potentially leading to a combinatorial explosion. Furthermore, implementing this method efficiently requires high-performance algorithms for computing "minimal hitting sets," a known hard problem.

Future research directions include developing sophisticated heuristics to prune the subsumption lattice and exploring "closed-world" assumptions to limit the number of tautologies required in practical applications.

Summary updated

BibTeX
@article{yamamoto2012inverse,
  author = {Yoshitaka Yamamoto and Katsumi Inoue and Koji Iwanuma},
  title = {{Inverse subsumption for complete explanatory induction}},
  journal = {Machine Learning},
  year = {2012},
  doi = {10.1007/s10994-011-5250-y},
}
Figure