Signature-Based Abduction with Fresh Individuals and Complex Concepts for Description Logics

Patrick KoopmannIJCAI 2021 · DOI

TL;DR

This paper investigates "signature-based abduction" in Description Logics (DLs), a reasoning technique for finding explanations for observations that don't logically follow from existing knowledge. The authors introduce and analyze the computational complexity of abduction that allows for "fresh individuals" (previously unknown entities) and "complex concepts" (sophisticated descriptions of entities) within hypotheses, providing tight bounds on hypothesis size and complexity.

What Problem Does This Paper Address?

In knowledge representation, we often use Description Logics (DLs) to build knowledge bases (KBs) that combine general domain knowledge (ontology) with specific facts (ABox). DL reasoners can infer implicit information. However, sometimes we encounter observations that cannot be explained by the current KB. Abduction is the process of finding a missing piece of knowledge (a hypothesis) that, when added to the KB, makes the observation logically follow.

This paper focuses on "signature-based ABox abduction." This means:

  1. ABox Abduction: The observation and hypothesis are sets of facts (ABoxes).
  2. Signature-Based: The hypothesis is restricted to use only names (concepts and roles) from a predefined "signature" (Σ). This helps ensure the hypothesis is relevant and explanatory, rather than just a trivial addition.

The core challenge addressed is that most existing signature-based abduction approaches either restrict hypotheses to be "flat" (simple assertions) or use less expressive DLs. This limits their ability to explain complex phenomena. The authors argue that real-world explanations often require introducing new, previously unknown individuals ("fresh individuals") and using sophisticated concept descriptions ("complex concepts"). They aim to understand the computational implications of allowing these features in signature-based ABox abduction.

Methods

The paper formally defines signature-based ABox abduction for various DLs, ranging from the simpler EL to more expressive ones like ALC, ALCI, and ALCQI. The key methodological contributions are:

  • Formalizing Abduction with Fresh Individuals and Complex Concepts: They extend the definition of abduction to explicitly allow hypotheses to contain fresh individuals and complex DL concepts. This significantly broadens the space of possible hypotheses.
  • Complexity Analysis: They systematically analyze the computational complexity of deciding whether a hypothesis exists and whether a hypothesis of a bounded size exists for different DLs. This involves proving lower bounds (hardness results) and upper bounds (feasibility results).
  • Size Bounds: They derive tight bounds on the size of hypotheses, showing how the expressivity of the DL and the allowance of fresh individuals/complex concepts impact the potential size of explanations.
  • Model Abstraction: For more expressive DLs (like ALC), they introduce the concept of "interpretation abstraction" and "hypothesis abstraction" as an intermediate step to manage the complexity of reasoning with complex concepts and potentially infinite models. This abstraction helps in constructing and verifying hypotheses.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and bounds rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Fresh Individuals and Complex Concepts are Crucial (and Costly): The paper demonstrates that allowing fresh individuals and complex concepts is often necessary for finding explanations, but it comes at a significant computational cost, potentially leading to exponentially larger hypotheses.
  • DL Expressivity Matters Dramatically: The complexity of abduction problems varies significantly with the expressivity of the DL. For instance, EL abduction is relatively tractable, while ALCF abduction is undecidable, and ALC abduction can lead to triple exponential hypothesis sizes.
  • Size Bounds are Key: Understanding the bounds on hypothesis size is critical. The paper shows that for some DLs, hypotheses can be exponentially larger than the input KB, while for others, no general bound exists. This motivates the study of "size-restricted abduction."
  • Trade-offs Between Completeness and Size: The authors highlight that while approaches like uniform interpolation can compute "complete" hypotheses (entailed by any other hypothesis), they can be prohibitively large. Their work focuses on finding any valid hypothesis, which can be smaller but might not be complete.

Key Results

The paper presents several theoretical results concerning the complexity and size of hypotheses for signature-based ABox abduction:

  • EL Family: For EL, flat abduction is polynomial. For EL₁, hypotheses can be exponentially large, and size-restricted abduction is NEXPTIME-complete.
  • ALCI Family: For ALCI, hypotheses can be exponentially large. Size-restricted abduction is NEXPTIMENP-complete.
  • ALCF Family: Flat ALCF abduction is undecidable.
  • ALC Family: Hypotheses can be triple exponentially large. Size-restricted abduction is NEXPTIMENP-complete.
  • Size-Restricted Abduction: The paper provides complexity results for size-restricted abduction across various DLs, ranging from NP-complete for EL to 2EXPTIME for ALCQI.

Limitations and Future Work

  • Undecidability for ALCF: The undecidability of flat ALCF abduction is a significant limitation, suggesting that practical solutions for such expressive DLs might require further restrictions or approximation techniques.
  • Complexity of ALC Abduction: The triple exponential size bound for ALC abduction is substantial, indicating that finding explanations in these DLs can be computationally challenging.
  • Future Work: The authors suggest extending their results to ALCI and ALCQI, investigating abduction for conjunctive queries, and exploring abduction with existential rules. They also mention ongoing work on practical methods for computing size-minimal flat hypotheses for EL.

Summary updated

BibTeX
@inproceedings{koopmann2021signature,
  author = {Patrick Koopmann},
  title = {{Signature-Based Abduction with Fresh Individuals and Complex Concepts for Description Logics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/266},
}
Figure