Optimizing Similarity Assessment in Case-Based Reasoning

Armin Stahl, Thomas GabelAAAI 2006

Introduction

Case-Based Reasoning (CBR) is a foundational artificial intelligence technique that solves novel problems by retrieving and adapting solutions from a library of past "cases." The efficacy of any CBR system is fundamentally tied to its similarity measure—the mathematical function used to determine the relevance of historical cases to a current query. Traditionally, defining these measures has been a labor-intensive process requiring significant domain expertise.

This paper introduces a novel framework for automatically optimizing Knowledge-Intensive Similarity Measures (KISM). By shifting from rigid, absolute classification metrics to Relative Utility Feedback (RCUF)—where users indicate relative preferences between cases—the authors demonstrate a method to evolve complex similarity functions and feature weights that significantly outperform standard distance metrics like Euclidean distance.

Methodology

The proposed framework addresses two primary limitations in existing automated optimization: task restriction (limited to binary classification) and scope restriction (limited to feature weight optimization). The authors propose a dual-strategy approach to optimize both global weights and local similarity measures.

Gradient Descent for Feature Weights

To optimize the importance of different attributes, the framework utilizes a differentiable error function. This function compares the system's predicted ranking of cases against a "teacher's" preferred ranking, allowing the system to iteratively refine feature weights to minimize ranking discrepancies.

Evolutionary Algorithms for Local Measures

While weights determine attribute importance, local similarity measures define how specific values (e.g., price ranges or color gradients) are compared. The authors treat these similarity functions as "individuals" within a population. These functions are discretized through sampling and then subjected to mutation and crossover operations to find the "fittest" measure that minimizes retrieval error.

Figure 1: The process of sampling a target similarity measure to create a discrete representation suitable for optimization via Evolutionary Algorithms.

Knowledge-Based Optimization Filters (KBOF)

A significant challenge in using Evolutionary Algorithms (EA) for similarity measures is the risk of overfitting, where the system creates nonsensical rules that only apply to the training set. To mitigate this, the authors introduce KBOFs. These act as "guardrails" by incorporating basic domain knowledge—such as reflexivity (a case must be 100% similar to itself)—to discard unrealistic similarity functions during the evolutionary process.

Experimental Evaluation

The framework was evaluated using standard datasets from the UCI Machine Learning Repository (such as the Hayes-Roth dataset) and simulated product recommendation scenarios involving PCs and used cars. These tests aimed to measure how well the system could learn complex user preferences from minimal feedback.

Key Results and Insights

The research yielded several critical insights into the nature of similarity assessment:

  1. The Power of Relative Feedback: The core finding is that relative feedback ("Case A is better than Case B") is more abundant and easier to acquire in real-world applications than absolute utility labels. This allows CBR to be applied to "softer" domains like e-commerce and personalized recommendation.
  2. Efficiency with Small Data: The system showed marked improvement even with very few training queries. As shown in the experimental results, the inclusion of background knowledge via filters significantly accelerated the learning process.
  3. Impact of Filters: The combination of meta-knowledge and expert knowledge (the "me-Filter") proved most effective. In the Hayes-Roth dataset, this approach reduced classification error from a default of 50% to under 15% with only 100 training examples.
Figure 3: Comparison of classification and regression errors across different filter types. The 'me-Filter' consistently demonstrates the lowest error rates as training examples increase.

Across six different domains, the learned similarity measures significantly outperformed default baselines. In some scenarios, the error rate was reduced to 58% of the baseline error, highlighting the importance of optimizing local similarity shapes rather than just global feature weights.

Conclusion and Future Work

The authors successfully demonstrated that a hybrid approach—combining machine learning with meta-knowledge filters—can produce highly accurate similarity measures with relatively little training data. While overfitting remains a risk in extremely data-scarce environments, the use of KBOFs provides a robust defense. Future research will focus on applying this framework to complex industrial applications and integrating the learned measures with explanation components to ensure the system's reasoning remains transparent to human users.

Summary updated

BibTeX
@inproceedings{stahl2006optimizing,
  author = {Armin Stahl and Thomas Gabel},
  title = {{Optimizing Similarity Assessment in Case-Based Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure