Deductive Module Extraction for Expressive Description Logics

Patrick Koopmann, Jieying ChenIJCAI 2020 · DOI

TL;DR

This paper introduces a novel method for extracting "deductive modules" from expressive description logic (DL) ontologies. These modules are smaller subsets of ontologies that preserve essential logical entailments, making them crucial for ontology analysis and reuse. The proposed approach, based on uniform interpolation, generates modules that are often significantly smaller than those produced by existing methods, offering practical benefits for managing complex knowledge bases.

What Problem Does This Paper Address?

Ontologies, which represent knowledge in a structured way, can become very large and complex. This makes them difficult to analyze, understand, and reuse in different contexts. Module extraction aims to address this by identifying smaller, relevant subsets of an ontology. However, existing methods for extracting modules from expressive description logics (like ALC and ALCH) often produce modules that are still too large or are computationally intractable. The paper focuses on "deductive modules," a specific type of module that preserves entailments expressible within a given signature. The challenge is to efficiently extract these deductive modules, especially for expressive DLs, while ensuring they are useful for practical applications like ontology analysis and reuse.

Methods

The core of the paper's contribution lies in its method for extracting deductive modules based on uniform interpolation. Uniform interpolation is a technique that generates a smaller ontology that captures the same entailments as the original ontology over a specific signature.

Here's a breakdown of their approach:

  • Uniform Interpolation for Expressive DLs: The authors adapt a previously developed uniform interpolation method to handle expressive DLs, specifically ALC and ALCH, which include features like universal roles (∀) and role hierarchies. This adaptation is crucial because existing methods often struggle with these expressive constructs.
  • Annotated Interpolants: A key innovation is the use of "annotated interpolants." During the uniform interpolation process, axioms from the original ontology are "labeled" with fresh concept names. The resulting interpolant then carries these labels, effectively linking parts of the interpolant back to the original axioms. This provides an explanation of why certain axioms are included in the module.
  • Complete Deductive Modules: Using the annotated interpolants, the paper defines and computes "complete deductive modules." These modules ensure that all axioms contributing to entailments within the target signature are included. This is particularly useful for ontology analysis, as it provides a comprehensive view of relevant knowledge.
  • Minimised Robust Deductive Modules: For ontology reuse, robustness under replacement is important – meaning the module should behave like the original ontology even if new axioms are added. The paper presents methods to compute "minimised robust deductive modules." These modules are not only robust but also aim to be as small as possible, without sacrificing the preservation of entailments. They achieve minimality by iteratively removing redundant axioms from the ontology.
  • Handling Pure ALC and Role Hierarchies: The paper also addresses specific cases, such as extracting modules for pure ALC (without universal roles) and incorporating role hierarchies (ALCH). For role hierarchies, they extend their interpolation calculus to explicitly track the usage of role axioms.

Datasets

The evaluation was performed on a corpus of 227 ontologies taken from the DL Classification track of the OWL Reasoner Evaluation (ORE) 2015. These ontologies are described as a balanced and varied mix from various sources, including MOWLCorp, BioPortal, and the Oxford Ontology Repository. Axioms that could not be equivalently expressed in ALCH were removed, and ontologies with fewer than 100 names or more than 100,000 axioms were excluded.

Key Insights and Ideas

  • Deductive Modules are Often Sufficient: The authors argue that for practical applications like ontology analysis and reuse, "deductive modules" are often sufficient, even though stronger module notions exist. This is because they are decidable and potentially smaller.
  • Uniform Interpolation as a Foundation: Uniform interpolation, when adapted for expressive DLs, provides a powerful mechanism for both preserving entailments and tracking their origins within the original ontology.
  • Annotations for Explainability: The use of annotated interpolants is a significant contribution, offering a way to understand why a module contains certain axioms, which is crucial for human comprehension and trust.
  • Completeness vs. Minimality Trade-off: The paper explicitly addresses the tension between wanting a "complete" module (including all relevant axioms) and a "minimal" module (as small as possible). They offer methods for both, catering to different user needs.
  • Practical Benefits of Smaller Modules: The evaluation demonstrates that their method can produce significantly smaller modules compared to existing approaches, which directly translates to improved performance and usability in real-world scenarios.

Key Results

  • Significantly Smaller Modules: The evaluation showed that the minimised deductive modules computed by their method were significantly smaller than those produced by existing tools like T⊥-modules and AMEX. For example, in one category of ontologies, minimised modules had an average size of 122 axioms compared to 1,022 for T⊥-modules.
  • High Success Rate: In 90.9% of cases, uniform interpolation did not cause a timeout, and in 96.4% of cases, they could generate a (possibly approximated) module.
  • Finer Granularity in Self-Contained Modules: When comparing self-contained modules, their method produced "complete-atoms" that were much smaller and more numerous than "star-atoms" from T⊥*-modules, indicating a finer granularity and better decomposition of the ontology. For instance, 70.1% of their complete-atoms contained at most 4 axioms, compared to 39.8% for star-atoms.
  • Efficiency: While their method is more computationally expensive than some existing tools (e.g., AMEX), it offers a better trade-off between module size and computational cost for expressive DLs.

Limitations and Future Work

  • Computational Cost: The paper acknowledges that uniform interpolation can be an expensive operation, and their method is more computationally intensive than some existing tools. They implemented timeouts to manage this.
  • Approximation: For very complex cases or when timeouts are reached, the generated modules might be approximations rather than strictly minimal or complete.
  • Future Work:
    • Investigating the impact of timeouts on module size and quality.
  • Exploring whether precomputed atomic decompositions can speed up computation.
  • Extending the approach to even more expressive DLs, potentially through approximations, as deductive modules can be undecidable in some cases.
  • Further research into the use of uniform interpolation methods for more expressive DLs.

Summary updated

BibTeX
@inproceedings{koopmann2020deductive,
  author = {Patrick Koopmann and Jieying Chen},
  title = {{Deductive Module Extraction for Expressive Description Logics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/227},
}
Figure