Dynamic Refinement of Feature Weights Using Quantitative Introspective Learning

1 Introduction

Case-based reasoning (CBR) is a problem-solving strat­ egy which uses stored previous cases to solve current problems [Kolodner, 1993]. It has enjoyed tremen­ dous success for solving problems related to knowledge reuse [Leake and Ram, 1993]. Usually in a case base a case's index is a set of important descriptors of the case. It can be used to distinguish a case from others. In many implementations, these descriptors are repre­ sented as feature-value pairs and usually a feature is as­ sociated with an importance value called f eature weight to indicate how important it is in the case retrieval pro­ cess. When a new problem is presented, its index will be extracted and used to trigger a search in the case base. The cases with the most similar indices will be retrieved for further consideration [Kolodner, 1993] .

The performance of a CBR system depends on how to use appropriate features to index cases, and how to ob­ tain an accurate measurement of the similarity between cases in the case retrieval process. Therefore the feature weights play an important role in determining the suc­ cess of CBR applications. How to choose and maintain an appropriate set of feature weights in a case base is a non-trivial problem in CBR research. In addition, the relative importance of the cases is changing with time , partly due to the uneven and changing distribution of the inherent problem space, also partly due to the changing interests of its users. How to evolve a case base con­ tinuously in an automated manner is also becoming an urgent task of the knowledge base industry.

One approach to tackling this problem is to use in­ trospective learning, which has a representation of its own process in order to detect deviations that show when the learning is needed as well as what the learning needs [Leake et a/., 1995; Ram and Cox, 1993]. In the past, various introspective learning methods have been employed in feature weighting in CBR systems [Fox and Leake, 1995; Leake eta/., 1995; Wettschereck eta/., 1997; Bonzano et a/., 1997] . A main theme is to learn through qualitative introspective learning, whereby the feature weights are adjusted based on a rough estimate of the direction for a change: if the weights are too high, then adjust them so that they become lower, and vice versa. But how much has to be changed quantitatively is not sufficiently determined. In this work, we extend qual­ itative introspective learning to quantitative introspec­ tive learning within CBR. With the quantitative learn­ ing methods, we can adjust the weights not only in the right direction, but also in the right amount. We claim that such an extension provides a sound and promising continual weight introspective learning method in CBR.

This paper is organized as follows . In Section 2, we introduce some related work on the application of intro­ spective learning to feature weighting. Section 3 presents a novel quantitative introspective learning model inte­ grated into case-based reasoning. In Section 4 we demon­ strate the experimental results for evaluating the performance of our integrated model. And also there we cross­ validate our work with others'. Section 5 concludes our discussion, where we will also explore our future work.

2 Qualitative Introspective Learning Methods

Leake et al. [Leake and Ram, 1993] summarize in a sym­ posium report the goal-driven learning process from var­ ious aspects. They indicate that one of the three key properties of a goal-driven learner is its introspectiveness, an ability to notice the gaps in its knowledge and to rea­ son about the information needed to fill in those gaps. They also pinpoint that introspective learning acquires problem-solving knowledge by monitoring its run-time performance, seeking chances in this process to learn by itself.

In [Fox and Leake, 1995], Fox et al. describe their ex­ periences with introspective learning in CBR. The ROB­ BIE system described is an application of an introspec­ tive model to the task of refining indexes used to retrieve cases. Its goal is to improve reasoning process when en­ countering failures in its reasoning. The introspective learning component in the system monitors its reasoning process by comparing it with a declarative model which is used to describe the system's ideal reasoning process. Once a failure is found, the model is used to create an explanation of the failure in terms of other failed asser­ tions, and to suggest a repair. The authors claim that even under knowledge-poor initial conditions, the intro­ spective learning of new feature indexes improves the success rate of the system. But they still indicate that there exists a problem with the ordering of the presenta­ tion of training cases to the system due to the inherent shortcoming of their learning mechanism.

As a variation of a model that is introduced in [Munoz­ Avilz and Huellen, 1996], Bonzano et al. [Bonzano et al., 1997] also propose introspective learning as an t;Lpproach to feature weighting in CBR, demonstrating thetr system which combines introspective learning with CBR. They first pose the problem with their experience in construct­ ing a CBR system f?r. Ai~ Traffic Control.. The p~oblem encountered is that 1t 1s dtfficult to determme the Impor­ tant features and adjust their relative importance. The situation is further complicated by the fact that the fea­ tures are highly context-sensitive; the predictiveness of a feature depends heavily on the current context. They use so-called pulling and pushing techniques to adjust the feature weights. Given a target T and two cases A and B, if it is judged that A is a ~orrect solution toT but B is not the learning method wtll push B away from T, and pull A closer to T. As to its weight updating ~ol­ icy, their introspective learning metho~ uses a decaymg learning process as shown in the followmg two formulae .

where Ke represents the number of times that a case has been correctly retrieved, Fe represents the number of times that a case has been incorrectly retrieved, and ~i determines the initial weight change. The ratio be­ tween Fe and Ke is used to reduce the influence of the weight update as the number of successful retrievals in­ creases. We can observe that the timing of triggering the adjustment process is very important; when to trig­ ger the adjustment of the weights using the above two formulae is a crucial issue yet to be further addressed in the work. This limitation makes it necessary to in­ volve a human user in the learning process. In contrast, instead of relying on a domain-independent decaying fac­ tor, what we propose in this paper is a continuallearni~g process in the lifetime of the case based reasoner. Thts extension releases the human manager of the decision to explicitly trigger a learning process.

The second limitation of the work by Bonzano et al. is that it is qualitative in nature. While the direction of change in feature weights is indicated in the above two formulae, the amount of change is only influenced by the frequency of successes and failures and the decaying factor. A quantitative change would be needed to reflect the amount of adjustment in proportion to the error.

The third limitation, reported by the authors, is that the learning method does not work well for pivotal cases, as the redundancy in a case base is essential in such a learning process. A pivotal case is the one that pro­ vides coverage not provided by the other cases in a case base [Smyth and Keane, 1995]. In contrast, the quantita­ tive introspective learning paradigm that we will present in this paper will allow not only pairs of cases to be com­ pared, but also any number of cases to participate in the learning process. This is achieved through a process in which a user can provide feedback at any time to all top­ ranking cases, not just to a few selected. In Section 4, we will provide experimental comparisons between the quantitative and qualitative methods.

3 A Quantitative Introspective Learning Paradigm

3.1 Problem Statement

Using introspective learning, we wish to acquire feature weights in a case base in a changing and multi-user en­ vironment. In a changing environment, users and their preferences for what cases are the best for their problems also change with time. For example, in an electronic commerce application using CBR, cases may represent a configuration of a product (say a computer) model. The features then can represent various user specifica­ tions on the product, and the weights can indicate the level of interest of a user in a particular feature. Since a user's preferences may change with time, there is a need to acquire and track her/his preferences. Furthermore, in a multi-user environment, there is a strong need for catering to users with different needs. For example, an on-line computer vendor may have different sets of fea­ ture weights for students and teachers. It is desirable to adapt a CBR system with its users.

Our assumptions for the research are as follows . We assume that our desired quantitative introspective learn­ ing model is given as an input a set of features where each feature has some values. Some subset of the fea­ tures and values may be relevant to a particular case at hand at any given time, but there is no prior knowledge on which ones are actually useful to the reasoner cur­ rently. Our model monitors its running process through the interactions with its users.

For a case base our learning task is of two folds:

1. Weight acquisition to acquire the feature weights after a user has used the system for a certain period of time;
2. Continual tracking to adapt the feature weights to a user's preference which may change with time, and to allow different users to have different preferences.

3.2 Strategy for Feature Weighting

The mechanism in our quantitative introspective learn­ ing process resembles that of a back-propagation neural network, which is a very popular learning paradigm in AI. For details on the mathematical foundation and ap­ plications of back-propagation neural networks, see [Zu­ rada, 1992; Gupta and Ding, 1994].

More specifically, we use a two-layer architecture to model a case base. The front layer consists of a set of feature-value pairs. The back layer consists of a set of cases. A feature-value pair is associated with a case if it may exert influence on that case. Furthermore, there is a weight attached to the association. Although we use a two-layer feature weighting system in this paper , the architecture can be potentially extended to multiple layers which can include hidden layers. We address this situation in [Zhang and Yang, 1998].

Using two-layer architecture to model a case base is conceptually shown in Figure 1

For a case base of J cases, suppose that there are N features. For each feature F;, there are m; values, where i = 1, 2, · · ·, N. There is a total of I = 'L:;: 1 m; feature­ value pairs. We label these feature-value pairs as FV;, where i = 1, 2, 3, ···,I. We use Cj to represent each case, where j = 1, 2, 3, · · ·, J . There is a weight Vj,; attached to the connection between case Ci and feature-value pair FV; if there is an association between them.

Computing A Case's Score

A case's score is computed using the feature-value pairs selected by a user to represent an input query. For each case Cj, its score is computed using the following for­ mula:

where j = 1, 2, 3, · · ·, J , Sci is the score of case Cj, and X; is 1 if there is a connection between case Ci and feature-value pair FV; and FV; is selected. Otherwise X; is 0.

Learning Feature Weights

After a query is presented, all the previous cases have been scored according to Formula 3 with the promising ones at higher positions. If the user wants to feed back some information to the system as whether a case is de­ sired or not, we then can employ the following formula to compute a new weight based on her/his feedback in­ formation.

where vrr is the new weight to be computed, 1-J:!d is the old weight attached to the connection between case Cj and feature-value pair FV;, DSci is the desired score for Ci, Sci is the score computed in Formula 3, and 1J is the learning rate. X; is 1 if there is a connection between case Cj and feature-value pair FV; and FV; is selected by the user. Otherwise it is zero.

We have to emphasize that, in the above formula, the term (DSci- ScJ * (1- SbJ encodes the quantitative information, i.e., the actual gap between the desired and computed behavior. On the other hand, in Formulae 1 and 2 there is no such quantitative information encoded. Although they try to use the number of retrieval success and failure in their weight learning, we consider that such a representation is not sufficiently accurate when compared with ours.

3.3 User's Interaction Model

The introspective learning process in our integrated model is similar to that of a back-propagation neural net­ work. An important difference between them is that our learning process is interactive rather than hatching and automatic. In our learning process, there is no training data explicitly defined; the system is continuously being trained by its user throughout its lifetime. A user's re­ sponses to the system's behavior form an implicit source of training data.

After our introspective learning model is integrated into a CBR system, the problem-solving process is paradigmed in Figure 2. The CBR system receives a user's current problem description and a set of selected feature-value pairs (label 1). It will then access the weights (label 2) to compute the case scores, and present the result to the user for her/his judgment (label 3). If the user feeds back some judgment to the system (la­ bel 4), the system will compute quantitatively the gap between the computed and the desired score, and if nec­ essary, modify the weights accordingly (label 5) .

4 Empirical Tests

!he introspective feature-weight learning model is fully Implemented and integrated in the framework of the ~aseAdvisor™ system [Zhang and Yang, 1998], which 1s a CBR system implemented by the Case-Based Rea­ soning Group at Simon Fraser University. Right now the ~esultant CaseAdvisor™ system from such an integration IS able to learn the unpredictable information hidden in an end user's behavior. A user's interactions with the s~stem provide the guidance in determining quantita­ tJv~ly not only what the right direction is for updating weights but also how much the weight should be updated quantitatively.

In this section, we will demonstrate that our proposed learning model conforms to our expectations. In partic­ ular , we wish to confirm through the experiments that the model could learn a user's queries after sufficient interactions with its users and could scale up to case bases with realistic sizes. This is shown in the first ex­ periment suite which is conducted on different case bases from the Repository of Machine Learning Databases and Domain Theories 1 at the University of California at Irvine (UCI). Furthermore, in the second experiment, we perform a comparison between the quantitative method and the qualitative method proposed by Bonzano et al. We will demonstrate that the quantitative method can achieve better learning accuracy and faster convergence rate through continual updating.

4.1 Experiment with Case Bases from UCI

We take the Dermatology Database and Car Database from the UCI Repository. We test our system on both databases and obtain the similar experimental results . For brevity, in the following we focus on the Dermatology Database. The experiments are conducted on a platform of SUN SparcStation 4 (Sun OS 5.6) with 32MB memory.

The Dermatology Database contains 366 instances (tuples) and 34 attributes . We divide this database into increasingly larger databases, which contain 50, 100, 150, 200, 250, and 300 instances, respectively, and test the performance of our learning model. In our experiment, we first adapt these databases into the case bases that our system can be applied by converting all rows into cases and all columns into features . The values for a fea­ ture are contained under each column. After conversion, these case bases contain 50 , 100, 150, 200 , 250, and 300 cases, respectively. For each case base, we generate a set of queries for testing, the size of which is half the number of cases. For instance, for the case base with 300 cases the number of queries is 150. Note that in these tests' the score of a case is scaled to between 0.0 and 1.0. '

1 http:/ jwww .ics. uci.edu/mlearn/MLRepository.html

The training process is composed of five rounds for all the case bases. Figure 3 shows the error conver­ gence chart of 150 queries for the case base of 300 cases. The X-axis represents the training process while the Y­ axis represents the error ranging from 0.0 to 1.0. It can be found that , almost all the cases, after five training rounds, have their errors falling into an acceptable range (in our experiment this range is set to 0.02). The error convergence for other five case bases also demonstrates the same trends. For brevity, we do not show them here.

We also measure the average CPU time required for the adjustments for individual cases in each of these six case bases. The result is shown in Figure 4, when~ the X-axis represents the six case bases with different sizes measured in cases, while the Y-axis represents the av­ erage running time for each case in CPU seconds. We can see that the increase of the running time is in pro­ portion to the square of the number of cases in a case base. Therefore we can say that our algorithm is fast enough to be used in real-world practice, in which usually the case base sizes are not very huge. This confirms the scalability conjecture we make about our learning model.

4.2 Comparison with Bonzano et al. 's Approach

A closely related work on introspective feature-weight learning is proposed by Bonzano et al. [Bonzano et a/., 1997] (also discussed in Section 2). We implement their algorithm and examine the convergence and performance comparison between our two models. The case base in­ volved is also converted from the Dermatology Database in UCI Repository. It contains 100 cases.

There are three types of case bases in Bonzano et al. 's model. The first is the training case base (It is composed of a user's queries in our learning model), the second one is the case base itself and the third one is a test case base (in our model, there is no explicit test case base; it is implicit in the usage of the system). For the experi­ ment using their method, we set the training case base and the test case base to be the same. This compari­ son experiment is also conducted on a platform of SUN SparcStation 4 (SunOS 5.6) with 32 MB memory.

Figure 5 (a) shows the comparison on the errors be­ tween our two models. In the figure, the X-axis repre­ sents all the 50 test cases, while theY-axis represents the errors of these cases along the training process. From the figure, we can easily see that among the 50 test cases, our model produces smaller errors for 43 cases.

In order to make a further comparison on the conver­ gence trends, we plot the error chart for the first five training rounds in Figure 5 (b), where the X-axis rep­ resents the training process, while the Y-axis represents the average error for each case. The figure shows that at the very first five training rounds our model has al­ ready produced an optimal training result. Most of the trained cases in our method show the trends to approx­ imate their desired scores.

We now analyze the learning and adjustment Formu­ lae 1 and 2 used in Bonzano et al. 's model. These for­ mulae give an estimation of what should be done when a retrieval success or failure is encountered. However, such an estimation is not precise enough. For example, if the desired case has a higher (similarity) score than expected, the case is over ranked and we have to reduce the weights associated with its feature-value pairs in or­ der for it to be properly ranked, rather than increasing its weights. In the two formulae, there is no quantitative estimate associated with these information. In contrast, our adjustment strategy not only decides when to do the adjustments, but also takes into account at a more detailed level the quantitative gap between the current score and the target score, thus resulting in better learn­ ing quality.

However, we have to indicate that a limitation of our learning model, as compared to the qualitative model, is that it might take longer time to learn for each individ­ ual case. On average our model takes about four CPU

seconds while Bonzano et al. 's uses approximately 1.8 CPU seconds to complete an individual learning task.

4.3 Discussion

Our learning model allows incremental changes to be made to a case base. As shown in the above experiments, for a case base of 100 cases, our model takes about four CPU seconds (running on a Sun SparcStation 4 with 32 MB memory) to train an individual case. Therefore for 50 queries, it takes about 20 CPU minutes to train the whole case base. This shows that it is practically possi­ ble to retrain the whole network after introducing a new case into the case base.

In our experiments, we also observe an interesting phe­ nomenon among feature-value pairs. In the above case base of 300 cases, we find that not all the cases converge to their desired scores; in that experiment, five out of 150 cases in the 150 queries oscillate around their de­ sired scores. We also find that no matter how long our training process undertakes, these five cases still cannot converge. We attribute this phenomenon to the inter­ actions among feature-value pairs. Definitely, removing such interactions from a case base will help increase the learning quality. How to detect and remove those inter­ actions pose an interesting research problem we wish to address in our future work.

We have to emphasize again that the quantitative in­ trospective learning in our model is a continuous process and can be triggered at any time if necessary. Our sys­ tem will respond to its user at any time. Every time a user changes her/his behavior, the change will be cap­ tured, and reflected in the next work session.

5 Conclusion and FUture Work

We have shown the empirical test results of our quantita­ tive introspective feature-weight learning model. Based on the discussions throughout the paper, we can find that our proposed quantitative learning model fulfills our ex­ pectations. It captures the interactions between the sys­ tem and its end user, and seeks chances to evolve itself. In the experiments, the model quickly approximates a user's behavior within a number of iterations.

Our work aims to introspectively learn feature weights in a dynamic context in the case retrieval process of CBR. The needs from practical application of CBR in a fielded diagnosis system motivate us to explore their dynamic nature. The research is also motivated by our desire that a CBR system be a responsive system; its behavior needs to simulate its end user's behavior, in­ corporating her/his preferences. Furthermore, a user's behavior is changing, requiring that a CBR system keep its pace with the changes. The integration of an in­ trospective learning network into a CBR system makes these expectations possible.

We also note that our learning model has some limita­ tions. Although in our experiments nearly all the cases converge to their desired scores, we actually encounter divergence several times due to the interactions among different features. The effects of such interaction could be possibly reduced by introducing stronger bias factors into the system. We are also seeking other efficient and effective techniques to deal with the problem. In ad­ dition, one of the assumptions of our learning model is that the user of our system should be consistently one person in a certain period. If a different user comes to use the system, s/he might not satisfy and thus destroy the previous optimal case retrieval result, requiring the whole case base be retrained.

We will further explore, for our model, the more accu­ rate relationship between the average running time and the size of a case base (including the number of feature­ value pairs and cases). In the future, we hope to address these problems by introducing more effective learning and feedback control mechanisms and architectures into CBR.