Abstract: Inductive logic programming (ILP), or relational learning, is a powerful paradigm for machine learning or data mining. However, in order for ILP to become practically useful, the efficiency of ILP systems must improve substantially. To this end, the notion of a query pack is introduced: it structures sets of similar queries. Furthermore, a mechanism is described for executing such query packs. A complexity analysis shows that considerable efficiency improvements can be achieved through the use of this query pack execution mechanism. This claim is supported by empirical results obtained by incorporating support for query pack execution in two existing learning systems.
Introduction
Inductive Logic Programming (ILP) and relational data mining algorithms learn rules from complex, multi-relational data using first-order logic. To find optimal rules, these algorithms typically employ a "generate-and-test" approach, creating a massive space of candidate hypotheses and evaluating them against a dataset.
The primary bottleneck in this process is computational redundancy. Candidate hypotheses are usually evaluated independently, even though they are generated by incrementally refining previous ones and thus share significant structural prefixes. For instance, an algorithm might test p(X), q(X,a) followed by p(X), q(X,b). A standard Prolog engine recomputes the shared prefix p(X) for every variation, making ILP practically infeasible for large-scale datasets.
Methodology: Query Packs and ilProlog
To address this redundancy, the authors propose a novel execution strategy centered on Query Packs. Instead of treating queries as a flat list, similar queries are organized into a prefix tree. The shared components form the trunk, while variations branch out as nested disjunctions.
The execution mechanism incorporates several key innovations:
- Tree-Structured Evaluation: Queries are merged into a prefix tree to ensure shared parts are processed only once.
- Smart Pruning: In standard Prolog, disjunctions are evaluated sequentially with exhaustive backtracking. The proposed mechanism "prunes" successful branches for specific training examples, preventing redundant re-evaluation during backtracking.
- Low-Level WAM Extension: High-level meta-interpreters proved too slow due to administrative overhead. Consequently, the authors modified the Warren Abstract Machine (WAM) to create
ilProlog. This dedicated engine uses a "pack table" to manage alternatives in memory efficiently at a low level.
Experimental Evaluation
The approach was integrated into two ILP systems: TILDE (a first-order decision tree inducer) and WARMR (a frequent pattern discovery algorithm). Evaluation was conducted on two primary datasets:
- Mutagenesis: A real-world benchmark involving structural descriptions of 230 molecules.
- Bongard Problems: An artificial dataset of geometric patterns, scaled from 1,000 to over 6,000 examples to test scalability and complexity.
Key Results
- TILDE Performance: The system achieved speedups between 2x and 75x. The gains scaled super-linearly with hypothesis complexity, as deeper trees provide more opportunities for prefix sharing.
- WARMR Performance: Speedups ranged from 1.5x to 8x. Gains were lower than TILDE because WARMR’s level-wise search naturally prunes infrequent branches, narrowing the query packs and reducing the potential for shared computation.
- Engine Benchmarking: Even without query packs, the
ilPrologengine performed competitively with state-of-the-art systems like SICStus, ensuring that the observed speedups were due to the pack mechanism rather than a weak baseline.
Conclusion
Redundancy in hypothesis evaluation is a major barrier to ILP scalability. Query packs effectively exploit the structural similarity of candidate rules to minimize this overhead. Theoretical and empirical results demonstrate that "broom-like" query structures—those with long shared prefixes—yield the most significant gains. Future work may involve adapting multi-query optimization techniques from relational databases or combining query packs with stochastic sampling methods to further enhance efficiency.
Summary updated