Case-based reasoning solves a problem by adapting the solution to a similar problem already solved. Motivated in part by the swamping utility problem, case-base maintenance strategies support a compact, competent case base by deleting, modifying, or discovering cases. This research summary briefly presents four case-base maintenance strategies developed by the author: flexible feature deletion, adaptationguided feature deletion, expansion-contraction compression, and predictive case discovery. Flexible feature deletion deletes components of cases instead of whole cases. Adaptation-guided feature deletion prioritizes components for deletion according to their recoverability via adaptation knowledge. Expansion-contraction compression, in addition to deleting cases, also adds cases in unexplored regions of the problem space. And predictive case discovery anticipates and acquires cases expected to be useful for solving future problems.
A case base can contain cases from training data, knowledge engineering by human experts, or the retention phase of the the case-based reasoning cycle. Each case could potentially, through adaptation, solve future problems. If other cases could not solve these problems or could only solve them with greater adaptation cost or inferior solution quality, then that case contributes to overall problem-solving competence. On the other hand, each retained case makes the case base larger. A larger case base requires more storage, more time to search through, more bandwidth to transmit over a network, and more expert attention to manually review.
The swamping utility problem describes this trade-of between the competence, quality, and
speed contribution of a case versus its storage, retrieval, and bandwidth cost [
Maintenance strategies normally make two assumptions: (1) that all cases have a uniform storage cost and (2) that they must retain or delete whole cases. For the first assumption, the storage costs of cases can vary when the cases contain varying amounts of data at varying levels of detail. Furthermore, the storage cost of both the problem and the solution can vary independently because a simple problem may require a complex solution and vice versa. For the second assumption, a maintenance strategy could delete an entire case, but it could also delete a single feature across all cases or a single feature from a single case. Each of these alternatives tends to degrade problem-solving competence –– but not necessarily to the same extent.
Domains that diverge from these two assumptions call for a diferent maintenance strategy:
Flexible feature deletion subdivides variable-size cases for deletion of their components [
Building on flexible feature deletion, instead of ordering features according to a knowledge-light
metric, adaptation-guided feature deletion integrates additional knowledge from the solution
transformation container about the recoverability of features [
A solution with recovered features may exactly match the original uncompressed solution, or it may solve the same problem in a diferent way. Compression to smaller sizes can increase the time required for recovery and decrease the quality of the recovered solution until adaptation knowledge can no longer recover any solution at all. Therefore, in order to preserve problem-solving competence, adaptation-guided feature deletion deletes features in order from most recoverable to least. Evaluation in a path finding domain showed superior retention of competence compared to flexible feature deletion.
Alternatively, instead of deleting features, maintenance could also replace them with a
smaller substitution or abstraction. Occasionally, this reorganization makes case contents more
accessible to adaptation rules of limited power. For example, consider a maintenance strategy
that extracts a component shared by multiple cases into a separate case leaving behind a marker
in the cases from which the component was removed. This decreases the size of the case base by
avoiding duplication. But it also makes the component available for reasoning as a standalone
case independent of the cases from which it came. Even though case-base compression normally
degrades competence, compression under these circumstances, termed creative destruction, can
improve competence instead [
By the representativeness assumption, maintenance strategies predict that future problems will
follow a similar distribution to the current case base [
In these situations, case-base maintenance strategies optimizing for assumed
representativeness may instead cause overfitting. Overfitting means that a statistical model or a machine
learning algorithm makes predictions based on peculiarities in the training data not reflected in
the testing data thereby improving performance on the training data and sacrificing performance
on the testing data [
Case-based reasoning does not normally apply data augmentation, but the solution
transformation container provides a natural source for such adaptations. Expansion-contraction
compression aims to improve competence preservation in case-base compression by combining
exploration and exploitation [
Experimental results show that expansion-contraction compression can outperform condensed nearest neighbor in terms of quality and competence preservation for some datasets –– especially when the training case base has gaps making it unrepresentative of the testing problems. The length of the adaptation path also influences competence retention, with longer paths associated with greater retention. The sparsity of the initial case base afects the competence trend, with a steeper decrease in competence for expansion-contraction compression in the early phases of case base growth. The evaluation suggests that expansion-contraction compression has potential benefits for compression of unrepresentative case bases.
Case-based reasoning depends on three types of regularity: problem-solution regularity,
problem-distribution regularity, and concept regularity. Problem-solution regularity says that
similar problems will have similar solutions, and this is necessary for the adaptation of a solution
to a similar problem to be useful for solving the given problem. Problem-distribution regularity
says that future problems will resemble past problems, and this is necessary for stored cases
to remain useful over time. Concept regularity says that learned concepts remain valid, and
this is necessary for machine learning generally. Leake and Wilson provide a formalization of
problem-solution regularity and problem-distribution regularity [
The many efective applications of case-based reasoning prove that suitable task domains and thoughtful system design provide practical approximations of these regularities. But they are not guaranteed! Changes in the environment, user preferences, technology, or the problem space can degrade regularity and cause practical shortcomings –– especially for long-running systems. Lack of concept regularity, such as a working solution that becomes obsolete, leads to concept drift. Lack of problem-solution regularity, such as a divergence between similarity measures and adaptation rules, leads to problem-solution drift. And lack of problem-distribution regularity, such as heretofore unforeseen problems, leads to problem-distribution drift.
Much machine learning research has explored concept drift [
Predictive case discovery attempts to mitigate problem-distribution drift by anticipating and
acquiring cases expected to be useful for solving future problems. Building on prior work in drift
detection [
Evaluation on four scenarios (no drift, abrupt drift, cyclical drift, and drift from obsolescence) demonstrated that it outperformed baselines. But as the efectiveness of the case discovery strategy depends on characteristics of the drift itself, there is no universal strategy. An important next step is to investigate other strategies for drift detection and case discovery and how to select the ideal strategy for a specific task domain.
The introduction to this research summary explained the swamping utility problem and how it motivates case-base maintenance. Middle sections briefly presented four case-base maintenance strategies that go beyond the deletion of cases by deleting features within cases or discovering new cases: flexible feature deletion, adaptation-guided feature deletion, expansion-contraction compression, and predictive case discovery. Evaluation of these case-base maintenance strategies, compared to appropriate baselines on suitable data sets, generally showed improvements in adaptation cost, competence, or solution quality. Future work will explore how to select the most appropriate strategy or combination of strategies for a particular scenario –– either using domain knowledge to guide maintenance policy or using cross-validation strategies that do not make assumptions about the case distribution.