A Case‐Addition Policy for Case‐Base Maintenance

Qiang Yang, Jun ZhuComputational 2001 · DOI

TL;DR

This paper introduces a novel "case-addition" policy for maintaining case-based reasoning (CBR) systems, aiming to build concise case bases with high coverage quality. The proposed algorithm guarantees a coverage that is at least 63% of the optimal case base and is computationally efficient, offering a valuable alternative to traditional case-deletion methods.

What Problem Does This Paper Address?

Case-Based Reasoning (CBR) systems rely on a collection of past cases (a case base) to solve new problems. As new cases are added, the case base can grow significantly, leading to issues like redundancy, increased retrieval time, and difficulty in understanding the system's knowledge. This problem, known as "case-base maintenance" (CBM), is crucial for the efficiency and effectiveness of CBR systems. While much research has focused on deleting cases to manage size and maintain competence, this paper addresses the complementary problem of adding cases strategically to build a high-quality case base from scratch. The goal is to create a case base that is both concise and offers excellent "coverage," meaning it can effectively solve a wide range of problems.

Methods

The core of this paper is a case-addition algorithm. Instead of deleting cases, this algorithm iteratively selects cases from a larger pool to build a new, smaller case base. The selection process is guided by the concept of "benefit," which is defined as the additional coverage a case brings to the case base being constructed. Specifically, the algorithm greedily selects the case that offers the maximum benefit with respect to the cases already added. This process continues until a desired case base size is reached or no further significant coverage can be gained.

The paper also introduces a formal definition of "coverage" based on the "neighborhood" of cases. A case's neighborhood is the set of other cases whose solutions can be reached with a small adaptation cost. Coverage is then defined as the proportion of the total problem space covered by the union of the neighborhoods of cases in the case base.

Datasets

The paper does not introduce new benchmark datasets. Instead, it uses two experimental domains for evaluation:

  • Towers of Hanoi: A classic planning problem with a defined state space.
  • Path-finding domain: A custom domain representing movement between cities.

For these domains, the authors generated problem instances and solved them using a best-first forward-chaining planner to create the initial case data.

Key Insights and Ideas

  • Benefit Reduction as a Predictor: The paper highlights that the rate at which the "benefit" (additional coverage) of new cases decreases is a strong indicator of how quickly the case base achieves high coverage. Faster benefit reduction implies faster convergence to good coverage.
  • Global View for Addition: Unlike deletion policies that might focus on local optimality, case addition allows for a more global view of how cases contribute to overall coverage, potentially leading to better-structured case bases.
  • Theoretical Guarantees: The proposed case-addition algorithm comes with a theoretical guarantee: the coverage of the resulting case base is at least 63% of the optimal case base for a given size. This provides a strong theoretical foundation for its effectiveness.
  • Coverage vs. Size Relationship: The paper analytically derives relationships between case base size and coverage, showing how linear and exponential decreases in benefit reduction lead to different coverage curves. This allows for prediction of coverage based on expected benefit reduction.

Key Results

  • Near-Optimal Coverage: The case-addition algorithm is shown to produce case bases with coverage at least 63% of the optimal case base.
  • Efficiency: The algorithm has a time complexity of O(n²), comparable to some case-deletion algorithms, making it computationally feasible.
  • Experimental Performance: In the Towers of Hanoi domain, the case-addition policy achieved full competence with 58 cases, significantly outperforming a randomly selected set of 200 cases and also outperforming a case-deletion policy.
  • Coverage Prediction: The paper demonstrates that the rate of benefit reduction (linear vs. exponential) significantly impacts how quickly coverage is achieved, providing a predictive model for coverage based on benefit reduction trends.

Limitations and Future Work

  • Worst-Case Guarantee: The authors acknowledge that while the algorithm has a worst-case guarantee, they do not claim it is always better than other CBM policies on average. Average-case analysis would require more detailed problem distribution analysis.
  • Future Work: The authors plan to develop algorithms that can dynamically update case bases by tracking adaptation costs and neighborhood estimates, allowing for incremental decision-making on how to update a case base in real-world scenarios.

Summary updated

Abstract

A major problem in many practical applications of case‐based reasoning (CBR) and knowledge reuse is how to keep the case bases concise and complete. To solve this problem requires repeated maintenance operations to be applied to case bases. Different maintenance policies may result in case bases with very different quality. In this article, we present a case‐addition maintenance policy that is guaranteed to return a concise case base with good coverage quality. We demonstrate that the coverage of the case base computed by the case‐addition algorithm is no worse than the optimal case‐base coverage by a fixed lower bound. We also show that the algorithm implementing the case‐addition policy is efficient. Our result also highlights benefit reduction as a key factor in influencing the convergence of case‐base coverage when cases are added to a case base. Through our theoretical analysis, we analytically derive the well known coverage convergence curves commonly displayed in CBR experiments and show that benefit reduction can be used as a predictor for convergence speed.
BibTeX
@inproceedings{yang2001caseaddition,
  author = {Qiang Yang and Jun Zhu},
  title = {{A Case‐Addition Policy for Case‐Base Maintenance}},
  booktitle = {Computational},
  year = {2001},
  doi = {10.1111/0824-7935.00143},
}
Figure