Remembering to Add: Competence-preserving Case-Addition Policies for Case Base Maintenance

1 Introduction

Case-base maintenance refers to the task of adding, deleting and updating cases, indexes and other knowl­ edge in a case base in order to guarantee the ongoing performance of a CBR system. Case-base maintenance is particularly important when a case based reasoning system becomes a critical problem solving system for an organization. This is because for any such organization, the knowledge may change over time and the need for different knowledge structures for problem solving may vary. The case-base size will increase with time, creating significant barrier to reasoning efficiency and the user 's ability to understand the results.

In response to these problems, there has been a signif­ icant increase in case-base maintenance research. One branch of research has focused on the ongoing main­ tenance of case-base indexes through training and case base usage [Cunningham et al., 1997; Fox and Leake, 1995; Aha and Breslow, 1997; Zhang and Yang, 1998]. Another branch of research have focused on increasing the overall competence of the case base through case deletion [Smyth and Keane , 1995; Markovich and Scott , 1988; Domingos , 1995; Aha et a/. , 1991; Smyth and Keane, 1995; Racine and Yang, 1997] in a way simi­ lar to utility-based control-rule deletion policies [Minton, 1990]. Excellent surveys of this field can be found in [Leake and Wilson, 1998] and [Watson , 1997].

This recent surge of interest in case-base maintenance is highlighted by Smyth and Keane seminal work on competence-preserving case-deletion policy [Smyth and Keane, 1995]. In this work , the cases in a case base are classified into a type hierarchy based on their cover­ age potential and adaptation power. The deletion policy then selectively deletes cases from a case base guided by the classification of the cases until a limit on the case base size is reached. The algorithm was empiri­ cally shown to preserve the competency of a CBR system and to outperform a number of previous deletion based strategies.

In this paper, we present a detailed analysis of Smyth and Keane's deletion based policy and show that this policy does not always guarantee the competence pre­ serving property. In particular, we show that using this policy can potentially result in a case base with signifi­ cantly decreased performance. In response, we develop a different case-base maintenance policy that is based on case addition rather than deletion. By this policy, cases in an original case base are repeatedly selected and added to an empty case base until a certain size limit is reached, producing an updated case base which high cov­ erage guarantee. The addition based policy will allow a more global view of the case base as a result of the main­ tenance operations. We show that both the Smyth and Keane's deletion-based policies and our addition-based policies have the same time complexity. The advantage of the addition-based policy is that we can place a lower bound on the competence of the resulting case base while the deletion-based policy cannot; we demonstrate that the coverage of the computed case base cannot be worse than the optimal case base in coverage by a fixed lower bound, and often is much closer to the optimal coverage.

Our result highlights the importance of finding the right similarity metrics in order to guarantee the best case-base coverage. We contend that it is important to tie the definition of similarity-based metrics to adap­ tation costs . Based on this observation, we demon­ strate through case-based planning how to construct high-quality similarity metrics that lead to highly com­ petent case bases, and discuss various implications of our result in practical implementation of case-base main­ tenance systems. Finally, we confirm our competence­ preserving claims through an experiment in case based planning.

2 Case-Base Maintenance and Case-deletion Policies

2.1 Related Work

Recently, there has been intense interest in case based reasoning research community on the problem of case­ base maintenance. Leake and Wilson gave an in-depth summary and analysis of this field [Leake and Wilson, 1998). For our purpose, the problem of case-base mainte­ nance is divided into two broad categories: maintaining the case base indexes and maintaining the case base con­ tents. In case-base index maintenance, [Cunningham et al., 1997) presents an introspective learning approach to learn adjusted case base indexes by monitoring the run­ time processes of a case based reasoner. An extended approach is developed in [Zhang and Yang, 1998), where a layered architecture is adopted for representing case base indexes and a neural network algorithm is adapted for maintaining the feature weights. Fox and Leake [Fox and Leake, 1995) and Aha and Breslow [Aha and Bres­ low, 1997) consider case-base index-revision policies that improve the performance of a case base in response to events such as plan failures.

Researchers in case-base content maintenance are mainly concerned with the issue optimization. Due to the large size of some case bases, it is necessary to delete cases as time goes by, and when retrieval become increas­ ingly expensive [Smyth and Keane, 1995) . This issue is called the swamping problem. The main strategy is that of deciding which cases to delete based on an adapta­ tion structure. These strategies include one for random deletion as advocated by [Markovich and Scott, 1988), and more sophisticated deletion based on the frequency with which each case is retrieved and deleted if they are not frequently accessed [Minton, 1990) . The prob­ lem with both of these approaches is that "important" cases can be deleted by mistake. Various approaches have been designed to address this problem. Domin­ gos [Domingos, 1995) and Aha, Kibler and Albert [Aha et al., 199 1) consider instance-based learning approaches for generalizing to reduce the size of a case base with­ out decreasing its problem-solving power. Smyth and Keane [Smyth and Keane, 1995) consider a competence­ preserving approach to case deletion. Watson lWatson, 1997) presents methodologies for a human designer of a case base to consider for case-base maintenance. Racine and Yang [Racine and Yang, 1996) consider the problem of removing redundancy and inconsistency from a large semi-structured case base in order to improve the case base performance.

2.2 Coverage and Neighborhood Functions

We define a case as a problem-solution pair. That is, each element C of a case base is a pair C = (x , s), where s E S is a corresponding solution to a problem descrip­ tion x. For each problem x1 in a case base X1 , x1 can represent the case (x1, 1r(xl)).

Hence we also call x1 a case. Let N(xl) be the set of cases x2 whose solution 1r(x2) is close to 1r(xl). More formally,

where L is a constant limit on the cost of adapting a so­ lution. Essentially, N defines a coverage of x1 . We call N(xl) the coverage or neighborhood of x1 . Later in the paper (Section 6), we define a distance metric d( x1 , x2) for case based planning using the number of adaptation steps to apply to the solution of x1 in order to solve x2 . For now, we assume that the neighborhood function is given as done by Smyth and Keane [Smyth and Keane, 1995), and consider how to use this information to com­ pute a near-optimal case base X1 from a given case base X.

Based on the above notion, the coverage of a case is determined by a similarity metric and adaptation costs. We can consider the coverage of a case as the neighbor­ hood of the case within certain adaptation limits. Hence, we consider the notion of a problem neighborhood and coverage interchangeable. Similarity metrics are used to measure the similarities between cases. They are usu­ ally numerical , but a good similarity metric is not easy to find in many application domains. We therefore in­ troduce the notion of a neighborhood which is a more intuitive notion.

2.3 Analyzing Case Deletion Policy

When the size of a case base gets large, there is a need to select a subset of the cases to keep. To address this problem, Smyth and Keane [Smyth and Keane, 1995) suggest a case deletion based approach. The premise of this approach is that each case in the case base should be classified according to its competence. These classifica­ tions are made according to two key concepts: coverage and reachability. Coverage refers to the set of problems that each case can solve. Reachability is the set of cases that can be used to provide solutions for a problem.

Cases that represent unique ways to answer a specific query are pivotal cases. Auxiliary cases are those which are completely subsumed by other cases in the base. In between these two extremes are the spanning cases which link together areas covered by other cases, and support cases which exist in groups to support an idea. The dele­ tion algorithm deletes cases in the order of their classi­ fications : auxiliary, support, spanning and then pivotal cases [Smyth and Keane, 1995].

Similarly, the definitions for spanning and support cases also rely on the concepts of coverage and reach­ ability. In their evaluation of their algorithm, which consisted of 50 cases, Smyth and Keane restrict the size of the case base and the size of the problem space and manually identify the category in which each case falls.

The deletion based policy is motivated by the need to delete cases in order to maintain the competency of a case base at a reasonable size. However , no mention is made about why auxiliary cases should be deleted first , and how the quality of the resulting case base is ensured after the update is done. Pivotal cases may be "impor­ tant" or they may simply contain anomalies that distin­ guish them from the rest of the case base. But deleting the rest of the case base first only offers an intuitive solu­ tion to the case-base maintenance problem; there was no guarantee on the level of true competence preservation.

Smyth and Keane's terminologies can be illustrated graphically as in Figure 1. In this figure, an arrow from a node x to a node y means that the case y is in the neighborhood of the case x. Therefore, in Fig­ ure 1, N(x) = {x,y}, N(y) = {y,a,b, c}, N(a) ={a}, N(b) = {b} and N(c) = {c}. According to Smyth and Keane's classification scheme, x is pivotal , y is spanning and a, b, care auxiliary.

From these definitions, it is easy to see that piv­ otal problems are the most unique, spanning prob­ lems are less unique, but auxiliary problems are not unique . Smyth and Keane's footprint deletion (FD) and footprint-utility deletion (FUD) policy delete auxiliary problems first, then support problems, then spanning problems, finally pivotal problems. This approach is bet­ ter than a random deletion policy for preserving compe­ tence. The competence of a case base built by Smyth and Keane's footprint deletion (FD) or footprint-utility deletion (FUD) policy is not guaranteed to be preserved.

Theorem 1 FD and FUD can lose almost all the com­ petence in the worst case.

Proof:

To prove this theorem, we only need to give an exam­ ple. Suppose that in some domain , we have the graph structure as shown in Figure 1.

In this figure, each node stands for a problem (or case). We see that the problem x is pivotal, y is spanning and a, b, c are auxiliary. Suppose that we want to build a case base with only one element; that is, we restrict our case base to be of size one. By the footprint deletion or footprint-utility deletion policies, cases a , b, c should be deleted first, followed by y. As a result, only problem x is left in the case base. The coverage is ~ of the origi­ nal competence. If we increase the number of auxiliary cases (such as a, b, c in the figure) to k, then the cover­ age is k!2 of the original competence. The percentage approaches to zero as k --+ oo. Therefore, the quality of the case base is arbitrarily bad. This completes the proof. D

3 Case-addition Ba:;;ed Policy

Suppose that the neighborhoods of all cases in a case base are obtained. We say a case is good if its neigh­ borhood is large. To select good cases, the distribution of the cases or the frequency of cases occurring should also be considered. For instance, in an example travel domain (Section 6.2), suppose that more people prefer a travel plan between City 1 and City 4, then we should put this plan in a case base in order to minimize the cost of searching for such plans. Taking this into account, we define case coverage as follows:

Given a domain, we have a case space X and a solu­ tion spaceY. Let x EX be a case. Denote N(x) the neighborhood of x and N(Xl) = UxEX 1 N(x) . N(Xl) contains cases which are close to some other cases in X1 . Suppose that P is a a frequency function of the cases (be­ tween 0 and 100%) ; equivalently there is a distribution of cases. Then the case base coverage of X1 is defined as

Since X 1 is a subset of X, the case coverage is a real number between 0 and 1. If the function P does not exist, we assume that P = 1 - the constant function.

The benefit of a case x with respect to a set W of cases is defined as Bft(x) = l:yEN(x)-N(W) P(y) , where N(W) = UwEwN(w) . The benefit of a case set {x1, x2, · · ·, xk} is defined as "2:yEU~= 1 N(x; )-N(W) P(y).

Suppose we want to build the case base X1 with at most k cases based on a set Z of cases. We formulate this optimization problem as follows

(*) Choose cases { x 1 , x2, · · · , x k} from case set Z to maximize the benefit of {x1 , x2 , · · ·, xk} (W = 0).

This optimization problem is NP-compete. One can easily prove this by a reduction from Set-Covering [Garey and Johnson , 1979) . Thus, we look for heuristics to find approximate solutions. Consider the following case-addition algorithm based on selecting cases from Z and adding them to the new case base:

Case-Addition Algorithm:

1. Determine the neighborhood N ( x) for every case X E Z.
2. Set X1 = 0.
3. Select a case from Z- X1 with the maximal benefit with respect to N(Xl) and add it to X1 .
4. Repeat step 3 until N(Z)- N(X1 ) is empty or X1 has k elements.

Remark. Here we consider the case coverage as the benefit. In fact, the benefit can be defined on other notions as long as it captures the concept of usefulness.

The Case-addition Algorithm is a greedy algorithm. Therefore it may not give the best choice of X1 with respect to the case coverage. However, we can prove that its case coverage is at least 63% of the optimal case base, for any fixed case-base size k .

Theorem 2 The case addition algorithm produces a case base X 1 such that the coverage of X 1 is no less than 63% of the coverage of an optimal case base.

The proof for this theorem is derived from that of a greedy algorithm for set covering. Due to space lim­ itations, we only provide an intuitive sketch for the proof here. Suppose that N(Z) - N(Xl) :f. 0, then X 1 = { x 1 , x 2, · · · , x k} has k elements and labeled by the order of selection. Let a; be the benefit of x;, 1 :::; i :::; k. Suppose that {Y1, Y2 , · · ·, Yk} is an optimal choice for X 1· Let b;, 1 :::; i :::; k , be the benefit of y; under the index order. Note that a1 ~ a2 , · · · , ~ ak. We can then relate a; with bj and derive the following inequality: the ration of the coverage of { x 1 , x2, · · · , x k} and the optimal case base coverage for k cases is ·

Our result is motivated by a similar result in [Hari­ narayan et al., 1996) for constructing a data cube used in building a . data warehouse. The main difference is that in CBR case adaptation is our main concern whereas in data warehousing the utility of a data view is of great importance.

Analyses of both Smyth and Keane's case-deletion al­ gorithm and our case-addition algorithms reveal that they require the same time complexity (O(n 2 )). This is because both algorithms are dominated by computing the coverage of cases, hence their costs should be about the same. When n is large, computing the competence categories and the coverage of cases becomes expensive. However , the key point is it is only computed once as a start-up cost . We have developed a practical incremen­ tal case-addition algorithm which will will present in an extension of the paper .

4 Relating Case Base Size with Coverage

We have so far assumed that the case base size k is given. Having a different k will result in a case base with a dif­ ferent coverage value. How should a case base maintainer choose an appropriate size for a case base?

In this section we will estimate how a case base size de­ termines its coverage. In our notation, we would like to estimate the ratio between IX1I and IN(Xl)l . Suppose that x 1 , x 2 , · · · , Xn are cases selected by case-addition al­ gorithm with the benefits of a1, a2, ···,an. Then

Hence, the ratio IX1I/IN(Xl)l is between a 1 , and a 1 ,.. However, this estimation is rather rough.

Our theorem below points out the precise relationship between case-base sizes and case-base coverage:

Theorem 3 Let M be the size of the original case base before applying the case-addition algorithm for mainte­ nance. Let k be the size of the case base after main­ tenance. Suppose that all cases have equal probability of appearance; that is, the frequency of all cases are the same. Suppose also that when constructing the re­ sult case base the benefits of new cases decrease linearly. Then we have

where R = k/M.

Again due to space limitations we omit the proof. In­ stead, we plot the coverage curve as shown in Figure 2.

From the graph, we see that over 15% of cases can at­ tain about 50% coverage while 50% of cases can attain about 85% coverage. In general, things are better. We have used the linear approximation to draw the coverage graph. In general, the difference (ak+l - ak) decreases quickly as k increases. Hence, we can have a better model via replacing I:;=0(a1-ai) with I:;=0(a1-ai 1 /h) , where h is an integer 2 1. The resulting graph of cov­ erage is similar, but the desired coverage can be reached much sooner.

5 Experiments with the Case-Addition Algorithms

To fully validate our case-addition algorithm, we need to perform empirical tests in various domains . In the remaining of this paper, we present one such experiment in a travel planning domain. In this domain, a problem x can be considered a pair of states: x = ( s; , s 9 ), where s; is an initial state and s 9 a goal state. A case is a pair (x,p) , where xis a problem definition and p a plan. We consider a plan as a sequence of actions taking one from the initial state to the goal state. There are many ways to define planning algorithms for finding a plan [Kambhampati et al., 1995; Yang, 1997]; here we focus on how to reuse the previous plans.

In planning various similarity metrics have been pro­ posed for determining the distances between two plans [Hammond, 1990; Hanks and Weld, 1995]. For ex­ ample, the foot-printed similarity metric [Veloso, 1992; 1994] compares relevant features of a case with features of a new problem where a relevant feature is considered relevant to a goal and a solution if the feature contributes to achieving the goal in the solution. rao:cbp97 presents a mechanism for adding plans to a plan library in or­ der to limit the size of the case base. The adaptation­ guided metric [Kinley et al., 1995] exploits the adapta­ tion knowledge of a case base.

In our example travel domain, as shown in Figure 3, there is a map in which an agent will travel between two cities. The agent would like to remember a few useful paths so that a case base can be constructed. In order to do this, it is assumed that a neighborhood function is defined based on adaptation as follows: Let a case x be a problem together with a solution soln , where x = ( s;, s 9 ) and soln = s1 --+ s2 --+ · · · --+ sk. Here s1 = s; and Sk = s 9 . Then the neighborhood N ( x) of problem x is defined as the neighborhood of the solution. More precisely,

where the neighborhood of a state N(sj) is defined as the set of states (that is, cities) that are one step from Sj. We call this neighborhood function the "state-based" similarity measurement for planning.

In our experiment, an input problem is defined as any pair of cities, and the solution, which is a case, is a path going from an initial city to a destination city.

The state can be moved horizontally or along the main diagonal lines. The number of states = 100. The prob­ lem space has 100 2 = 10000 problems. Randomly se­ lect 80 problems from the problem space and solve these problems from scratch by a forward chaining and breath­ first planner. By computing the neighbors of these prob­ lems, we see that the union of all these neighbors covers 3138 problems. Applying the case-addition algorithm, we get the result which is shown in Figure 4.

6 Conclusions and Discussion

We conclude that it is important to tie similarity met­ rics with adaptation costs. Based on this concept , we have given an approximation algorithm for building a case base with near-optimal property. We attribute this property to the fact that we use a case-addition rather than a case-deletion policy as done by Smyth and Keane. In the future, we will study how to maintain a case base in order to increase the quality of cases in addition to increasing the case bsae coverage.

Acknowledgment

The authors are supported by grants from: Natural Sciences and Engineering Research Council of Canada (NSERC) , an Ebco/Epic NSERC Industrial Chair Fund, BC Advanced Systems Inst itute and Canadian Cable Labs Fund. We wish to thank IJCAI reviewers for their in-depth suggestions .