Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering

1 Introduction

Recently, there has been increased interest in the is­ sue of the utility of knowledge in knowledge-based sys­ tems. Several studies [Markovitch and Scott, 1993; Minton 1988] have defied the traditional belief that in­ creasin~ a problem solver's knowledge is a monotonically beneficial process. Utility of knowledge depends on th_e difference between its cost (e.g. cost of knowledge acqm­ sition, storage, matching) and its benefits (e_.g. incre~ed problem solving efficiency, increased solutiOn q~ahty_). Operational definitions of utility of a knowledg~ 1t~m m the literature (e.g. [Minton, 1988]) _state that 1t 1s ~he difference between the cost of solvmg a problem w1th Katia Sycara The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213, U.S.A. katia@cs.cmu.edu the knowledge item and solving it without it. Machine learning systems can acquire greater amounts of know~­ edge than is possible to be hand-coded for them by the1r developers. Because less intelligence is involved in ~he automated knowledge acquisition by machine learnmg systems, the acquired knowledge may be of low qual­ ity (e.g. it could be incorrect, irrele_vant or ~edundant) . Hence it is very important for machme learmng systems to consider the quality of the knowledge they employ and develop heuristic strategies to eliminate harmful knowledge, i.e. knowledge whose elimination from con­ sideration would improve problem solving performance. [Markovitch and Scott, 1993] has termed such strategies information filters because they filter_ out harmful kno':"l­ edge from being used in problem solvmg. Examples of m­ for~~tion_ filters include discardin~ of least useful board pos1tlons m the Checkers Player lSamuel, 1959], select­ ing only misclassified instances in ID3 . [Quinlan, 1986], and estimating the utility of newly acqmred control rules and deleting those unlikely to be useful in PRODIGY [Minton, 1988]

*Previously at Matsushita Electric Industrial Co. Ltd.

To ascertain the utility of information filtering, it has to be shown that learned unfiltered knowledge is harm­ ful in the sense that its addition to a system's knowl­ edge base deteriorates system performance al~ng some evaluation criterion. In this paper, we expenmentally show non-beneficial effects of unfiltered learned knowl­ edge in a system called CABINS and study the effec­ tiveness of three filtering strategies designed to fix the problem. CABINS is a case-based system that learns control knowledge through user interaction and utilizes it for solution improvement through iterative repair in job shop scheduling, an ill-structured domain [Miyashita and Sycara, 1995] . The information filtering idea can be applied in a CBR system in various ways. One way could be to eliminate cases from the case base ("for­ getting" [Kolodner, 1993]) . Another way would be to prune out parts of the case base from consideration dur­ systems by using some sort of similarity metric. By ad­ justing the similarity metric a larger or smaller number of cases are allowed to pass this filter and be considered during problem solving. Alternatively, instead of adjust­

ing problem solving. Traditionally, this is done in CBR ing the similarity metric, various filteri~g tests could be applied to selectively narrow down retneved knowledge from the cases. A fourth method could be filtering out information retrieved from cases, for example filtering out failure information. Yet a fifth method could be to use retrieved knowledge to extract new indices for sub­ sequent retrieval thus using successive retrievals as fil­ ters. The filtering strategies we have developed involve progressive information filtering using a combination of successive retrievals and tests and utilizing success and failure information stored in cases.

The use of failure information in CBR systems is not new. For example, CHEF [Hammond, 1989] assumes the existence of a model-based simulator for evaluat­ ing a derived plan and detecting failure and uses hand­ crafted domain rules for selecting repair actions. Work by [Kambhampati and Hendler, 1992] aims to speed­ up system performance through learning and case-based reuse of control rules in planning, where a correct satis­ ficing plan is sought and a strong domain model is as­ sumed. The contribution of our work is to experimen­ tally study failure-based information filtering strategies in case-based control knowledge learning for an optimiza­ tion task in a domain without a strong domain model. CABINS was evaluated in the task of schedule optimiza­ tion in the job shop scheduling domain. Our experi­ mental results, presented in section 5.4 show that pro­ gressive filtering is superior to flat filtering in that it enables CABINS to increase both solution quality and search efficiency. In particular, CABINS uses its past failure experiences in progressive filtering to ( 1) validate use of a selected repair action, and (2) interrupt a re­ pair that is unlikely to produce useful results. Given our encouraging experimental results, we believe that our filtering strategies can be used as a domain-independent refinement of k-Nearest Neighborhood retrieval for con­ trol knowledge learning tasks.

2 The Task Domain

Scheduling assigns a set of tasks over time to a set of resources with finite capacity. One of the most diffi­ cult scheduling problem classes is job shop scheduling. Job shop scheduling is a well-known NP-complete prob­ lem [French, 1982]. In job shop scheduling, each task (heretofore called a job or an order) consists of a set of activities to be scheduled according to a partial activity ordering. The dominant constraints in job shop schedul­ ing are: temporal precedence constraints that specify the relative sequencing of activities within a job and resource capacity constraints that restrict the number of activi­ ties that can be assigned to a resource during overlap­ ping time intervals. The activity precedence constraints along with a job's release date and due date restrict the set of acceptable start times for each activity. The capac­ . ity constraints restrict the number of activities that can use a resource at any particular point in time and cre­ ate conflicts among activities that are competing for the use of the same resource at overlapping time intervals. The goal of a scheduling system is to produce sched­ ules that respect temporal relations and resource capac­ ity constraints, and optimize a set of objectives, such as minimize tardiness, maximize resource utilization etc.

The tight interactions between temporal precedence and capacity constraints give rise to many nonlinear effects during search for an optimal schedule. It is in gen­ eral impossible to have a strong domain model that could help estimate the effects of system decisions on optimiza­ tion objectives. The use of heuristics and study of ex­ perimental results is the typically use. d method for job shop schedule optimization lFrench, 1982].

3 CABINS Overview

In order to make the information filtering aspect compre­ hensible, we give here a brief and of necessity incomplete overview of CABINS. For more details on CABINS im­ plementation, operation and other experimental results that describe different CABINS capabilities, the reader is referred to [Miyashita and Sycara, 1995].

CABINS incrementally revises a complete but sub­ optimal schedule to improve its quality. Revision con­ sists in identifying and moving activities in the schedule. To move activities, CABINS uses a number of repair op­ erators, called repair tactics that it possesses. In the current implementation, CABINS has 11 repair tactics (e.g., jumpJeft, which moves an activity as much to the left on the timeline as possible without violating prece­ dence constraints). Because of the tight constraint in­ teractions, a revision in one part of the schedule may cause constraint violations in other parts. It is gener­ ally impossible to predict in advance either the extent of the constraint violations resulting from a repair action, or the nature of the conflicts because of interacting in­ fluences of constraint propagations. Therefore, a repair operator must be selected, applied and its repair out­ come must be evaluated in terms of the resulting effects on scheduling objectives.

Thus, at each decision point, CABINS must make three control decisions: which activity to move, which repair operator to apply and how to evaluate the repair result so as to eventually optimize overall schedule qual­ ity according to scheduling objectives. Each of these de­ cisions is very difficult for the following reasons . A sched­ ule typically contains many jobs, each of which contains many activities. There is no a priori knowledge as to the order of activity moves that will give the best result . Moreover, we have found no distinguishing features of an activity per se that would allow satisfactory match­ ing with previous similar activities. Therefore, CABINS orders the jobs randomly and within each job repairs ac­ tivities from the first to the last [Miyashita and Sycara, 1995]. Since activities get moved during repair, an ac­ tivity may be repaired (moved) multiple times during a problem solving session. Selecting a repair operator to apply is also very difficult . Unlike traditional planning operators, the repair operators in CABINS have no well defined preconditions or postconditions. Hence learning operator selection is fraught with all the difficulties of learning control rules in traditional planning plus the additional complexity of not knowing the operator pre­ and post-conditions. CBR enables CABINS to learn a control model of repair operator selection. Finally, eval­ uation of the result of applying a repair operator is also very difficult, since the optimization objectives are often context and user dependent and reflect state-dependent tradeoffs that are difficult to describe in a simple manner. CABINS learns through CBR what combinations of effects of application of a particular repair action con­ stitutes an acceptable or unacceptable repair outcome.

In each repair iteration, CABINS focuses on one ac­ tivity at a time, the focaLactivity, and tries to repair it. A case in CABINS describes the application of a par­ ticular modification to a focaLactivity. A case in CAB­ INS comprises 3 types of the features: global features, local features and repair history. The global features reflect an abstract characterization of potential repair flexibility for the whole schedule. Associated with the focaLactivity are local features that we have identified and which potentially are predictive of the effectiveness of applying a particular repair tactic. Because of the ill­ structuredness of job shop scheduling, local and global features are heuristic approximations that reflect prob­ lem space characteristics.

The repair history records the sequence of applica­ tions of successive repair actions, the repair outcome and the effects. Repair effect values describe the impact of the application of a repair action on scheduling objec­ tives. A repair outcome is the evaluation assigned to the set of effects of a repair action and takes values in the set ['acceptable', 'unacceptable']. Typically the out­ come reflects tradeoffs among different objectives. An outcome is 'acceptable' (i.e. a success) if the user ac­ cepts the tradeoffs involved in the set of effects for the current application of a repair action. Otherwise, it is 'unacceptable', a failure. The effect salience is assigned by the user when the outcome is 'unacceptable', and it indicates the significance of the effect to the repair out­ come. The user's judgment as to balancing favorable and unfavorable effects related to a particular objective constitute the explanations of the repair outcome.

Once enough cases have been gathered through user interactive schedule repair, CABINS repairs sub-optimal schedules without further user interaction. CABINS re­ pairs the schedules by (1) sorting jobs in a random or­ der, (2) focusing on a focaLactivity to be repaired in each repair cycle, (3) invoking .CBR with global and lo­ cal features as indices to decide the most appropriate repair tactic to be used for each focaLactivity, ( 4) in­ voking CBR using the repair effect features (type, value and salience) as indices to evaluate the repair result, and (5) when the repair result is deemed a failure, deciding whether to give up or which repair tactic to use next. The similarity metric that CABINS uses is a k-Nearest Neighborhood method.

4 Experimental Design

To test whether learned unfiltered knowledge is bene­ ficial or not, we used controlled experimentation on a benchmark suite of job shop scheduling problems. These problems are variations of the problems we have used to test other aspects of CABINS [Miyashita and Sycara, 1995]. The benchmark problems have the following structure: each problem has 10 orders of 5 activities each. Six groups of 10 problems each were randomly gen­ erated by considering three different values of the range parameter, and two values of the bottleneck configura­ tion.

A cross-validation evaluation method was used. Each problem set of each problem class was divided into two groups with the same size (i.e., each group contains 30 problems). Currently we have collected about 12000 cases for each group of training sets. These cases were then used for case-based repair of the test problems in the other group. The above process was repeated by interchanging the training sets.

In the experiments reported here, we used the sum of tardiness and inventory costs as an explicit cost function to reflect optimization criteria 1 . We built a greedy hill­ climb rule-based optimizer (RBR) that goes through a trial-and-error repair process to optimize a schedule by minimizing the cost function. RBR was implemented to try what seems a best repair action first based on heuris­ tic evaluation of its possible repair effects and go through all the available repair actions before giving up further repair. For each repair, the repair effects were calcu­ lated and, on this basis, since RBR had a pre-defined cost function, it could evaluate repair results precisely. RBR was used as the experimental baseline where no learning of control knowledge takes place. RBR was also used as a case base builder for CABINS. Each time RBR repaired an activity, the repair decisions made by RBR such as repair action selection and repair result evalua­ tion were recorded in a case. In this set of experiments, RBR was used to create a case base with 12000 cases. Naturally, a cost function, though known to RBR, is not known to CABINS and is only implicitly and indirectly reflected in an extensional way in the case base.

In our experiments, the number of repair tactic appli­ cations was used as a metric of search efficiency for a number of reasons: (1) tactic application involves con­ straint propagation and calculation of repair effects, thus being the most computationally expensive process in schedule repair, (2) the number of tactic applications is a machine independent measure, as opposed to for exam­ ple, CPU time, and (3) the number of tactic applications directly reflects the number of search states examined. Reduction of the number of tactic applications improves the efficiency of iterative schedule revision process.

Table 1: Performance in unfiltered learning of control knowledge

I

In Table 1 "Unfiltered" indicates the performance of CABINS, which retrieves similar successful repair expe­ riences and applies the repair tactic that was dominant in the most similar success cases. If the tactic is evalu­ ated as unacceptable, in the Unfiltered condition, CAB­ INS automatically tries another repair tactic used in the next most similar cases.

Table 1 shows that. unfiltered learned knowledge is in­ deed harmful in terms of problem solving efficiency although it produces solutions of similar quality as com­ pared to the base condition of RBR. This result means that the cost of utilizing the learned knowledge is ex­ cessive. We think that this is due to the Unfiltered repair's greediness and stubbornness. Greediness makes Unfiltered repair applies the tactic from the most similar success case no matter how small the similarity. Stub­ bornness makes the Unfiltered repair insists on trying to repair the current focal...a.ctivity without giving up if the likelihood of a successful repair seems small.

1 Such a cost function is widely accepted in practical scheduling environments.

5 Information Filtering

To decrease the number of tactic applications without sacrificing solution quality, filtering strategies must be found that retrieve more relevant tactics and better esti­ mate the likelihood of successful outcome before applica­ tion of a selected tactic. We hypothesized that incorpo­ rating failure information in filters would alleviate non­ beneficial effects of potentially harmful learned knowl­ edge by lowering the cost of excessive number of tac­ tic applications. So we focused on designing filters that would enable CABINS to ( 1) learn to avoid repeating similar previous failures, and (2) learn to avoid wasting lots of efforts in trying to solve too difficult problems.

To analyze the correctness of the above hypothesis, the following three filtering strategies were experimentally implemented in CABINS: validated filtering, interruptive filtering and hybrid filtering. These filtering methods were tested using the same problems, cost function and case bases used for the experiment in Section 4.

5.1 Validated Filtering

The validated filtering method allows CABINS to apply a repair action only after it has been validated as possibly effective for repairing the current problem. Validation techniques have been used in case-based reasoning sys­ tems (e.g. [Hammond, 1989; Simoudis and Miller, 1991]). For example, in CASCADE and COAST [Simoudis and Miller, 1991], a validation process extracts from the case base only those cases that appear to be closely relevant to the current problem using a validation model of the do­ main which consists of knowledge of interrelations among diagnostic tests and knowledge about individual diagnos­ tic tests and their expected values in previous cases that would match a current problem.

The above systems utilized established models based on deep understanding of their domain for validation. Domain models act as filters that allow only validated information to be used in problem solving. However, in ill-structured domains like job shop scheduling, nei­ ther causal model nor validation model of the domain are readily available. In the job shop scheduling prob­ lem, non-linearity of objectives and tight interactions of constraints make it hard to predict the effects of a local optimization decision on global optimality, thus making the analysis of the domain structure required to build a causal model and a validation model extremely diffi­ cult.Therefore, CABINS must validate the potential ef­ fectiveness of a retrieved repair tactic without such mod­ els. To compensate for lack of these models, CABINS

utilizes failure information as a filter through which only validated repair tactics can pass.

Fig. 1 shows the schematic diagram of the validation filtering process in CABINS. First, using global and lo­ cal features as indices, candidate cases are retrieved from success cases that store successful repair episodes in a case base. Then, another CBR retrieval is done from failure cases using as additional indices the repair tactics indicated in the already retrieved successful cases. This retrieval results in a set of rejecting cases. The candidate repair tactics found in rejecting cases with low credibil­ ity (i.e. low similarity to the current problem), are then allowed to be used since they have been validated to be possibly effective (i.e. not likely to fail).

The repair tactic selection procedure using validated filtering is as follows:

1. Select k 2 nearest cases of the current problem that succeeded in repair using global and local case fea­ tures as indices (these are labelled "candidate cases" in Fig. 1).
2. Among the candidate cases, obtain the sum of case similarity 3 to the current problem for each of the repair tactics which was successfully appiled in the cases.
3. Sort the repair tactics of step 2 in decreasing order of the corresponding value of the similarity sums.
4. Until no repair tactic remains in the sorted queue, do the followings:
5. (a) Pick up the next repair tactic in the sorted re­ pair tactics queue.
6. (b) Using as indices, global and local features and the picked-up repair tactic, select k nearest cases of the current problem, in which an appli­ cation of the picked-up tactic resulted in failure ("rejecting cases" in Fig. 1).
7. (c) Sum up the similarity of the selected k "reject­ ing cases".
8. (d) If the sum is smaller than a pre-defined thresh­ old value, return the tactic as a validated tactic.
9. Return "give.up" as a repair tactic, i.e. give up trying to repair the current activity.

2 In our experiments, we heuristically decided k as 5.

3 For details of the similarity calculation, see [Sycara and Miyashita, 1994].

The validated filtering procedure allows only validated tactics to be considered for repair application. CABINS judges the likelihood that a selected repair tactic will fail in the current problem from the past failure experiences of the same tactic. If CABINS judges that a tactic is not likely to fail in the current problem (i .e. the sum of similarity of rejecting cases associated with the tactic is less than some threshold), CABINS considers the repair tactic as validated.

Since in difficult problems such as schedule repair, fail­ ures usually outnumber successes, if the value of the threshold (in step 4(d) of the above procedure) is defined as moderately high, overly pessimistic results could be produced (i.e. CABINS seldom validates a tactic) . To avoid this, a threshold value was set as 4.99. Since the value of k was 5 in the experiments, validation rejection was less likely to occur.

5.2 Interruptive Filtering

In validated filtering, CABINS gives up repairing a par­ ticular activity either when there are no validated tac­ tics, or when all validated tactics have resulted in failure (i.e. an unacceptable repair outcome). The interruptive filtering method allows CABINS to shift its repair atten­ tion to another activity when repair of the current ac­ tivity is estimated too difficult . CABINS gives up a fur­ ther repair when it determines that it would be a waste of time. If there are enough failure cases in the past similar situations to the current one, CABINS gives up repairing the current activity, and switches its attention to another.

Fig. 2 shows the schematic diagram of the interrup­ tive filtering process in CABINS. In the process, cases that match the current problem are retrieved from failure cases (the retrieved cases are called interrupting cases in Fig. 2). If the interrupting cases have high credibility (i.e. high similarity to the current problem), the pro­ cess of retrieving candidate cases to use in repairing the current focaLactivity is not allowed to proceed and the problem solver seeks another activity to repair.

The repair tactic selection procedure using interrup­ tive filtering in CABINS is as follows:

1. Using global and local features as indices, retrieve k nearest cases of the current problem from failure .cases (i .e., " interrupting cases" in Fig. 2) .
2. Sum up the similarity ofthe selected k " interrupting cases" .
3. If the sum exceeds a pre-defined threshold value, re­ turn "give.up" as a repair tactic, i.e. give up repair­ ing the current focaLactivity.

Otherwise, select k nearest cases of the current problem using global and local features as indices from successful cases (these are the "candidate cases" in Fig. 2 and they are the same as the "can­ didate cases" in Fig. 1 for a given focaLactivity).

1. Among the candidate cases, obtain the sum of case similarity to the current problem for each of the repair tactics which was successfully appiled in the cases.
2. Sort the repair tactics of the previous step in de­ creasing order of the corresponding value of the sim­ ilarity sums.
3. Return the first repair tactic in the sorted repai r tactic queue as the selected repair tactic.

In the above procedure, CABINS judges the likelihood that a current problem cannot be repaired from failure experiences in past similar problems. If CABINS judges that the current problem is not likely to be repaired (i.e. the number of failures of similar past problems is high enough), CABINS gives up repairing the current prob­ lem. If CABINS decides that the current problem is not too difficult, it proceeds to repair it selecting repair tactics from success cases without tactic validation. As was discussed in the validated filtering method, in dif­ ficult problems such as schedule repair, failures usually outnumber successes and if the value of the threshold (in step 3 of the above procedure) is defined moderately high, overly pessimistic results could be produced (i .e. CABINS suggests giving up too often) . To avoid this, a value of the threshold was set as 4.99.

The ways failure cases are used in validated and inter­ ruptive filtering seem to be independent and compatible with each other. Each filtering strategy filters different knowledge at different stages of repair action retrieval and evaluation. Hence, the two strategies can be com­ bined in a serial fashion to form a hybrid filtering strat­ egy.

5.3 Hybrid Filtering

In hybrid filtering, CABINS first decides whether to give up repairing the current focaLactivity using "interrupt­ ing cases" (as in Interruptive Filtering) . If it is decided that repair of the current focaLactivity should proceed, CABINS uses Validated filtering to validate the selected tactics that will be tried in the repair.

The repair tactic selection procedure using hybrid fil­ tering in CABINS is as follows :

1. Using global and local features as indices, retrieve k nearest cases of the current problem from failure cases (i.e. "interrupting cases" in Fig. 2).
2. Sum up the similarity of the selected k "interrupting cases".
3. If the sum exceeds a pre-defined threshold value, re­ turn "give.up" as a repair tactic, i.e. give up repair­ ing the current focaLactivity.

Otherwise, use the validated filtering procedure (Fig. 1).

5.4 Experimental Results

Table 2 shows performance comparison among the un­ filtered condition, RBR, and the three filtering strate­ gies. The results in the table show that CABINS with validated filtering improved its efficiency about 58% as compared with the unfiltered condition without unduly sacrificing schedule quality. CABINS with validated fil­ tering was even faster than RBR. Table 2 also shows that CABINS with interruptive filtering improved its ef­ ficiency about 46% as compared with unfiltered condi­ tion while maintaining high schedule quality.

From the results in the table, it is also shown that CABINS with the hybrid repair improved its efficiency about 65% compared with the unfiltered condition with­ out reducing schedule quality. The results also suggest that CABINS with hybrid filtering produced high qual­ ity schedules more efficiently than RBR.

To analyze the effects of combining two repair meth­ ods in the hybrid repair, the number of tactic application using validated filtering and using interruptive filtering were compared with that of hybrid filtering. By hypoth­ esis testing, it was found that CABINS with hybrid filter­ ing should be more efficient than CABINS with interrup­ tive repair or CABINS with validated repair. Therefore, by combining the validated repair and the interruptive repair, a synergistic effect emerges in improving the effi­ ciency of the repair process.

Although experimental results show that the three in­ formation filtering strategies were effective in reducing the number of tactic applications in CABINS, it could be argued that knowledge filtering will also consume~ com­ putational resources. CPU time is a generally accepted metric of overall problem solving cost. The averaged CPU time results in Table 2 show a pattern similar to the one observed for number of tactic applications (i.e., validated repair, interruptive repair and hybrid repair consume less CPU time than unfiltered repair) m our experiments. These results are encouraging.

6 Conclusions

We discussed the phenomenon of non-beneficial effects, in terms of degradation of the performance of a problem solver, of learned knowledge. We showed the existence of this phenomenon in the context of case-based learning of control knowledge. This knowledge is used to to guide revision-based optimization in an ill-structured domain, job shop scheduling. To alleviate the non-beneficial ef­ fects of learned knowledge, we designed and experimen­ tally demonstrated the effectiveness of three knowledge filtering strategies. These strategies, validated filtering, interruptive filtering and hybrid filtering employ a com­ bination of successive case retrievals and in particular exploit failure information found in cases in order to (1) validate learned control actions, or (2) avoid wasting ef­ fort in attempting repairs where the likelihood of success is low. Our experimental results show that the knowl­ edge filtering strategies were effective in increasing the efficiency of problem solving without compromising so­ lution quality. We are currently exploring automated adaptation of the filtering control parameters (value of k and of the threshold).