PEBM: A Probabilistic Exemplar Based Model

1 Introduction

Case Based Reasoning (CBR) is an approach that utilises past situations in an attempt to solve new prob­ lems. The basic CBR cycle involves retrieving cases that are similar to the current problem and utilising them to solve the current problem. This makes memory organisa­ tion and indexing a fundamental part of CBR systems. One approach is to store a flat database of cases and scan all the cases to identify the most similar cases. For applications where many more are involved, this simple organisation is considered to be slow [Kolodner, 1993].

A more sophisticated method is to partition the cases into clusters and organise them hierarchically. The hier­ archy can then be searched more efficiently by following a path depending on the features of the new case. Dif­ ferent types of hierarchies have been proposed leading to different approaches. One approach is to use deci­ sion trees so that the leaf nodes contain the cases and where the internal nodes contain questions that can be

Sunil Vadera

School of Sciences University of Salford Salford M5 4WT, UK S. Vadera@cms.salford.ac. uk

used to partition the cases. So for example, systems like ReMind [Althoff et al., 1995] provide a tree induction algorithm that can be used to avoid examining all the cases. This kind of approach is particularly useful when large databases of cases are already available. However, when cases are not available in advance, and the domain is not well defined this approach is more difficult to ap­ ply.

Another approach is to use an abstraction hierarchy where each internal node is an abstraction of the cases represented by its children .. These hierarchies are known as discrimination networks or redundant discrimination networks when the nodes represent overlapping regions of cases. A number of research systems, such as MEDIA­ TOR and CASEY (see [Kolodner, 1993] for a description and references) have used this approach and their out­ comes have shown its utility. However, these systems require much more memory to store the network and the procedures for adding new cases are very expensive since the abstraction hierarchy may need to be restruc­ tured [Kolodner, 1993].

Thus, current approaches to CBR work well in some situations, but also have problems in other situations. In particular, for domains, sometimes called weak do­ mains [Porter et al., 1990], where: (i) the categories or concepts are difficult to define by necessary and sufficient features, (ii) the categories can be non-disjoint, (iii) the data are not structured, (iv) all the data do not exist in advance, and (v) there is uncertainty in how the cat­ egories are represented by cases, these approaches have limitations since they often require all the features and examples in advance, and do not handle uncertainty ex­ plicitly (they use a weighted sum of the differences).

An alternative approach, that is perhaps more ap­ plicable to weak domains, is to store only prototypi­ cal cases. This approach, known as the exemplar based model has its basis in cognitive theories, which postulate that concepts can be represented by exemplars [Smith and Medin, 1981]. Exemplar based models do not neces­ sarily require all the features or all the cases in advance.

This paper focuses on developing an exemplar based model. The next section presents the main problems of developing exemplar based models. The paper is organ­ ised as follows : section 3 presents the model in terms of the knowledge representation, the classification, and learning processes; section 4 presents an empirical eval­ uations on three datasets; and section 5 presents the conclusions.

2 The Problem

To understand the problem, consider the diagram shown in Fig. 1 that shows a weak domain in which there are two categories A and B (solid lines). The category A has nine cases (the points) c1, c2 , c3, c4, c6, c7, cs, cg, and c10 , and the category B has five cases c3, c4, c5, c9, and c11 . Note that the cases c3, c4 and cg are common cases that occur in both categories. The main problem is to

proceed from a view like the one shown in Fig. 1 to an exemplar based view like the one shown in Fig. 2 where the exemplars e6 , e8 , e9 , and en represent sets of similar cases (dashed lines) . That is, instead of storing all the

cases, only the prototypical cases are stored. Although conceptually, this is an elegant idea, attempting to de­ velop it raises the following difficult questions:

1. What is a good representation of the model?
2. How can a new case be classified?
3. What notion of similarity can be adopted?
4. What makes a good exemplar?
5. How can the model be learned incrementally?

The next section of this paper develops the model by addressing these questions.

3 The Model

3.1 The Knowledge Representation

One way of representing the information in Fig. 2 is to use a network in which nodes can be used to denote ex­ emplars, features, and categories. Thus, Fig. 3 shows the network representing the exemplar based model shown in Fig. 2. In this representation, the dashed lines show the relationship between categories and exemplars, and the solid lines show the relationship between exemplars and their features. So for example, category A has the exemplars e6 , e8 , and e9 and exemplar e6 has the features h, h, and !3. Notice that exemplars can be shared by categories, and features can be shared by exemplars.

As it stands, Fig. 3 is not an adequate representation of an exemplar based model since it does not contain any information about the degree of dependency between a category and its exemplars and an exemplar and its fea­ tures. So for example, a car can have features such as colour, engine, and make. But, which of them is more relevant in the representation of a car? The above rep­ resentation would not differentiate between the strong dependency: an object being a car and having an en­ gine, and the weak dependency: an object being a car and its colour.

Hence, to include the strengths of such dependencies, the relationships between exemplars and features are represented as probabilistic dependencies. That is, each feature fi, that is a leaf node in the network, is labelled with the conditional probability P(fi I e1 · · · ek), where e1 · · · ek are the exemplars that share the feature fi . Sim­ ilarly, the importance of an exemplar in the category is represented by probabilistic dependencies. Each exem­ plar ·ei, which is an intermediate node in the network, is labelled with the conditional probability P(ei I JC) , where JC is the joint category formed by the parents of ei. This probability is the prior probability of the exemplar when no evidence is available. With this ad­ ditional information, the network of Fig. 3 becomes a hybrid representation.

3.2 The Classification Process

Given the above representation, how can the following questions, raised earlier, be addressed:

• How can a new case be classified?
• What notion of similarity can be adopted?

The majority of current CBR systems address these questions by adopting a similarity metric, which is a weighted sum of the differences between a new case and a stored case [Kolodner, 1993]. The main problem with this approach is that the weights of the similarity metric need to be estimated and obtaining reliable weights is not easy for non-trivial problems (see [Wettschereck et al., 1997] for a survey).

In this paper, the notion of similarity adopted is that two cases are similar if they are represented by the same exemplar. But how can one determine if a new case is represented by a particular exemplar? Since in the above representation, the lower network that relates exemplars and features is a Bayesian network, the degree to which a new case with features hnc, · · ·, /qnc is represented by an exemplar e can be computed by:

This computation can be carried out by using propaga­ tion methods developed by Pearl (1988].

Given this capability of calculating the extent to which an exemplar represents a new case, all the exemplars could be investigated, in theory at least. However, prob­ abilistic propagations methods can be computationally expensive (it is known to be NP-hard in general) and investigating all the exemplars is therefore not practical.

Hence, first it is necessary to rank the categories in order of the likelihood of them containing a suitable ex­ emplar. This ranking has to be performed in a way that avoids missing suitable exemplars but is computationally efficient. This ranking can be obtained by utilizing an observation by Smith and Medin (1981] who point out that:

"the features that represent a concept are salient ones that have a substantial probabil­ ity of occurring in instances of the concept".

Thus, the important features will have high values of occurrence given an exemplar, i.e., high values of P(/j I e). Hence, a reasonable way of ranking the cate­ gories is to obtain the contribution of the features of the exemplar that are present in the new case, averaged over the number of features in the exemplar e;:

where

In this equation, nc is a new case and nfe; is the number of features in the exemplar e;.

Then, the categories can be ranked in order of the rank of their exemplars. Once the ranking is obtained, a suit­ able investigation strategy can be adopted. For example, the list of categories can be investigated in order of rank until a good exemplar is found. Within each category, propagation methods can be used to assess the merits of an exemplar e by computing P(e I nc) and stopping if this is above a threshold that is normally dependent on the application.

3.3 The Learning Process

Learning an exemplar based model incrementally in­ volves two aspects: (i) learning the the model and (ii) estimating its parameters, both of which are described in this subsection.

Learning the model

The learning process of an exemplar based model needs to answer the following questions, that were raised ear­ lier:

1. What makes a good exemplar?
2. How can the model be learned incrementally?

To answer these questions, consider a situation where there is a category C that is represented by three exem­ plars e1 , e2 and e3 . Suppose a new training case with category C arrives, then there are two situations that can arise: (i) the new case is not classified by the exem­ plars in C, and (ii) the new case is correctly classified by an exemplar in C.

In the first case, clearly the new case should be re­ tained as a new exemplar since it must be different from the other exemplars. In the second case, criteria need to be developed for deciding which of the two, the new case or exemplar, will be the best representative of all cases in the region.

For exemplar based models these criteria have to be based on the notion of prototypicality. Before describing the measure of prototypicality used in this work, it is necessary to first describe the idea of a summary rep­ resentation. Earlier, an exemplar was represented as a Bayesian network with dependencies from the exemplar to its features. In general, an exemplar may not have the same features as all the similar cases that it repre­ sents. For example, an exemplar e2 may have the fea­ tures / 4 , f 6 , and fg while the union of all the features of the cases it represents may be /3, /4, /6, h, and fg. A summary representation is a Bayesian network where all the features of the similar cases are included.

Returning to the notion of prototypicality, the prob­ lem is to develop a measure of prototypicality so that a good prototype can be selected. Rosch and Mervis (1975] argued that a case is an ideal prototype if :

• it has the highest family resemblance with other members in the same category, (this is known as focality [Biberman, 1995]) and
• it has the least family resemblance with members of other categories (this is known as peripheral­ ity [Biberman, 1995]).

In the context of the model being developed here, family resemblance is viewed as the collection of similar cases and which have a summary representation. In terms of regions, a case that maximizes the probability of cover­ ing a region can be considered to have the highest family resemblance. Since the summary representation denotes regions, and takes the form of a Bayesian network, a suit­ able measure of focality of an exemplar e; is the proba­ bility of covering a region:

where SR(ei) denotes the summary representation of the region that contains ei .

Likewise, a suitable measure of peripherality is obtained by working out the average probability of an exemplar representing regions in other categories:

These two measures can be used to define a measure of prototypicality as follows. Since a good prototype is one that has the greatest focality and the least peripherality, the measure of prototypicality adopted here is:

This measure of prototypicality can now be used to de­ cide which case makes the better exemplar in a region. These considerations lead to a learning algorithm that can be summarised as follows. Given a new training case, nc, first use the classification process described above. If the case is not classified successfully, then the training case becomes an exemplar. If it is correctly classified by an exemplar e then use the above prototypicality mea­ sure to determine which of the two best represents the region of cases and retain the more representative one.

Estimating the probabilities

To use the above classification and learning processes, one needs the probabilities that define the Bayesian net­ work which represents the exemplars. Since the model is incremental, and the cases are not retained, estimating the probabilities in a manner that enables a good exem­ plar based model to be learned is a non-trivial problem.

The Bayesian exemplar based model requires the es­ timation of two parameters that need to evolve as new cases are seen:

1. prior probabilities of the exemplars in the joint cat­ egory P(e I C) and
2. the conditional probability P(f I parents(!)).

The first of these is obtained in a standard way by util­ ising the beta distribution which leads to the following equation (see [Lindgren, 1976] for details) that can be used to compute and update the prior probabilities:

Estimating the conditional probabilities P(flparents(f)) is much more difficult. In general, 2n+1 probabilities need to be estimated for n parents. In par­ ticular, there may not be enough cases in the intersection of the parent events, even if there are enough cases in the regions represented by the parents. This means that es­ timates of probabilities such as P(j I ·el, e2) could only be based on a small number of cases and would therefore be inaccurate even when many cases have been seen.

To overcome this problem, the noisy or model [Pearl, 1988] is considered. If this model can be adopted, then instead of requiring P(flparents(f)) only P(f I ei) is needed, for each parent ei of f. To see if the noisy or model can be used, consider the assumptions that it makes [Pearl, 1988]:

Accountability An event m1 is false, P(m 1 ) = 0, if all conditions listed as causes of m 1 are false.

Exception independence If an event m 1 is a conse­ quence of two conditions d1 and d2 , then the inhibi­ tion of the occurrence of mj under d1 is independent of the mechanisms of inhibition of m 1 under d2 .

In the context of this model, the exception indepen­ dence assumption can be interpreted as requiring that the absence of the feature given one exemplar is indepen­ dent of the absence of the feature given another exem­ plar. The extent to which this assumption holds depends on the way the exemplars are selected. In Section 3.3, the selection scheme uses a measure of prototypicality that aims to reduce the possibility of selecting exemplars that represents similar regions. That is, the selection scheme used minimizes the possibility of the exception indepen­ dence assumption being broken.

The accountability assumption requires that if a case is not represented by the parent exemplars of a feature, then that feature does not occur in the case. Although this may hold when an accurate exemplar based model has been learned, it clearly does not hold while it is still learning (e.g. consider a new case that should be a new exemplar) . To overcome this problem, an additional vir­ tual exemplar is added in the representation of each cat­ egory. This additional exemplar can be viewed as rep­ resenting all the cases that have not yet been seen and therefore ensures that the accountability condition holds. With this additional exemplar, the revised model is il­ lustrated in Fig. 4. As the figure shows, this introduces dependencies between the virtual exemplar and the fea­ tures. But how can the strengths of the dependencies be estimated, since the virtual exemplar represents unseen cases? Estimating the strengths of these dependencies is

a task that requires predicting the behaviour of the de­ pendencies as more cases are observed. This behaviour can be expected to have the following characteristics:

• The strengths of the dependencies should be the highest initially when no cases have been seen and ignorance is greatest.
• As more cases are observed, the strengths of the dependencies can be expected to decay since the

virtual exemplar will represent fewer unseen cases.

• There is always a small chance that a new case will be in the region represented by the virtual exemplar even after many cases have been observed.

There may be several functions that satisfy these char­ acteristics. However, this work utilises the exponential function, which is often used to represent decay (e.g., in modelling radioactivity) and takes the form:

where n is the number of cases in a category and the parameters a and .X determines the rate of decay. The lower bound of 0.1 in this function reflects the possibility that a new case will be in the region represented by the virtual exemplar even after many cases have been seen.

This completes the description of how the probabilities can be learned incrementally, thereby allowing the use of the classification and the learning procedures.

4 Empirical Evaluation

The model described has been implemented and eval­ uated on three datasets, votes, zoo, and audiology, available from the University of California repository of datasets. Due to the lack of space, this section presents only a very brief summary of the results which are pre­ sented more fully in [Rodriguez, 1998]. Table 1 sum­ marises the characteristics of each dataset. Each exper-

iment randomly partitioned the data into a 70% training set and a 30% testing set, and was repeated 20 times to obtain an average accuracy and a compression ratio (de­ fined as the proportion of cases not retained) for each class. All the experiments were carried out with the pa­ rameters .X and a set to 0.6 2 d 0.1 and a threshold of 0.75. Although no attempt has been made to find op­ timal values for these paramet.ers, the model works well with these values. The problem of recommending their optimal values given the characteristics of the domain is a subject for future work. Tables 2 and 3 give the results for the votes and the zoo datasets. As the re­ sults show, the model performs well both in terms of accuracy and the number of exemplars retained. The overall compression ratio for the votes dataset is 97% with an accuracy of 89%. The overall compression ratio for the zoo dataset is 87% with an accuracy of 92%. In Table 3, an interesting difference in accuracy occurs between class-3, which has a low accuracy of 16% and class-5 which has an accuracy of 77% and both classes have about 3 training cases on average. A close look at the classes reveals the reason for this behaviour. Class3 consists of five relatively different animals: pitviper, seasnake, slowworm, tortoise, and tuatara, while class-5 consists of fairly similar animals: frog , poisonous frog , newt, and toad. Since, class-3 is very polymorphic and only a few cases have been observed, the exemplars rep­ resenting that category are weak and hence the accuracy of class-3 is low. However, although there are only a few cases in class-5, they are similar and the exemplars are therefore more representative of the category. Hence, the accuracy for class-5 is significantly better.

1 The category of all the unclassified cases is omitted.

Figure 5 present the accuracy obtained, and the num­ ber of training cases per category for the audiology dataset. The accuracies obtained are good for some of the categories and poor for some categories where there are few training cases. This behaviour is to be expected since the model is not expected to learn exemplars from a few cases. The motivation for applying PEBM to the audiology dataset was to enable some comparison with a closely related system, PROTOS [Bareiss, 1989] that utilised that data. Unfortunately, due partly to the na­ ture of PROTOS, and partly because of the lack of avail­ ability of the information utilised in the PROTOS ex­ periments, it is not possible to repeat the experiments reported in [Bareiss, 1989]. Although it would be incor­ rect to draw comparative conclusions from the results of the single trial presented in [Bareiss, 1989], it is encour­ aging that the results obtained in terms of accuracy and compression ratio, are similar to those obtained when PROTOS was trained with the aid of an audiology ex­ pert (see [Rodriguez, 1998] for details).

5 Related Work and Conclusion

The model presented in this paper is related to work on CBR, Bayesian networks, and inductive learning. There are numerous systems in these categories and a compari­ son with these systems is too lengthy for the space available in this paper. It is, however, important to mention the main differences with two of the most related models: PROTOS and Tirri et al.'s [1996] model. The represen­ tation used by PROTOS is similar to the one used by PEBM in that exemplars are used to define categories. The notionof exemplar is , however, very different in that cases denote exemplars, whereas in PEBM, exemplars are represented by Bayesian networks. The classification process used by PROT OS is dependent on the use of in­ dices called remindings, censors, and difference links. In contrast, classification in PEBM is achieved by proba­ bilistic propagation. The learning mechanisms are also very different since PROTOS relies heavily on heuristics that learn from user provided explanations, while PEBM learns from data. The most significant difference, how­ ever, is that PEBM has foundations in probabilistic rea­ soning, whereas PROTOS appears to be based primarily on heuristics.

The Bayesian network representation used in Tirri et al. 's [1996] work is very simi.lar to the one adopted for PEBM but with the exception that their upper level nodes are random variables that represent cases and not prototypes. Given the potentially large number of cases, standard propagation methods would not be practical. Hence, they assume that the cases are mutually exclu­ sive in order to simplify the network to a tree. The extent to which this assumption holds or the effects of violating the assumption are unclear since a new case can be expected to be similar to a number of previous cases. In contrast, PEBM does not make this assump­ tion and uses exemplars which aim to represent regions of similar cases. This difference is also reflected in the requirements for learning, since their model only esti­ mates the probabilities from all the cases, while PEBM identifies prototypes incrementally.

To conclude, this paper has presented an exemplar based model with foundations in Bayesian networks. The model learns exemplars by using a measure of prototypicality and utilises probabilistic propagation to de­ termine whether a new case is similar to an exemplar. The model has been evaluated on 3 datasets and shows promising results in terms of accuracy and in terms of the number of exemplars retained.

Acknowledgements

The authors are grateful to Enrique Sucar for his useful comments and discussions on the model presented in this paper.