Adaptation-Guided Case Base Maintenance

Vahid Jalali, David LeakeAAAI 2014 · DOI

Introduction

Case-Based Reasoning (CBR) systems solve novel problems by retrieving and adapting solutions from a repository of past experiences, known as a case base. As these systems accumulate data, they often encounter the "utility problem," where the computational overhead of searching a massive case base diminishes the efficiency gains of the system. Case Base Maintenance (CBM) aims to mitigate this by selectively pruning the case base to retain only the most valuable cases while preserving overall system competence.

Traditional CBM strategies typically assume that adaptation knowledge—the rules used to modify a retrieved case to fit a new problem—is static and independent of the case base itself. However, in many modern CBR implementations, adaptation rules are derived dynamically from the existing cases. This paper introduces Adaptation-Guided Case Base Maintenance (AGCBM), a novel framework that recognizes the dual role of cases: as potential solutions and as the foundational data for generating adaptation knowledge.

The AGCBM Framework

The core innovation of AGCBM lies in its evaluation of a case's contribution to system competence. Unlike previous methods that focus solely on a case's coverage (the range of problems it can solve as a source), AGCBM considers two distinct components:

  1. Source Case Contribution ($CaseComp$): The effectiveness of a case when used as the starting point for solving other problems.
  2. Adaptation Knowledge Contribution ($AdaptComp$): The utility of a case in generating accurate adaptation rules, specifically through the "case difference heuristic."

By integrating these two metrics, AGCBM ensures that cases essential for deriving powerful adaptation rules are preserved, even if they are not frequently retrieved as primary solutions.

The AGCBM1 Algorithm

The authors present AGCBM1, an implementation tailored for regression tasks. The algorithm employs a leave-one-out evaluation on the initial case base to track the performance of cases in both source and adaptation roles. Cases are then ranked using a weighted formula: $$Comp(C) = \alpha \times CaseComp(C) + (1 - \alpha) \times AdaptComp(C)$$ Experimental results suggest that low values of $\alpha$ often yield the best performance, indicating that a case's role in the adaptation library is frequently more critical than its role as a source solution. Following ranking, a Condensed Nearest Neighbor (CNN) approach is used to select the final subset of cases.

Experimental Results

AGCBM1 was evaluated against five standard maintenance methods—Random Deletion, CNN, Coverage-Based, Reachability-Based, and Relative Coverage—across four UCI regression datasets: Automobile, Auto MPG, Housing, and Computer Hardware.

Figure 1: Mean Absolute Error (MAE) vs. case base size across four datasets. AGCBM1 (circles) consistently achieves the lowest error, particularly at high compression levels.

As shown in Figure 1, AGCBM1 consistently outperformed competing methods across all domains. The performance gap is most significant at high compression rates (small case base sizes), where AGCBM1 maintains high accuracy while other methods' performance degrades.

Figure 6: Percent improvement over random deletion for the Hardware dataset. AGCBM1 shows substantial gains, especially when the number of maintained cases is very low.

In the Hardware domain (Figure 6), AGCBM1 demonstrated an improvement of over 38% compared to random deletion when only 10 cases were maintained. This highlights the algorithm's ability to identify "bridge" cases that facilitate broad system competence through effective adaptation, even in sparse problem spaces.

Conclusion

AGCBM represents a significant shift in case base maintenance by acknowledging that adaptation knowledge is often intrinsically linked to the cases themselves. By prioritizing cases that support accurate adaptation, AGCBM1 achieves superior accuracy and stability compared to traditional footprint-based methods. Future work will focus on scaling the $O(N^2)$ leave-one-out process for larger datasets and extending the framework to classification and symbolic domains.

Summary updated

BibTeX
@inproceedings{jalali2014adaptation,
  author = {Vahid Jalali and David Leake},
  title = {{Adaptation-Guided Case Base Maintenance}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8989},
}
Figure