Relational Knowledge Extraction from Attribute-Value Learners

Manoel V. M. França, Artur S. d'Avila Garcez, Gerson ZaveruchaIccsw 2013 · DOI

TL;DR

This paper introduces a novel algorithm to translate knowledge learned by attribute-value learners on propositionalized relational data back into first-order logic rules. This approach aims to bridge the gap between efficient propositional learning and the expressiveness of relational representations, offering comparable accuracy to traditional ILP systems but with significant speedups and enhanced representational power.

What Problem Does This Paper Address?

Relational learning aims to extract knowledge from data with complex relationships, often represented in first-order logic. Inductive Logic Programming (ILP) systems tackle this directly but can be computationally expensive. An alternative is "propositionalization," where relational data is transformed into a format understandable by faster attribute-value learners. However, this process can lead to information loss, making it difficult to represent the learned knowledge back in first-order logic. Bottom Clause Propositionalization (BCP) is a recent method that achieves good accuracy with attribute-value learners but still struggles with extracting interpretable first-order rules. This paper addresses the challenge of consistently and accurately extracting first-order rules from knowledge learned by attribute-value learners that have processed BCP-propositionalized data.

Methods

The core contribution is a novel algorithm for extracting first-order rules from "BCP-rules" (rules learned from BCP-propositionalized data). The process involves three main steps:

  1. Unconstrained Variables Search: Identifies variables within BCP-rules that do not have their scope constrained by other literals in the rule's body. These are variables whose presence or absence in the background knowledge might lead to unintended consequences when the rule is interpreted as first-order logic.
  2. Unconstrained Variables Replacing: Uses a hash table generated during the BCP process to replace these unconstrained variables with grounded constants. This step leverages Theorem 2, which demonstrates that a BCP feature is semantically equivalent to a disjunction of its possible unifications across examples.
  3. First-Order Filtering: Applies a modified version of the T-reduce algorithm (originally for ILP) to filter the generated first-order rules. This step removes redundant literals and, crucially, literals that do not contain variables. The rationale is that such literals, like the negated dad(E, F) in an example, can become universally true or false depending on the background knowledge, hindering generalization.

The algorithm is designed to be learner-agnostic, but the authors evaluate it using the RIPPER propositional rule learner.

Datasets

The paper evaluates its methodology on four Alzheimer's disease datasets: Alz-ami, Alz-ace, Alz-mem, and Alz-tox. These datasets are part of the Alzheimers benchmark.

Key Insights and Ideas

  • Bridging the Propositional-Relational Divide: The paper offers a practical way to recover the expressiveness of first-order logic from the efficiency of propositional learning, which is a significant challenge in relational data mining.
  • Handling Unconstrained Variables is Crucial: The identification and proper grounding of unconstrained variables are key to ensuring that extracted first-order rules are consistent and generalize well, avoiding issues where literals might always evaluate to true or false.
  • BCP's Strengths and Weaknesses: While BCP enables attribute-value learners to achieve competitive accuracy, its propositional nature inherently obscures the relational structure. This work directly tackles that obscuration.
  • Enhanced Representational Power: The extracted rules can represent disjunctions and negation as failure, capabilities not typically found in standard ILP systems when dealing with propositionalized data.

Key Results

The proposed methodology, when applied with RIPPER and evaluated against traditional ILP systems like Aleph, demonstrates:

  • Comparable Accuracy: The extracted first-order rules (BCP+RIP FOL) achieve accuracy comparable to Aleph and the propositional BCP+RIPprop on several datasets.
  • Significant Speedup: The approach is considerably faster than Aleph, achieving an average speed-up of over an order of magnitude.
  • Smaller Rule Sets: The generated first-order rules are smaller (fewer literals) than those produced by Aleph.
  • Improved Representation: The extracted rules can represent disjunctions and negation as failure, offering greater expressiveness.

Limitations and Future Work

  • Learner Agnosticism: While the algorithm is presented as learner-agnostic, it was evaluated using RIPPER. Further investigation is needed to confirm its effectiveness with other propositional rule learners.
  • Numerical Data: The current experiments focus on symbolic data. Future work includes experiments on datasets with numerical (continuous) data, such as Carcinogenesis.
  • Large-Scale Data: Experiments with very large datasets, like CORA, are also planned.
  • Mode Declarations: A new version of RIPPER that satisfies mode declarations for learning with BCP is being studied to further enhance the learning process.

Summary updated

BibTeX
@inproceedings{franca2013relational,
  author = {Manoel V. M. França and Artur S. d'Avila Garcez and Gerson Zaverucha},
  title = {{Relational Knowledge Extraction from Attribute-Value Learners}},
  booktitle = {Iccsw},
  year = {2013},
  doi = {10.4230/oasics.iccsw.2013.35},
}
Figure