Provenance for the Description Logic ELHr

Camille Bourgaux, Ana Ozaki, Rafael Peñaloza, Livia PredoiuIJCAI 2020 · DOI

TL;DR

This paper introduces a novel framework for handling provenance in the Description Logic ELHr, a language used for knowledge representation. The authors extend existing provenance techniques to track how conclusions are derived from ontologies, addressing challenges posed by the logic's expressive features like conjunctions. This work is crucial for building more transparent and trustworthy AI systems that rely on complex knowledge bases.

What Problem Does This Paper Address?

In many AI applications, understanding why a system reached a particular conclusion is as important as the conclusion itself. This is especially true when dealing with ontologies, which are structured knowledge bases used to represent domain knowledge. Description Logics (DLs) are a family of logics used to build these ontologies. While DLs like ELHr are efficient for reasoning, tracking the provenance (i.e., the specific axioms and facts used to derive a conclusion) in these complex structures has been challenging. Existing methods often struggle with features like conjunctions, which allow combining concepts, and qualified existential restrictions, which express the existence of related individuals with certain properties. This paper tackles the problem of providing robust and informative provenance for ELHr ontologies, enabling users to understand the derivation path of any conclusion.

Methods

The authors adapt a semiring-based approach to provenance, a popular technique in database provenance. They define a provenance semantics for ELHr ontologies, where axioms are annotated with provenance tokens. When reasoning, these tokens are combined to form provenance polynomials, which represent the derivation history.

Key methodological contributions include:

  • Handling Conjunctions: The paper identifies specific difficulties introduced by conjunctions in ELHr and proposes solutions, including assuming multiplicative idempotency of the semiring. This assumption simplifies provenance tracking by ensuring that repeated use of an axiom doesn't inflate its provenance contribution unnecessarily.
  • Syntactic Restrictions: To manage the complexity, the authors introduce a syntactic restriction on ELHr axioms. This restriction preserves the expressivity of the full logic when provenance is not considered but simplifies provenance tracking.
  • Completion Algorithm: A core contribution is a completion algorithm, adapted from existing DL reasoning techniques. This algorithm iteratively adds new annotated axioms to an ontology until it's "saturated," effectively deriving all possible provenance-annotated consequences. This algorithm is crucial for reasoning tasks like axiom entailment and query answering.
  • Query Answering Adaptation: The paper extends existing methods for answering conjunctive queries (CQs) in DLs to handle provenance. This involves constructing a canonical model of the ontology and rewriting queries to incorporate provenance information.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and algorithmic design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Conjunctions are Tricky for Provenance: The paper highlights that the straightforward combination of provenance tokens for conjunctive axioms can lead to unintuitive results. The proposed solution, using idempotent semirings, is a clever way to manage this complexity.
  • Provenance vs. Minimality: The authors distinguish their provenance approach from "axiom pinpointing," which seeks minimal sets of axioms. Provenance, in their framework, captures all derivation paths, offering a richer, though potentially less concise, explanation.
  • ELHr's Expressiveness Demands Novel Approaches: The paper demonstrates that standard DL provenance techniques, which work well for simpler DLs, need significant adaptation to handle the features of ELHr. This underscores the trade-offs between expressiveness and the complexity of reasoning and provenance tracking.
  • Completion Algorithms are Powerful Tools: The development of a completion algorithm for annotated ELHr ontologies is a significant step, providing a concrete mechanism for deriving provenance-annotated consequences.

Key Results

  • Decidability Results: The paper establishes decidability for key reasoning tasks with provenance, including axiom entailment and instance queries, in polynomial time with respect to the ontology size and polynomial space with respect to the provenance monomial size.
  • Relevant Provenance Variables: An efficient polynomial-time algorithm is presented to compute the set of relevant provenance variables for a given query or axiom, helping to identify which axioms contributed to a specific conclusion.
  • Query Answering Complexity: Conjunctive query answering with provenance in ELHr is shown to be decidable in exponential time with respect to the ontology size and the query's provenance information.

Limitations and Future Work

  • Syntactic Restrictions: While necessary for managing provenance complexity, the introduced syntactic restrictions on ELHr axioms might limit the expressiveness of ontologies that can be directly handled. The authors suggest exploring how to relax these restrictions in future work.
  • Non-Idempotent Semirings: The paper primarily focuses on $\times$-idempotent semirings. The authors acknowledge that non-idempotent semirings, which can capture more detailed provenance information (like the number of times an axiom is used), might be relevant for certain applications and leave this as future work.
  • Scalability for Large Provenance: The exponential time complexity for query answering with respect to provenance size is a limitation. Future work could explore more efficient methods for handling large provenance expressions.
  • Empirical Evaluation: The paper is primarily theoretical. Future work could involve implementing the proposed algorithms and evaluating their performance on real-world ontologies and benchmark datasets.

Summary updated

BibTeX
@inproceedings{bourgaux2020provenance,
  author = {Camille Bourgaux and Ana Ozaki and Rafael Peñaloza and Livia Predoiu},
  title = {{Provenance for the Description Logic ELHr}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/258},
}
Figure