TL;DR
This paper tackles the challenge of explaining "subsumption" (a core reasoning task) in Description Logics (DLs), particularly those using efficient "normalize-compare" methods. The authors propose a proof-theoretic approach, breaking down complex proofs into modular, understandable "atomic justifications" to make DL reasoning transparent for knowledge engineers.
What Problem Does This Paper Address?
Knowledge-based systems (KBS), especially those providing expert advice, need to be debuggable and capable of justifying their conclusions. Description Logics (DLs) are a powerful formalism for representing knowledge and form the basis of many modern KBS. However, DL reasoners, particularly those employing efficient "normalize-compare" techniques (where knowledge is first transformed into a standard form before comparison), often lack clear explanation facilities. This is problematic because DL inferences can be complex and sometimes yield unexpected results for developers. Traditional explanation methods, like tracing rule firings, are unsuitable for these DL implementations due to the procedural nature of their internal workings, which hides the underlying logic. The paper aims to bridge this gap by providing a principled way to explain subsumption, a fundamental DL inference.
Methods
The core of the paper's approach is to cast DL reasoning into a "natural deduction"-style proof-theoretic framework. Instead of a raw, lengthy proof, the authors propose a two-pronged strategy for generating explanations:
- Decomposition into Atomic Descriptions: Complex DL descriptions are broken down into smaller, independent "atomic descriptions." This simplifies the explanation process by allowing individual components to be explained separately.
- Atomic Justifications: Explanations for these atomic descriptions are provided as "atomic justifications." These justifications are designed to be self-contained and can collapse multiple standard proof rules or highlight specific aspects of a rule's application. They can be "told information" (explicitly asserted by the KB builder), "inheritance" (from parent concepts), or based on specific inference rules like "All" or "Prim."
The authors also discuss implementation aspects, suggesting that explanation systems should ideally be integrated with existing DL reasoners rather than being entirely separate. They advocate for "replaying" the normalization and subsumption algorithms in an explanation mode to reconstruct proofs on demand.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Proof Theory as the Foundation: The paper argues that a deductive framework based on proof rules is the most principled way to explain DL inferences, especially when direct procedural traces are misleading.
- The Problem of Proof Verbosity: Raw proofs generated by formal systems are often too long and detailed for human understanding. This necessitates a mechanism for simplifying and modularizing explanations.
- "Atomic Descriptions" and "Atomic Justifications": These are the key innovations for making explanations digestible. By breaking down complex concepts and providing focused justifications for these smaller parts, the system can present explanations that are both informative and manageable.
- Integrating Explanation with Existing Reasoners: The authors emphasize that building a separate theorem prover for explanations is often impractical. Instead, augmenting existing "normalize-compare" DL reasoners with explanation capabilities is a more viable approach.
- Handling Complex Constructors: The paper touches upon the challenge of explaining constructors like "same-as," which involve graph-like structures and can lead to complex reasoning chains, highlighting the need for careful handling of these cases.
Key Results
The paper presents a theoretical framework and a conceptual design for an explanation system for DLs. It demonstrates the approach with an example of explaining subsumption for a concept involving "at-least" and "prim" constructors. The authors report that their approach has been implemented for the CLASSIC knowledge representation system. While specific quantitative results (e.g., speedups, accuracy improvements) are not detailed, the qualitative outcome is a more transparent and understandable reasoning process for knowledge engineers working with DL-based systems.
Limitations and Future Work
- Defining "Atomicity": The paper acknowledges that defining a universal criterion for "atomic descriptions" is difficult, as many descriptions can be decomposed in multiple ways. They suggest that candidates for atomic descriptions should be found among the components of normalized concepts used in the implementation.
- "Spurious" Conjunctions: The authors identify and discuss "spurious" conjunctions that don't necessarily indicate a lack of atomicity, posing a challenge for automatic decomposition.
- User Control: The need for user control over the explanation process is highlighted, as explanation chains can become long and branching.
- "Surface" Presentation: The paper mentions that the "surface" presentation of explanations (making them more human-readable) is still preliminary.
- Future Work: The authors suggest further work on developing more automated approaches to explanation, handling more complex DL constructs, and refining the presentation of explanations. They also note that their full system explains every inference CLASSIC makes, including individual reasoning and error detection, and offers extensive filtering methods.
Summary updated