Using Case Provenance to Prop agate Feedbackto Cases and Adaptations⋆David Leake and Scott A. DialComputer Science Department, Lindley Hall 215Indiana UniversityBloomington, IN 47405, U.S.A.{leake, scodial}@cs.indiana.eduAbstract. Case provenance concerns how cases came into being in acase-based reasoning system. Case provenance information has been pro-posed as a resource to exploit for tasks such as guiding case-based main-tenance and estimating case confidence [1]. The paper p resents a newbidirectional provenance-based method for propagating case confidence,examines when provenance-based maintenance is likely to be useful, andexpands the application of provenance-based methods to a new task:assessing the quality of adaptation rules. The paper demonstrates theapplication of the resulting quality estimates to rule maintenance andprediction of solution quality.1 IntroductionCase provenance concerns tracking how the cases in a case-based reaso ning sys-tem came into being, whether from external sources or from internal reasoningprocesses [1]. Just as humans consider a case’s sources when determining itstrustworthiness [2], it may benefit a case-based reas oning system to considerthe origins of externally-provided cases to estimate cases’ applicability or re-liability, and some systems have co ns idered case sources in their reaso ning [3,4]. More generally, internal provenance information provides a basis for CBRsystems to refine their own processing through introspective reasoning (for anoverview of introspective reasoning, see [5]). L e ake and Whitehead [1] hypoth-esized that information about internal ca se provenance—how a CBR systemderived a new case from other cases—can be exploited for many purpos es inCBR system maintenance such as assessing case confidence, explaining systemconclusions, and improving the ability of case-ba se ma intenance to respond todelayed feedback (as might arise CBR tasks such as design or loa n decis ions) orcase obsolescence (as might arise when predicting prices for a real estate domain).In principle, provenance-based methods could also help focus maintenance efforton knowledge containers beyond the case base, such as similarity information oradaptation knowledge.⋆This material is based on work supported in part by the National Science Foundationunder Grant No. OCI-0721674.Leake and Whitehead provided empirical illustrations of the value of prove-nance information to guide maintenance in the case of delayed feedback, a nddemonstrated that provena nce information abo ut adaptation history could helpto estimate case quality. The focus of these approaches is to use provenance toidentify low-confidence cas e s and how those potentially problematic cases arose,in order to anticipate possible problems before the case is applied and, after feed-back is available, to focus maintenance activities on c ases or adaptation ruleswhich may have contributed to the problems.This paper builds on that work, focusing o n how pr ovenance considerationscan enable more effective use of feedback at any time. It advances provenance-based maintenance in thr e e ways. First, it proposes and tests a new bidirectionalstrategy for pr opagating case confidence, and provides a finer-grained examina-tion of the use of provenance information to estimate case quality. Second, itexamines how initial case-base quality affects the benefit of provenance-basedfeedback propagation. Third, it presents and evaluates a first study of the use ofprovenance information to guide maintenance of case a daptation rules, a novelarea for CBR s ystem maintenance. Experimental studies support the promise ofthese new dir e ctions for exploiting case provenance information.2 Bidirectional Feedback PropagationWhen a CBR s ystem derives new cases from the cases in its c ase library, theirprovenance trace includes the cases from which they were derived and the adap-tations used to derive them. Leake and Whitehead’s work sugge sted that propa-gating feedback to related cases (as determined by adaptation history) providesa computationally practical and effective way of exploiting feedback concerningflawed conclusions. Their studies considered the effects of propagating feedbackeither to parents of a case—the cases from which the case was derived—or to thecase’s children—cases which had been derived from it prior to the feedback be-ing received. Both methods were shown to improve performa nce, but downwardpropagation (to descendants) performed better in their tests [1].To determine whether a bidirectional method could improve on both, wedeveloped the algorithm shown in Figure 2. When the system receives feedbackon a case, it pr opagates the feedback to the case’s ancestors and repeats anyadaptations to descendants (we will refer to this as repairing the case base).An example of a case base with adaptation provenance is shown in Fig. 1(a);Fig. 1(b) then gives an ex ample of the propagation of feedback if the feedbackwas given for “Cas e 4.” We note that adapting children to find solutions for theproblems of their par e nt cases is not always po ssible. However, in practice theability to adapt cases is often symmetric, and the algorithm assumes the abilityto perform such adaptation.Two factors complicate the propagation proces s:1. Repeated ancestors: A single case may appear more than once in the ances trytrace.Case 1Case 2 Case 3Case 4 Case 5 Case 6 Case 7(a) Graph of provenanceCase 1Case 2 Case 3Case 4 Case 5 Case 6 Case 7(b) Path of feedback propagationFig. 1. Sample provenance and feedback propagation paths, beginning with “Case 4.”2. Repeated descendants: A single case may appear underneath more than oneparent (e.g., for k-NN with k > 1).Consequently, bidirec tional propagation must address the risk of cycles and mul-tiple paths.To address the problem of repeated ancestors, the algorithm only traversesthe graph upwards to parents which have not yet been visited. Because thesearch is brea dth-first, this ensures that the parent receives feedback along theshortest p ossible chain. By the heuristic of using chain length as a proxy foramount of knowledge degradation during propagation (which has been shown togive reasonable performance in some tests [1]), in the absence of finer-grainedinformation we expect this to be the most reliable feedback.To address the problem of repeated descendants, the algorithm simply re-calculates the effect of each adapta tio n path in the