Representing Problem-Solving for Knowledge Refinement

AAAI 1999

TL;DR

This paper introduces KRUSTWorks, a framework for building specialized knowledge refinement tools. It proposes a novel "problem graph" structure to represent the reasoning process of a knowledge-based system (KBS), enabling more effective refinement by considering not just the knowledge itself but also how it's used during problem-solving. This approach is crucial for refining complex KBSs that go beyond simple backward chaining.

What Problem Does This Paper Address?

Developing and maintaining knowledge-based systems (KBSs) is challenging. As KBSs are used, their knowledge can become faulty due to errors in initial encoding or changes in the environment. Knowledge refinement tools aim to help debug and update these systems. Existing tools often focus on specific KBS architectures (like Prolog) or applications, and many assume a simple, exhaustive reasoning process. However, real-world KBSs frequently employ more complex reasoning mechanisms, such as non-monotonicity (where conclusions can be retracted or overwritten) and conflict resolution strategies (like rule priorities), which significantly impact how rules are applied and thus how refinement should be performed. The paper addresses the need for a generic knowledge refinement framework that can handle these complexities and represent the dynamic problem-solving process, not just the static knowledge.

Methods

The core of the KRUSTWorks approach is a generic refinement framework that uses a repository of refinement operators and a core refinement algorithm. This algorithm operates on internal representations of the KBS. The key innovation is the problem graph, a knowledge structure designed to capture an individual problem-solving event.

The problem graph has two parts:

  • Positive part: Derived from the KBS's execution trace, it records which rules fired, when they fired, and what facts were asserted or retracted.
  • Negative part: Constructed by backward chaining from a desired conclusion, it identifies rules and facts that could have been applied but weren't, representing potential alternative reasoning paths.

This structure allows the refinement tool to reason about the "blame" for errors and suggest repairs by analyzing the interactions between rules, the order of operations, and the effects of conflict resolution strategies. The paper also discusses how to build this graph from execution traces and static knowledge, and how to use it to generate both "logical refinements" (altering rule content) and "conflict resolution refinements" (altering rule priorities or other conflict resolution mechanisms).

Datasets

Not discussed in the paper. The paper uses a simple, illustrative Clips KBS example to demonstrate the problem graph construction and refinement generation.

Key Insights and Ideas

  • Problem-solving matters more than just static knowledge: Refinement isn't just about fixing rules; it's about fixing how those rules are used in the context of a specific problem-solving session.
  • The "Problem Graph" is crucial: This novel structure explicitly represents the dynamic reasoning process, including both what happened (positive part) and what could have happened (negative part), providing a rich basis for refinement.
  • Chaining direction and conflict resolution are critical: Unlike simpler systems, real-world KBSs often have complex inference mechanisms (forward chaining, non-monotonicity, rule priorities) that significantly alter outcomes. The problem graph is designed to capture these effects.
  • Two types of refinements are needed: Beyond altering rule logic (logical refinements), it's often necessary to adjust how rules are prioritized or selected (conflict resolution refinements).
  • Backward chaining is easier to refine, but forward chaining is more common: The paper acknowledges that backward chaining is more naturally aligned with the retrospective nature of refinement, but the KRUSTWorks approach aims to handle the more prevalent forward chaining.

Key Results

The paper demonstrates the utility of the problem graph and the KRUSTWorks approach through a simple Clips example. It shows how the problem graph can be constructed and how it facilitates the generation of both logical and conflict resolution refinements. For instance, it illustrates how to identify that a desired outcome (result y) was not achieved due to rule priorities and how to suggest increasing the priority of a specific rule (rule5) to achieve the correct outcome. The paper also references prior work where KRUSTTools have achieved competitive results on benchmark KBSs.

Limitations and Future Work

  • Complexity of trace translation: Building the positive part of the problem graph from execution traces can be complex, especially for systems with features like backtracking (e.g., PowerModel), requiring careful translation to map trace events to problem graph nodes.
  • Generic vs. Specific: While the problem graph structure is generic, the translation process from a KBS trace to the problem graph is specific to the KBS's platform.
  • Future Work: The authors suggest that the problem graph approach can be extended to handle more complex reasoning mechanisms and that the KRUSTWorks framework can be used to build a variety of specialized refinement tools. They also note that while the problem graph provides a basis for reasoning about refinements, all proposed refinements are ultimately checked by executing the refined KBS on its native platform.

Summary updated

BibTeX
@inproceedings{1999representing,
  title = {{Representing Problem-Solving for Knowledge Refinement}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure