TL;DR
This paper introduces a novel method for "abductive reasoning" in description logic ontologies, specifically for the ALC language. It leverages a technique called "forgetting" to generate minimal, independent explanations for observations, addressing a gap in current ontology reasoning capabilities. The proposed method is practical and evaluated on real-world ontologies, demonstrating its effectiveness in generating useful hypotheses.
What Problem Does This Paper Address?
Abductive reasoning is about generating the best explanation for a given observation, often by inferring new knowledge. In the context of Artificial Intelligence and knowledge representation, ontologies (structured representations of knowledge) are increasingly used. However, existing methods for abductive reasoning in description logics (DLs), the formal language used for ontologies, are often not suitable for complex scenarios, lack practical implementations, or don't produce the desired characteristics for hypotheses. Specifically, this paper tackles the challenge of performing ABox abduction (explaining observations about individuals) in ALC ontologies, aiming to produce hypotheses that are:
- Explanatory: They logically explain the observation given the ontology.
- Consistent: They don't contradict the existing knowledge.
- Minimal: They make the fewest assumptions necessary.
- Independent: Each part of the hypothesis is a distinct explanation, not redundant with others.
This is crucial for applications like hypothesis generation, diagnostics, and belief expansion where understanding why something is observed is as important as knowing what is observed.
Methods
The core of the paper's contribution lies in its novel application of "forgetting" (also known as uniform interpolation) for ABox abduction. Here's a breakdown of their approach:
- Forgetting for Uniform Interpolation: Forgetting is a process that removes specified symbols (concepts or roles) from an ontology while preserving all entailments that can be expressed using the remaining symbols. The paper uses a specific tool called LETHE, which implements a resolution-based method for uniform interpolation in ALC, capable of handling ABoxes and disjunctive assertions.
- Abduction via Negation: The fundamental idea is that if an ontology $O$ and a hypothesis $H$ entail an observation $\psi$ ($O, H \models \psi$), then by contraposition, $O, \neg \psi \models \neg H$. The paper leverages this by computing a uniform interpolant $V$ for $(O, \neg \psi)$ with respect to a forgetting signature $F$. The hypothesis $H$ is then derived by negating $V$.
- Handling Redundancy: A key challenge is that directly negating the uniform interpolant often results in hypotheses with many redundant explanations. The paper addresses this through two main steps:
- Annotation-Based Filtering (Approximate): An efficient method is introduced where "annotator" symbols are added to the negated observation. This allows tracing which axioms in the uniform interpolant are "dependent" on the observation. Axioms not containing these annotations are considered redundant and removed. This yields an approximate hypothesis $H_{app}$.
- Full Filtering: For a more rigorous approach, after annotation-based filtering, entailment checks are performed on the remaining axioms to eliminate any remaining inter-disjunct redundancies. This results in a fully compliant hypothesis $H$.
- Abducibles and Forgetting Signature: The set of "abducibles" (symbols allowed in the hypothesis) must include all role symbols. The "forgetting signature" $F$ specifies symbols to be removed, typically concept symbols from the observation. This ensures that the generated hypotheses are focused and informative.
Datasets
The paper evaluates its method on a corpus of real-world ontologies. These ontologies were preprocessed into their ALC fragments. The corpus includes:
- EL ontologies: BFO, LUBM, HOM, DOID, SYN.
- ALC ontologies: ICF, Semintec, OBI, NATPRO.
These ontologies were chosen for their consistency, parsability, and varying sizes to assess performance. The experiments involved generating 30 consistent, non-entailed observations for each ontology, using ALC concepts and operators.
Key Insights and Ideas
- Forgetting as a Powerful Abduction Tool: The paper demonstrates that forgetting, a technique primarily for ontology simplification, can be effectively repurposed for generating abductive hypotheses. This opens up new avenues for reasoning with ontologies.
- The Necessity of Redundancy Elimination: Directly negating uniform interpolants is insufficient for practical abduction. The paper highlights that hypotheses must be cleaned of redundant explanations to be truly useful, and proposes practical methods for this.
- Annotation-Based Filtering is Crucial for Scalability: The annotation-based filtering technique significantly reduces the computational cost of redundancy elimination, making the method practical for large ontologies. Without it, the process becomes prohibitively expensive.
- Iterative Abduction Potential: The paper hints at the possibility of using the full uniform interpolant for iterative abduction, where hypotheses can be refined by further forgetting, creating a cycle of abduction, deduction, and induction.
- Limitations of ALC for Role Assertions: The current method's inability to handle role assertions in observations and hypotheses is a significant limitation, stemming from the underlying forgetting tool's capabilities.
Key Results
- Practicality Demonstrated: The proposed method, implemented in a Java prototype using OWL-API and LETHE, was evaluated on real-world ontologies.
- Efficiency Gains from Annotation Filtering: The annotation-based filtering significantly reduced the time for redundancy elimination. For larger ontologies, full filtering without annotation-based preprocessing was orders of magnitude slower, often failing to complete within reasonable time limits.
- Hypotheses are Minimal and Independent: The experiments showed that the generated hypotheses, especially with full filtering, satisfied the criteria of semantic minimality and inter-disjunct independence.
- No Fixpoints in Practice: In 100% of the experimental cases, the generated hypotheses were represented without fixpoints, suggesting that cyclic, semantically minimal hypotheses are rare in practice.
- Approximate vs. Full Filtering Trade-off: The approximate filtering method provides a good balance between computational cost and hypothesis quality, while full filtering offers stronger guarantees but at a higher computational price.
Limitations and Future Work
- Role Assertions: The method cannot handle role assertions in observations or hypotheses due to limitations in the LETHE tool. Future work aims to address this by removing this restriction.
- TBox Abduction: The paper acknowledges that TBox abduction has different characteristics and will be investigated further.
- Iterative Abduction: The potential for iterative abduction, where hypotheses are refined through repeated forgetting, is identified as a promising area for future research.
- Nominals and Other Logics: The authors suggest that nominals could help overcome limitations related to role assertions, and that extending the approach to more expressive DLs is a natural next step.
- Computational Complexity: While practical, the worst-case complexity for computing hypotheses remains high (3EXPTIME), and further optimizations might be needed for extremely large or complex ontologies.
Summary updated