Knowledge Base Revision through Exception-Driven Discovery and Learning

AAAI 1999

TL;DR

This paper introduces a novel approach to automatically refine knowledge bases (KBs) by focusing on exceptions to existing rules. By analyzing these exceptions, the system can discover new concepts and relationships, leading to a more robust and accurate KB without extensive manual intervention. This is crucial for building intelligent agents that can learn and adapt in complex domains.

What Problem Does This Paper Address?

Building intelligent agents often involves creating knowledge bases (KBs) that consist of an ontology (describing concepts and relationships) and a set of rules (problem-solving procedures). A common challenge is that ontologies, even when imported from existing sources, are often incomplete. This incompleteness leads to rules that work well for typical cases but fail when encountering specific, nuanced situations – these are called "exceptions." Manually identifying and resolving these exceptions is time-consuming and requires deep domain expertise. This paper addresses the problem of how to automatically discover and resolve these exceptions to improve the accuracy and completeness of KBs, thereby enhancing the agent's problem-solving capabilities.

Methods

The authors propose a mixed-initiative, multi-strategy approach to KB revision. Their core idea is to leverage "exceptions" to existing rules as signals for discovering new knowledge. They categorize exceptions into two types:

  • Negative Exceptions: A positive example that is incorrectly covered by a rule.
  • Positive Exceptions: A negative example that is not covered by a rule.

Their approach involves two main classes of methods:

  • Local Methods: These methods focus on a single rule and its exceptions at a time. They employ techniques like:
  • Analogical Transfer: Identifying discriminating features from positive examples and applying them to other objects, considering similarities and dissimilarities with negative exceptions.
  • Explanation-Based Techniques: Eliciting explanations from a domain expert about why a negative exception is incorrect, which helps discover discriminating features. These methods can lead to local extensions of the ontology and rule refinements.

  • Global Methods: These methods analyze the concept characterizations suggested by local methods across multiple rules. They aim to discover a reduced set of concept characterizations that can resolve exceptions across a broader set of rules. This involves using specialization and generalization operators to combine characterizations and then interacting with the domain expert to identify meaningful concepts. Global methods contribute to extending the ontology with new objects and features.

Datasets

Not discussed in the paper. The paper focuses on the methodology and its evaluation, implying that the methods are demonstrated on general knowledge bases and potentially simulated or expert-provided examples rather than specific, publicly available datasets.

Key Insights and Ideas

  • Exceptions as Knowledge Discovery Signals: The most significant insight is treating rule exceptions not as errors to be simply fixed, but as valuable indicators of missing knowledge or imprecise concepts within the ontology.
  • Bridging the Ontology-Rule Gap: The approach directly addresses the disconnect that arises when rules are more nuanced than the underlying ontology can represent.
  • Mixed-Initiative Learning: The system doesn't operate in isolation; it actively involves the domain expert, making the learning process more efficient and ensuring the discovered knowledge is relevant.
  • Local vs. Global Refinement: The distinction between local methods (rule-specific) and global methods (KB-wide) provides a structured way to incrementally build a more comprehensive KB.

Key Results

The paper describes the approach and its goals rather than presenting specific quantitative results from a formal evaluation. The key outcomes are:

  • KB Revision: The development of a suite of methods that continuously extend the ontology and revise rules.
  • Reduced Exceptions: The ultimate goal is to achieve a KB with fewer exceptions, leading to more competent and efficient problem-solving.
  • Domain Adaptation: The process results in an extended and domain-adapted ontology.
  • Evaluation Focus: The authors emphasize that a significant part of their research is devoted to evaluating the effectiveness of their approach in terms of exceptions removed, impact on other rules, knowledge acquisition effort, and agent performance.

Limitations and Future Work

Limitations:

  • Reliance on Expert Interaction: While mixed-initiative, the methods still require interaction with a domain expert, which can be a bottleneck.
  • Completeness of Initial Ontology: The effectiveness of the methods relies on the initial ontology containing some useful concepts, even if incomplete.
  • Complexity of Exception Handling: The paper acknowledges the complexity of handling both positive and negative exceptions.

Future Work:

  • Formal Evaluation: The authors state their research is devoted to evaluating the approach, implying that detailed quantitative results are a future step.
  • Integration of Methods: Further work on how local and global methods best interact and complement each other.
  • Scalability: Investigating how these methods scale to very large and complex knowledge bases.

Summary updated

BibTeX
@inproceedings{1999knowledge,
  title = {{Knowledge Base Revision through Exception-Driven Discovery and Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure