Detecting Discontinuities in Case-Bases

AAAI 1996

Sure, here's a blog-style summary of the paper "Detecting Discontinuities in Case-Bases":

TL;DR

This paper introduces a method for detecting "discontinuous cases" in case-based reasoning (CBR) systems. These are cases that, while similar in input, have significantly different outputs compared to their neighbors, often indicating valuable exceptions or anomalies. By identifying these, CBR systems can avoid generating incorrect solutions and potentially uncover new insights.

What Problem Does This Paper Address?

Case-based reasoning (CBR) systems work by retrieving similar past cases to solve new problems. This relies on a core assumption: similar inputs should lead to similar outputs. However, real-world data often contains "discontinuous cases" – records that are retrieved by a query but have output values that are drastically different from the majority of other retrieved cases. If not handled, these discontinuities can lead CBR systems to adapt incorrect solutions, undermining their reliability. The paper aims to address this by developing a mechanism to automatically detect and flag these discontinuous cases within a case-base.

Methods

The proposed method involves a three-step process:

  1. Retrieving Maybe Similar Cases (MSCs): When a user provides an input specification, the system first retrieves all cases whose input specifications are the same or similar to the user's query, within a defined "input threshold."
  2. Selecting a Base Case (BC): From the retrieved MSCs, the system identifies the single case that most closely matches the user's input specification. This "Base Case" serves as a reference point.
  3. Detecting Discontinuous Cases: The output specifications of all other MSCs are compared to the output specification of the Base Case. If the difference exceeds a pre-defined "output threshold," the case is flagged as discontinuous.

This method is implemented within an enhanced version of the CARET (Case-based retrieval tool) system, which operates on commercial RDBMS. CARET efficiently retrieves similar cases by generating SQL queries based on similarity definitions and weights. The extension focuses on the third step, comparing output similarities against the Base Case.

Datasets

The paper uses package tour data as a running example to illustrate discontinuities. For empirical evaluation, the system was tested on a case-base of 1,500 cases, with experiments conducted using ORACLE version 6 on SunOS version 4.1.2.

Key Insights and Ideas

  • Discontinuities are not always errors: While they can lead to incorrect adaptations in CBR, discontinuous cases often contain valuable information, like exceptional pricing or unique product behaviors.
  • Context matters for discontinuity: Whether a case is considered discontinuous depends on the observed attributes, the neighboring cases it's compared against, and potentially "hidden" attributes (derived values like total cost for a family).
  • The Base Case is crucial: The method relies on a single, most similar case as a reference to define what constitutes a "normal" output for a given input.
  • Efficiency is key: The paper highlights the challenge of efficiently retrieving cases from large RDBMS and how CARET's SQL generation approach addresses this.

Key Results

The extended CARET system successfully retrieves not only similar but also discontinuous cases. Empirical results show that the system achieves acceptable response times, with an average query response time of about 2.0 seconds even with a case-base of 1,500 records. The number of detected discontinuous cases varied depending on the query characteristics (e.g., query length, tree depth) and the defined thresholds. For example, one query retrieved 105 cases, of which 102 were similar and 3 were discontinuous.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Generalizing Discontinuities: Currently, discontinuous cases are identified individually. The authors suggest that if many individual cases of the same type are flagged as discontinuous, the system should attempt to generalize them and warn domain experts about potential unrecognized common problems.
  • Attribute Selection: Determining which attributes are most important for detecting discontinuities is challenging. The paper notes that discontinuities depend on observed attributes, and monitoring all attribute combinations is inefficient. Future work should focus on methods for selecting the most relevant attributes.
  • Hidden Attributes: While the paper mentions hidden attributes, their automatic detection and incorporation into the discontinuity detection process are not fully explored.

Summary updated

BibTeX
@inproceedings{1996detecting,
  title = {{Detecting Discontinuities in Case-Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure