A Genetic Prototype Learner

1 Introduction

The induction of concept classification methods has re­ ceived widespread attention both in the cognitive sci­ ences and in the machine learning communities. This is to be expected because the development and use of con­ cepts is a key characteristic . of intelligent behavior. A study of the acquisition of conceptual knowledge involves an analysis of the representation of this knowledge, as well as the process of drawing inductive inferences using these representations.

A number of symbolic and subsymbolic systems have been proposed to solve the problem of inductively ac­ quiring concept classification knowledge from a set of pre-classified instances. Some of the more influential symbolic. systems include ID3 [Quinlan, 1986), version spaces [Mitchell, 1986), and COBWEB [Fisher , 1987] . The most widely used subsymbolic systems for concept learning are based either on neural networks [Rumel­ hart et al., 1986] or on genetic algorithms (GAs) [De­ Jong, 1990; Holland, 1986]. Some of the more frequently used representations in symbolic concept learning sys­ tems use logic expressions and programs, decision trees and lists, hierarchical clusters, and rules. Representa­ tions used in subsymbolic systems include networks of simple computational units connected by weighted links and bit strings.

Leslie Knight

Dept of Math & Computer Sciences, The University of Tulsa U.S. A.

In addition to these mainstream machine learning ap­ proaches, there exists a significant body of work on sta­ tistical induction schemes [Breiman et al. , 1984; Cheese­ man et al., 1988]. Other researchers have been motivated by the findings of cognitive psychologists [Schaffer, 1978; Smith and Medin, 1981] and are using exemplar-based classification schemes [Aha et al., 1991; Kruschke, 1992; Stanfill and Waltz, 1986]. These methods store the set of training instances and classify a new instance by some voting scheme using a given number of nearest stored examples. The exemplar-based approach (also called the nearest neighbor classification algorithm [Vosniadou and Ortony, 1989]) is attractive because of its simple representation, and because it can be used to explain a number of human cognitive phenomena [Schaffer, 1978; Smith and Medin, 1981]. Hybrid GA-nearest neighbor algorithms have been developed to learn weights associ­ ated with individual attributes [Kelly and Davis, 1991] (used in calculating distance of new instance from the stored instances) and to store only a subset of the set of training instances [Cherkauer, 1992].

The other form of concept representation that has been commonly posited by cognitive scientists as a theory of human concept learning is that of proto­ types [Reed, 1972; Smith, 1989]. A prototype is a col­ lection of salient features of a concept . An instance can be classified using prototypes by finding the prototype with which it shares most of its features, and then using the class of that prototype. The exemplar based models of concept classification are more flexible than prototype models, but cannot account for some general aspects of ordinary concepts. Smith [Smith, 1989] concludes that for ordinary concepts like birds, we use prototypes rather than storing exemplars; for complex concepts like stu­ dents in my class, however, exemplars can be used to construct prototypes or to directly classify instances . In addition, the prototype models produce much more compact concept descriptions compared to exemplar­ based models, and hence require much less computa­ tional effort to classify new instances. The on-line com­ putation of prototypes, however, has been recognized as a difficult computational problem [Hintzman, 1986; Kahneman and Miller, 1986].

In this paper, we use a genetic algorithm [Holland, 1975] to evolve prototypes from pre-classified instances. We believe that in addition to possessing psychological plausibility, prototype models can be used to build effec­ tive classification techniques for supervised classification problems. To test this hypotheses, we have defined a set of classification problems involving two classes and two real-valued features . The constructed problems are of varying complexity as measured by the number of pro­ totypes per category required for correct classification. We compare our system with the C4.5 system [Quinlan, 1993] on these data sets.

The rest of the paper is organized as follows: Sec­ tion 2 discusses alternate representations for prototype based classification and introduces our representation; Section 3 describes the GA used to evolve these pro­ totypes; Section 4 describes the cl~sification problem set used to evaluate our system; SectiOn 5 compares ex­ perimental results of our system with the C4.5 system, and Section 6 presents the shortcomings of the current system and future research directions to address these problems.

2 Representation

The standard approach to representing prototypes con­ sists of using the descriptions of individual instances of a given class and then abstracting the more frequent prop­ erties of these instances [Kahneman and Miller, 1986]. A prototype is often represented in a slot-filler struc­ ture containing default attribute values, relationships between attributes, and weights on attributes. In these representations, prototypes are often linked in hierar­ chies. Other possible representations for prototypes in­ clude production systems [Holland et al., 1986] and con­ nectionist networks.

In general, only one prototype is constructed per class 1 . The similarity of an input instance to a prototype is calculated from their respective attribute values using a "contrast rule": attributes not having common values are weighted and subtracted from the weighted sum of the attributes having common values. This method of classification explains typicality effects seen in most nat­ ural concepts (e.g., some birds are more easily recognized as bird than others).

Using a single prototype per class, however, is not suf­ ficient to learn linearly non-separable categories. Since most practical classification problems are likely to be linearly non-separable, we allow multiple prototypes per class. The classification problems used in this paper are defined on real-valued attributes. Hence, the calculation of the similarity metric and the representation of pro­ totypes are modified to suit these domains. Our repre­ sentation of prototypes is identical to that of exemplars, that is a prototype is represented as a list of feature values together with its associated class. The similarity metric used is the Euclidean distance between the input instance and the prototype in the space defined by the features .

1 Actually, it is widely believed that an ordinary concept definition consist of a prototype constr'ucted from perceptu­ ally salient and easy to compute features and a core made up of more accurate but less accessible features [Smith et al., 1984].

Let P;j,i = {1, ... ,n}, j = {1, . .. ,m} be the value of the jth attribute of the ith prototype, and Ikj be the value of the jth attribute of the kth instance. Then the nearest prototype to the kth instance is calculated as

Note that our prototype model is similar to the ex­ emplar model in the nearest neighbor calculation. The difference is that the prototypes are, in general, distinct from any examples seen by the system, and the number of prototypes per class is restricted to a small number (5 in this paper). Our model .is ~im~lar to someyroto­ type models which calculate similanty from a distance measure in some underlying psychological space rather than measuring it by common and distinctive proper­ ties [Shepard, 1974].

3 Genetic algorithms for learning prototypes

Genetic-Based Machine Learning (GBML) systems are rule-based systems which· can be used to determine the class membership of input instances from a set of at­ tributes. A GBML system matches the set of attributes corresponding to an instance against a set of rules to determine the class membership of the instance. These domain-independent classification mechanisms are par­ ticularly useful in problem domains for which there is no known precise model to determine the class, or for which determining a precise model is impractical.

There are two principal schools of thought in designing GBML systems [DeJong, 1990]. The first school of re­ searchers proposes to use genetic algorithms to evolve in­ dividual rules, a collection of which comprises the classi­ fication expertise of the system. This approach to build­ ing classifier systems was originally proposed by ~ ohn Holland at the University of Michi&an, and hence IS re­ ferred to as the Michigan approach lHolland, 1986]. The other school of thought has been popularized by Ken De Jong and Steve Smith [Smith, 1980] from the University of Pittsburgh, and is therefore referred to as the Pitt ap­ proach to building classifier systems. In this approach, genetic algorithms are used to evolve structures, each of which represent a complete set of rules for classification. Each structure in the population in the Pitt approach corresponds to the entire set of rules in the Michigan approach.

The Pitt approach seems to be better suited for batch-mode learning (where all training instances are available before learning is initiated) and for static do­ mains. The Michigan approach is more flexible to han­ dle incremental-mode learning (training instances arrive over time) and dynamically changing domains. We have chosen the Pitt approach in this paper to take advantage of the availability of all training data before learning is initiated. The only difference with the Pitt approach is that a structure consists of a set of prototypes instead of a set of rules.

3.1 Population structures

Each population structure consists of one or more pro­ totypes belonging to each of the possible classes in the domain. Each prototype is represented as a set offeature values as described in Section 2. Prototypes belonging to the same class are placed adjacent to each other. Pro­ totypes belonging to different classes are separated by a special marker, II- Let us denote the jth feature value of the ith prototype belonging to the kth population struc­ ture by p .k. Then given a problem with two classes and two featuies, the kth structure in the population with two prototypes belonging to the first class and three pro­ totypes belonging to the second class is represented as:

Traditional GAs use bit-string representations for pop­ ulation structures [Goldberg, 1989]. Our choice of real valued representation has recently received increasing at­ tention in the GA community [Goldberg, 1991] and has been effectively used for supervised concept classifica­ tion rroblems [Kelly and Davis, 1991; Corcoran and Sen, 1994.

3.2 Operators for structure manipulation

Genetic algorithms are a class of adaptive techniques that were motivated by the effectiveness of natural evo­ lution in developing organisms well-suited to a variety of environmental conditions. A majority of the struc­ ture manipulation operators in GAs are highly abstract versions of operators found in natural genetics.

GAs operate on a population of structures, evolving more well-adapted structures to the given environment over successive generations. Each structure is evaluated in the domain to give it a fitness measure. We formu­ late the prototype learning problem as a function mini­ mization problem, where we are searching for structures that reduce the number ofmisclassifications on the train­ ing set. The number of misclassifications produced by a structure is used as a measure of its fitness. We formulate the prototype learning problem as a function minimiza­ tion problem, where we are searching for structures that reduce the number of misclassifications on the training set.

After all the structures in the population are evalu­ ated, a new generation is formed by inserting new struc­ tures into the population according to their fitness val­ ues, causing the poorer performing structures to be elim­ inated (some get copied over multiple times depending on their relative fitness). For this selection process we use a rank-based method which has been claimed to be superior to the traditional fitness proportionate selection scheme [Whitley, 1989].

Mutation is used to replace the current value of one feature of a prototype by a randomly generated number in the domain of the feature . Thus mutation allows for a drastic change in the position of a prototype along one of the dimensions in the input space (each dimension corresponds to one attribute of the problem) . Mutation takes place infrequently. The probability of mutation is set by a parameter Pmut·

A creep operator is used to displace the current posi­ tion of a prototype on the input space by a small amount. The creep operator is applied with a probability Pcr eep and changes the values of all the features of a prototype by a small percentage, 8, of their current values 2 .

A two point crossover operator is used to swap sub­ parts of two structures. The crossover points can fall anywhere within a structure. When two parents are se­ lected for crossover two crossover points are first ran­ domly selected on ;ne of the parents . Now, two points are chosen on the other parent which match up semanti­ cally with the previously chosen points on the first par­ ent . For example, if a crossover point on the first par­ ent is in between prototypes belonging to category X , the corresponding crossover point in the the second par­ ent should also fall between prototypes for category X. Similarly, if the crossover point in the first parent falls between the second and third features of a prototype be­ longing to category Y, the corresponding crossover point in the the second parent should also fall between the sec­ ond and third features of a prototype belonging to cate­ gory Y. After crossover points are sele~ted in both par­ ents, the portions of the chromosomes m between these points are swapped between the parents. to produce two offsprings. Any crossover that results m chromosomes with empty categories or with a number of prototypes for a category exceeding the maximum limit, is disal­ lowed. The following example demonstrates a valid two­ point crossover as described above (crossover points are marked by the symbol !):

4 Problem set

In order to evaluate our proposed system, PLEASE, we designed a set of problems of varying complexity. These problems were defined on two continuous attributes, x andy, each having a range of [0, 1]. So, the input space is a square of unit area. We formulated four different problems by labeling different regions of this unit square with one of two possible categories, 1 or 0. The area of the region allocated to each of the categories is equal in area for all the problems. These regions were chosen so that the classification problem can be solved with a spe­ cific number of appropriately positioned prototypes for each category. Different problems require different num­ ber of prototypes per category. The minimum number of prototypes required per category to solve the classifi­ cation problem is used as a measure of the complexity of the problem. Given a particular problem, we randomly generated a set of points from the input space and then labeled each point with the category associated with the region containing that point . These sets of points were then divided into training and testing sets.

2 In our experiments, we found faster convergence when all the feature values were changed by the creep operator rather than changing only one feature at a time.

We present the problems used in the experiments in this paper in Figure 1. The problems are labeled as N /M, where N and M stand for the minimum number of prototypes in the two categories required to accurately solve the classification problem. The darkened regions in each of the figures are associated with category 0, and the rest of the square is associated with category 1. The prototypes required to solve the problem are labeled '-' and'+' for categories 0 and 1 respectively. We should clarify that the presented problems are not unique instances of N/M problems; their choice was motivated by considerations of the ease of exposition. The following describes each of the problems in more detail:

• 1/1 problem: The unit square is divided by a diagonal into two right-angled triangles, and each assigned to one category. This is the simplest problem in the problem set, and can be solved by using only two prototypes, one each for the two categories. The two prototypes must be placed on a perpendicular bisector of the dividing diagonal and should be at the same distance from the diagonal. The proto­ types should also be correctly labeled, i.e., the pro­ totype in the region assigned to category 1 should be labeled by a '+' and the prototype in the region assigned to category 1 should be labeled by a '-' (we will assume this is the case when describing the other problems). Such an orientation of the proto-

types means that any point in the upper triangle will be closer to the prototype in that triangle and hence classified correctly. The interesting thing to note here is that the above solution description al­ lows for an infinite number of minimal solutions 3 to the problem (infinite number of perpendicular bi­ sectors of the diagonal, infinite number of pairs of points on any of these bisectors that are equidistant from the diagonal). One such solution is showed in the figure 4 .

• 2/1 problem: In the particular 2/1 problem chosen for experimentation, a single diagonal strip associated with category 0 separates two triangular regions as­ signed to category 1. Once again, prototypes placed on any straight line perpendicular to the two diag­ onal lines can solve the classification problem per­ fectly. As a result, there are infinitely many mini­ mal solutions to this classification problem with the prototype representation we have chosen. One such placement of prototypes is shown in the figure.
• 3/1 problem: The presented problem consists of a tri­ angular region associated with category 0, and the rest of the unit square associated with category 1.

3 Minimal solutions refer to solutions that require the min­ imal number of prototypes for each category.

4 The placement of the prototypes in the figures are only approximately correct.

X

X

In contrast to the above problems, there is a unique minimal solution to this problem. This solution is found by first drawing perpendicular bisectors of the three sides of the triangle and placing the '-'proto­ type at the intersection of these three bisectors. The three '+' prototypes are then placed at points out­ side the triangles obtained by reflecting the position of the '-' prototype about each of the three sides of the triangle.

• 4/1 problem: The presented problem consists of a square embedded within the unit square and with vertices placed on the midpoints of the sides of the unit square. The embedded square is associated with category 0 and the rest of the unit square is associated with category 1. Once again, there ex­ ists a unique minimal solution to this problem. This solution is obtained by placing the '-' prototype at the center of the square, and the four '+'prototypes at the four vertices of the unit square.

The problem set, therefore, consists of problems of varying complexity, both in terms of the minimal num­ ber of prototypes required per category to solve the clas­ sification problems, as well as in terms of the number of minimal solutions existing for the problems.

5 Experimental results

In this section, we present results from experiments con­ ducted to solve the previously mentioned classification problems using both PLEASE and C4.5. We have used the cross validation error estimation technique [Breiman et a/., 1984] for evaluating the performance of the algo­ rithms on the problem set. For each of the problems, 1000 points were randomly generated from the input space and classified according to the region from which it was drawn. We used a five-fold cross validation, gen­ erating five different training/testing set splits. In each such split, 800 input instances were used for training, and the remaining 200 were used for testing. The con­ straint imposed on training/test split was that both the categories were equally represented in the training and test sets. Additionally, within a category, all the regions were also equally represented. Results obtained with the C4.5 system are averaged over these five training/testing set splits for each of the problems. Our PLEASE system uses genetic algorithms for learning prototypes, and the performance of the latter depends on the random initial population. As such, the PLEASE system was run on each training/testing split with 10 different random ini­ tializations . The results of PLEASE on each problem, therefore, is averaged over 50 runs.

The parameters used for the PLEASE system in these experiments are as follows: population size = 150, num­ ber of generations = 200, Pmut = 0.0001, Pereep = 0.3, 8 = 0.1, selection bias= 1.7, maximum number of pro­ totypes per category = 5. Table 1 contains the average and standard deviations of the percentage error rates of C4.5 and PLEASE on each of the four problems in the problem set.

The main observations from these results are as fol­ lows:

• PLEASE was consistently able to discover a set of prototypes that achieved near-perfect classification accuracy.
• The error rates for PLEASE and C4.5 increased slightly with more complex problems.
• Though C4.5 performed slightly better on training instances in the some of the problems, these dif­ ferences were not statistically significant. On the other hand, a two-sample t procedure shows that with at least 99% confidence level it can be stated that PLEASE produced lower error rates on the test instances than C4.5. The other notable difference between C4.5 and PLEASE was their relative per­ formance on the training and test cases. Training and test set errors were much more consistent in PLEASE than in C4.5. In fact, for the C4.5 system, test errors were approximately 5 to 8 times higher than errors on training instances. Since test set per­ formance is more important in supervised classifica­ tion problems, PLEASE seems to be able to better represent the underlying target concept.

We now analyze the kind of solutions PLEASE gener­ ates for the given problem set . Table 2 presents the aver­ age number of prototypes used by the best solutions gen­ erated by PLEASE for each of the four problems. The numbers show that the solutions produced use more pro­ totypes than required by the minimal solutions to corre­ sponding problems. On analyzing individual solutions, we found that some of the solutions indeed were minimal, but in general, more prototypes were used. The decision trees produced by C4.5 for these problems contained, on the average, 44.2, 57.4, 69, and 70.2 nodes for the 1/1, 2/1 , 3/1, and 4/1 problems respectively. Hence, the data compression obtained with the PLEASE system is sig­ nificantly better compared to that obtained with C4.5.

We will use a typical solution for the 4/1 problem to analyze both the nature of the solutions generated by PLEASE, and the classification errors made by such a solution. Figure 2 presents the 1000 data points for the 4/1 problem and also a typical solution produced by PLEASE together with the training and test set mis­ classifications of that solution. For the sake of clarity we have also drawn the lines outlining the embedded square for this problem. We find that the solution produced by PLEASE contains several prototypes for category 0, all clustered around the center of the unit square. The min­ imal solution contains just one prototype at the center. Similarly, there are two prototypes belonging to cate­ gory 1 placed close to each other at the left corner of the unit square. These two observations suggest the use of a prototype merging operator that will replace two prototypes by a new one in between them, if the dis­ tance between the two prototypes is less than a preset threshold. The placement of the prototypes in the solu­ tion generated by PLEASE is found to approximate the prototype locations in the minimal solution. This close approximation to the unique minimal solution produces very low classification errors, 3 on the training set and 3 on the test set.

On analyzing the misclassifications produced we find no "blatant" errors, i.e., all errors are located close to the boundary of separation between the categories. The other solutions that we have analyzed show similar trends in both the prototypes developed and the errors produced.

6 Conclusions

The choice of prototypes as a representation of target classes and the use of genetic algorithms to learn ap­ propriate prototypes for given classes has been shown to be an effective means for addressing supervised clas­ sification problems. In particular, we have provided a novel way of successfully addressing the difficult prob­ lem of on-line computation of prototypes from training data [Hintzman, 1986; Kahneman and Miller, 1986].

This paper contains an experimental evaluation of our proposed classification system, PLEASE, on a set of real-valued classification problems of varying complex­ ity. PLEASE produces near-perfect solutions to these problems and performs better than the well-known C4.5 system on these problems. In a further study with an ex­ tended set of problems [Knight and Sen, 1995], we have found the PLEASE system performs favorably compared to simple exemplar-based classification mechanism like the nearest neighbor algorithm.

The system as it stands today can be improved in a number of ways. We envision the following experiments with and extensions to the current system:

• Developing a representation for both structured and nominal attributes in addition to the ordinal at­ tributes that are used currently.
• Evaluating PLEASE for noisy immunity.
• Using prototypes with a subset of attributes (nec­ essary to handle domains with large number of ir­ relevant attributes); this goes back to the more tra-

ditional view of prototypes [Kahneman and Miller, 1986].

• Collapsing two prototypes into a single prototype if they are closer to each other than a given threshold.
• Using the inversion operator in GAs, to allow swap­ ping of prototypes between any two classes in a chro­ mosome.
• A prototype add (delete) operator that randomly selects a class in the chromosome and then adds {deletes) a prototype to {from) that class. The pro­ totype to be added may be constructed by averag­ ing feature values of a subset of the instances in the training set of that class that have been misclassi­ fied by this chromosome. A prototype may also be deleted if it did not classify any instance.
• Seeding of the population by chromosomes con­ structed from possibly useful prototypes; these pro­ totypes can be formed by averaging feature values over a certain number of instances of a class that are randomly selected from the training set.

We also plan to develop a prototype-based Michigan­ style classifier system.