Enhancing Context Knowledge Repositories with Justifiable Exceptions (Extended Abstract)

Loris Bozzato, Thomas Eiter, Luciano Serafini

Abstract

This paper extends the Contextualized Knowledge Repository (CKR) framework to support "defeasible" global rules—general truths that can be overridden by specific local exceptions. By introducing a formal semantics for "justifiable exceptions" and a translation method into Datalog, the authors provide a practical way to reason with context-dependent knowledge where global assumptions occasionally clash with local realities.

Introduction

In classical logic, knowledge is typically "monotonic": once something is known to be true, adding new information cannot make it false. However, real-world knowledge is often contextual and full of exceptions.

Imagine a tourism recommendation system. Globally, you might have a rule: "Cheap events are interesting." But for a specific user (a "local context"), a cheap football match might be totally uninteresting because they hate sports. In standard logic, these two statements would create a contradiction, breaking the system. The authors address the challenge of exception handling by overriding, creating a system where global knowledge is inherited by default but can be "turned off" in specific contexts if there is a provable justification.

Methodology

The researchers built upon the existing Contextualized Knowledge Repository (CKR) framework, which organizes knowledge into a two-layer structure: a global context and multiple local modules.

The architecture of a Contextualized Knowledge Repository (CKR) showing global context and local modules for a tourism scenario.

Key components of the methodology include:

  1. Defeasible Global Axioms: A new syntax, $D(\alpha)$, representing a global rule that holds "by default."
  2. Justifiable Exceptions: For a global rule to be overridden locally, the system requires a clashing set—a set of local facts that would lead to a logical contradiction if the global rule were applied.
  3. Datalog Translation: To make this computationally feasible, they developed a method to translate these complex Description Logic structures into Datalog programs under Answer Set Semantics (ASP).
  4. CKRew Prototype: A tool called CKRew (CKR Datalog Rewriter) was implemented to automatically convert OWL-RL files into Datalog programs.

Experimental Setup

The paper uses a custom-built scenario for a tourism recommendation system in the Trentino region of Italy. This includes:

  • Global Knowledge: Concepts like Event, Tourist, and City.
  • Local Contexts: Specific instances like a football match (fbmatch) or a specific user's profile (tourist01).
  • Evaluation Sets: Synthetic test sets with varying sizes and percentages of defeasible axioms were used to test the scalability of the CKRew prototype.

Key Insights

  • Parsimony (Occam’s Razor): The system uses exceptions minimally. If a global rule can apply without causing a local contradiction, it must apply.
  • Reasoning by Cases: Via ASP, the framework can present multiple valid "models" or scenarios, allowing for nuanced decision-making.
  • Proof by Contradiction: To verify a negative fact, the system hypothetically assumes the opposite and checks for local knowledge base breakage.
  • Inheritance vs. Contradiction: The framework distinguishes between "normal" and "exceptional" members at the individual level.

Results and Discussion

  • Formal Soundness: The translation to Datalog is proven to be both sound and complete.
  • Computational Complexity: While general satisfiability is NP-complete, model checking can be performed in polynomial time.
  • Scalability: Experimental results confirmed that performance is primarily influenced by the number of defeasible axioms and triggered exceptions, rather than total database size.

Conclusion and Future Work

While the CKRew prototype is successful, future work will focus on:

  • Optimization: Exploring alternative translations to avoid full materialization for extremely large datasets.
  • Justification Safeness: Identifying specific "safe" structures to simplify reasoning.
  • Local-to-Local Defeasibility: Allowing defeasible rules to propagate between similar local contexts.
  • Handling Inconsistency: Exploring how to manage inherently inconsistent local contexts.

Summary updated

Abstract

The Contextualized Knowledge Repository (CKR) framework was conceived as a logic-based approach for representing context dependent knowledge, which is a well-known area of study in AI. The framework has a two-layer structure with a global context that contains context-independent knowledge and meta-information about the contexts, and a set of local contexts with specific knowledge bases. In many practical cases, it is desirable that inherited global knowledge can be "overridden" at the local level. In order to address this need, we present an extension of CKR with global defeasible axioms: these axioms locally apply to (tuples of) individuals unless an exception for overriding exists; such an exception, however, requires a justification that is provable from the knowledge base. We formalize this intuition and study its semantic and computational properties. Furthermore, we present a translation of extended CKRs to datalog programs under the answer set (i.e., stable) semantics and we present an implementation prototype. Our work adds to the body of results on using deductive database technology in these areas, and provides an expressive formalism for exception handling by overriding.
BibTeX
@inproceedings{bozzato2018enhancing,
  author = {Loris Bozzato and Thomas Eiter and Luciano Serafini},
  title = {{Enhancing Context Knowledge Repositories with Justifiable Exceptions (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/786},
}
Figure