Exploiting the Ordering of Observed Problem-Solving Steps for Knowledge Base Refinement: An Apprenticeship Approach

Steven K. Donoho, David C. WilkinsAAAI 1994

Abstract

Traditional knowledge base (KB) refinement often focuses on the final output of a decision-making process. This paper proposes an "apprenticeship" approach that instead leverages the sequential order in which experts gather information. By identifying instances where an expert requests data that the current KB deems redundant, the system can pinpoint specific logical gaps. This method uses the expert's problem-solving sequence as a heuristic to guide the generation of new rules, significantly improving classification accuracy in complex domains like medical diagnosis.

Introduction

In many real-world diagnostic domains, such as medicine or mechanical repair, data acquisition is not instantaneous or free. Information is gathered sequentially, where each step is informed by the results of the previous one. While standard machine learning models often assume all data is available upfront, human experts operate through a dynamic process of hypothesis testing and information gathering.

This paper addresses a critical gap in Knowledge Base (KB) refinement: the failure to utilize the process of problem-solving. The authors argue that the specific sequence of an expert’s attribute requests contains "hidden leverage." If a machine's KB cannot explain why an expert is seeking a specific piece of information at a specific time, it indicates a discrepancy between the machine's logic and the expert's internal model. By treating the system as an "apprentice" observing a master, the KB can be refined to bridge these logical gaps.

The Apprenticeship Approach

The proposed framework consists of a two-stage process designed to detect and repair shortcomings in an existing KB.

1. Detection of Shortcomings

The system monitors an expert's attribute requests in real-time. A "shortcoming" is detected when the expert requests a value for an attribute that the current KB considers irrelevant or redundant based on the information already known. For example, if the KB believes that knowing a patient's age is sufficient to reach a conclusion, but the expert proceeds to ask for a specific test result (e.g., history-noise), the KB identifies a contradiction: "I don't know why you're asking that." This contradiction serves as a precise signal that the expert possesses knowledge missing from the KB.

2. Knowledge Repair

Once a gap is identified, the system attempts to construct a new rule to explain the expert's behavior. The repair process follows a specific logic:

  • Initial Rule Construction: The system starts with a simple hypothesis: unexplained attribute + value -> class.
  • Greedy Refinement: The system then "greedily" adds conditions to this rule. Crucially, it only considers attributes that the expert requested prior to the unexplained attribute in the observed sequence.
  • Purity Validation: The rule is refined using training examples until it reaches a high level of accuracy (purity).

This heuristic-guided search is significantly more efficient than brute-force statistical analysis because it limits the search space to relationships already suggested by the expert's workflow.

Experimental Evaluation

The researchers evaluated the apprenticeship approach using the audiology dataset. To test the refinement process, they established a baseline and a simulated expert:

  • Baseline KB: An initial knowledge base was generated using the C4.5 algorithm trained on a small subset of 100 examples.
  • Expert Simulation: To simulate the sequential requests of a superior problem-solver, the researchers used a C4.5 model trained on a larger, more comprehensive set of 226 examples. This "expert" provided the ordered sequences of attribute requests for the apprentice to observe.

Results and Discussion

The apprenticeship approach demonstrated a significant performance boost in the audiology domain. By refining the initial KB through observed sequences, the system achieved the following results:

  • Baseline Accuracy (C4.5): 67.9%
  • Refined Accuracy: 82.1%
  • Net Improvement: 14.2%

These results suggest that the power of the apprenticeship method lies in its ability to discover attribute-class relationships that are first suggested by the expert's workflow and subsequently verified by data. This is a departure from traditional data mining, which attempts to discover relationships from data alone without the benefit of the expert's procedural heuristics.

Conclusion and Future Work

This research highlights that the order of operations is a window into the expert's mind. Learning is most effective when the system's expectations are violated; the contradiction between the KB's logic and the expert's actions provides a targeted learning signal.

However, several areas remain for future exploration. The current model assumes an optimal expert; in practice, human experts may be inconsistent or make errors, which could introduce noise into the refinement process. Additionally, while the greedy rule-building approach worked well on the audiology dataset, further research is needed to determine how this method scales to high-dimensional domains with hundreds of attributes. Finally, transitioning from simulated experts to real-world human practitioners will be the ultimate test of the apprenticeship metaphor.

Summary updated

BibTeX
@inproceedings{donoho1994exploiting,
  author = {Steven K. Donoho and David C. Wilkins},
  title = {{Exploiting the Ordering of Observed Problem-Solving Steps for Knowledge Base Refinement: An Apprenticeship Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure