Constraints on Tree Structure in Concept Formation

1 Background and Motivation

The task of concept formation involves the incremental acquisition of concepts from unlabeled training instances (Fisher & Pazzani, in press). Much of the recent re­ search on this topic builds on Fisher's (1987) CoBWEB. Fisher's system assumes that each instance is described as a conjunction of attribute-value pairs, and employs a probabilistic representation for concepts. In particular, CoBWEB represents each concept 01c as a set of attributes A; and a subset of their possible values V;j. Associated with each value is the conditional probability of that value given membership in the concept, P(A; = V;i IC~c). In addition, each concept has an associated probability of occurrence, P( C~c). CoBWEB organizes its conceptual knowledge into a hierarchy, with nodes partially ordered according to their generality; thus, the root node sum­ marizes all instances that have been observed, terminal nodes correspond to single instances, and intermediate nodes summarize clusters of observations.

CoBWEB integrates the processes of classifying in­ stances and incorporating them into memory. The sys­ tem sorts each new instance I down the hierarchy, start­ ing at the root, locating nodes that summarize classes into which the instance fits well. At a given node N, CoBWEB retrieves all children and considers placing the instance in each child node C in turn; it also considers creating a new child based on the instance. The algo­ rithm uses an evaluation function, category utility (Gluck & Corter, 1985), to determine the "best" resulting par­ tition, then incorporates the instance into memory ac­ cordingly. The system then recurses, sorting the instance through memory until it produces a disjunct or reaches a terminal node. Other research on concept formation of the concept tree it constructs, in the learning algo­ rithm it employs, and in the way it classifies instances. Below we discuss each of these differences in turn.

· Also affiliated with Sterling Federal Systems.

2.1 Constraints on Memory Organization

ARACHNE's main goal is to create well-structured con­ cept trees, but this requires some specification of "de­ sirable" structures. We have chosen to state these as formalized constraints, but we have been careful to fo­ cus on local constraints that can be tested efficiently. Our hope has been that global properties would tend to emerge from these local concerns, even though we could not guarantee this would occur. The system's approach assumes that one has some similarity metric S that lets one determine the similarity of two instances, an instance and a concept, or two concepts. The constraint frame­ work does not depend on any particular metric.

Recall that, in our framework, each concept is a prob­ abilistic abstraction of the nodes below it in the hierar­ chy, and each child is a specialization of its parent. This structure suggests two local constraints on the structure of concept trees, which we believe reflect useful notions of well-formed hierarchies. The first deals with the rela­ tion between a child, its parent, and its siblings:

DEFINITION. Concept N is horizontally well placed in a concept tree w.r.t. similarity metric S if Pis the parent of N and for all siblings K of N, S(N, P) 2: S(N, K).

Thus, a concept is horizontally well placed if it is of equal or greater similarity to its parent than to any sibling. If a node N violates this constraint, it suggests that one should consider merging N with one of its siblings.

A second constraint concerns the relative similarity between a child, its parent, and its grandparent:

DEFINITION. Concept N is vertically well placed in a concept tree w.r.t. similarity metric S if Pis the parent of N, G is the parent of P, and S(N, P) > S(N, G).

Thus, a concept is vertically well placed if it is more sim­ ilar to its parent than to its grandparent. If a node N violates this constraint, it suggests that one should con­ sider promoting N to become a child of its grandparent (and thus a sibling of its parent).

Taken together and applied over all the nodes in a concept tree, these constraints can be used to define a characteristic of the entire tree:

DEFINITION. A concept tree is well organized w.r.t. sim­ ilarity metric S if all concepts in the tree are horizontally and vertically well placed with respect to S.

ARACHNE seeks to generate concept hierarchies that are well organized for a given similarity metric. We hypoth­ esize that such hierarchies will reflect concepts that are inherent in the domain.

2.2 ARACHNE's Control Structure

The ARACHNE learning algorithm has many similarities to CoBWEB but also important differences. The system accepts an instance I and a concept node N as argu­ ments, and incorporates I into the hierarchy below N. If N is a terminal node, ARACHNE (like CoBWEB) ex­ tends the hierarchy downward, creating a new concept P that summarizes N and I, making N and I children of the new concept. If N is not a terminal node, the system averages I into the existing probabilistic descrip­ tion and stores the instance as a new child. At this point, ARACHNE considers two operators for restructuring the hierarchy, and this is where it most diverges from its predecessor.

The system first checks each child C of N in turn (in­ cluding the new child I) to make sure it obeys the con­ straint that it be vertically well placed. If C violates this condition, ARACHNE promotes C, removing it as a child of N and making it a child of N's parent. (Actually, the system must recheck each constraint after applying the promote operator, since this changes the description of N). This ensures that no children of N are more similar to their grandparent than to their parent. Thus, storing a new instance as a child of a concept can cause a sibling instance or concept to "bubble up" to a higher location in memory.

ARACHNE's next step involves checking each child of N to make sure it obeys the constraint that it be horizon­ tally well placed. If two or more children are more similar to each other than either is to N, the system merges the most similar pair. This involves replacing these siblings with a new node that is their probabilistic average, tak­ ing the union of their children as its children. ARACHNE then recursively considers merging this new node's chil­ dren. In some cases, this leads to recreation of the orig­ inal siblings at a lower level in the hierarchy; in other cases, it produces further reorganizations in the subhier­ archy. In particular, if the original instance is merged with an existing concept, recursive calls of the merge operator can effectively sort it down through memory.

Once it has merged two nodes at a given level, ARACHNE checks the remaining nodes for satisfaction of horizontal well placement. If it finds two or more nodes that violate this constraint, it again merges the most similar, then repeats this process until all nodes at this level satisfy the constraint. In this way, a sin­ gle new instance can cause the system to merge succes­ sively many of the nodes previously stored at a given level, including pairs of nodes dissimilar from it. For instance, suppose ARACHNE had stored four instances of cats under a common parent, and a dog instance is added (through merging from above). Here the system would first merge the two most similar cats, then merge a third into the resulting node, and finally the fourth . The result would be two concepts, one representing the abstraction of four cat instances and the other based on a single dog. This iterative merging process differs from that used in CoBWEB, which merges nodes only when they are similar to a new instance. Thus, we expect ARACHNE will create well-structured trees regardless of the order in which instances are presented.

2.3 Similarity and Prediction in ARACHNE

Recall that ARACHNE's constraints and control struc­ ture rely on the ability to measure the similarity be­ tween nodes and/or instances. At each level, the sys­ tem uses its similarity metric to decide in which class an instance belongs by determining which class description is most similar to that of the instance. ARACHNE also uses its similarity measure to determine the depth to which it should sort an instance, halting whenever the best similarity score at the next level is no better than that at the current level. The metric also plays a role in deciding when to invoke the merge and promote operators. Hadzikadic and Yun (1989) have also used a similarity metric to guide the concept formation process; both their INC system and ARACHNE differ in this way from CoBWEB, which uses an evaluation function over an entire partition of nodes. Although ARACHNE can use different similarity functions, our tests with the system have used a simple measure of "probabilistic overlap" between the attributes of nodes and instances.

ARACHNE uses the same similarity function and es­ sentially the same control structure for prediction that it uses in learning. The system sorts an instance down the hierarchy in accordance with its constraints, except that no promotion is allowed and only merges that involve the instance are executed. 1 Thus an instance sorts to the class at which it would ordinarily become a disjunct, and a prediction is made from the last node to which it sorted. ARACHNE includes a simple recognition cri­ terion to foster prediction from internal nodes and thus avoid overfitting. As it sorts an instance through mem­ ory, the system makes a prediction from an internal node if its modal values perfectly match all the values of the instance.

3 Comparative Studies

Now that we have described ARACHNE, we must still demonstrate that hierarchies constructed according to its constraints have desirable structural properties, and that ARACHNE is competitive with CoBWEB in terms of predictive ability. In designing the algorithm, we sus­ pected that good structure would, if anything, enhance the latter ability, and sought to show this experimentally. To this end, we designed a set of comparative studies, which we report after summarizing the dependent vari­ ables we used to measure the systems' behaviors.

3.1 Accuracy of Class Prediction

Typically, researchers have evaluated inductive learning systems by training them on a set of examples and then measuring their ability to make predictions about new examples. For supervised learning methods, the predic­ tion task involves identifying the class name of a novel instance, given training instances that include this in­ formation as part of their description. In contrast, the training data for unsupervised systems like CoBWEB and ARACHNE does not include class information. Thus, Fisher (1987) introduced the task of flexible prediction, which requires the system to predict the values of one or more arbitrary attributes that have been excised from the test instances. Martin (1989) and Gennari (1990) have used similar performance measures.

1 Recall that during learning, ARACHNE can merge any two nodes at the current level. It is not limited to considering only merges that involve the instance being sorted.

However, the class name can be used for predic­ tion straightforwardly, even with unsupervised learning methods. A typical unsupervised system does not in­ clude the class name in the description of training in­ stances, but there is nothing to prevent one from includ­ ing such class information, provided the system does not use it to determine concepts. To take advantage of this idea in evaluating systems like ARACHNE and CoBWEB, we associate the class name with each instance descrip­ tion as an extra attribute, hiding the label so that it does not affect clustering. However, we do let the system re­ tain probabilities at each concept for the class labels of instances summarized by the node. To predict the class name of a new instance, the system simply classifies the instance to a node in the hierarchy and predicts the most frequently occurring label at that node.

We chose to predict class names in our comparative studies because they provide a good baseline for pre­ dictive ability. Class names are never provided by the environment; domain experts assign them based on reg­ ularities they have observed over time. Thus, they are designed to be predictable from observed features. In contrast, Fisher's notion of flexible prediction fails to dis­ tinguish between attribute~? that can be predicted triv­ ially, ones that can be predicted with appropriate knowl­ edge, and ones that cannot be predicted at all.

3.2 Quality of Tree Structure

Informal inspections of the trees constructed by ARACHNE and CoBWEB suggested that the former sys­ tem was frequently building "better" trees, in that fewer instances were situated in classes where they did not seem to fit well. ARACHNE also seemed to construct fewer "junk" nodes - spurious clusters of instances that have little in common. The challenge was to quantify these observations and to construct a measure of tree quality that could be applied to the hierarchies of both systems. This measure should not favor the guiding or­ ganizational constraints of either system. For example, we might have evaluated whether the category utility of the top-level partitioning was optimized, as in Fisher's (1987) study of tree quality in COBWEB, or how well the hierarchies adhered to global variants of the constraints set forth for ARACHNE. But these measures would be biased in favor of one of the systems.

Instead, we devised two dependent measures which we could apply to trees in artificial domains for which we knew the "correct" concept hierarchy. A good hierarchy should contain nodes that correspond to concepts em­ bodied in the data. If one knows that a domain contains well-defined, distinct concepts, then a natural measure of tree quality should reflect the degree to which the learned tree respects the known structure of the data used to build it. In keeping with this idea, we counted the percentage of formed concepts, or those nonterminal nodes whose modal values exactly matched the modal values of a concept known to exist in the data.

Furthermore, we defined a measure of well-placed in­ stances, singleton nodes that are descendents of a target concept and that match 50% or more of the modal at­ tribute values of the target concept. Concepts containing well-placed instances tend to adhere closely to their ex­ pected concept description, and show minimal presence of attribute values in frequencies that vary from the ex­ pected. A high percentage of well-placed instances in a tree implies a large number of accurate concepts.

3.3 Experimental Procedure

In our experimental studies, we carried out groups of ten runs, 2 presenting ARACHNE and CoBWEB with identical sets of randomly selected training instances for each run. We used the same test set for every run in a group. In experiments not concerned with order effects, the train­ ing instances were randomly ordered. In all cases, test instances were taken from the same distribution as the training instances. Thus, if the training data had a noise level of 90%, on average the test data would have that noise level as well.

Both systems sorted training instances one at a time through their hierarchies. Learning took place as each instance was incorporated, as probabilities in the con­ cept descriptions changed and the hierarchies were re­ structured. After each training instance, the entire test set was presented to each system, which used the hier­ archy it had formed thus far to predict the class name of each test instance. We compared this to the "actual" class name associated with the test instance, giving the system a score of one if the prediction was correct and zero otherwise. No learning was done on the test in­ stances, so it was possible to construct learning curves which plot average accuracy on the test set as a function of the number of training instances seen.

For our studies we used two versions of CoBWEB that built identical hierarchies but differed in their predic­ tion mechanisms. Recall that ARACHNE has a recogni­ tion criterion to foster prediction from internal nodes; it stops sorting an instance if its values perfectly match the modal values of a node it has reached in memory. To control for the effect on predictive accuracy, we cre­ ated a version of CoBWEB, denoted CoBWEB', which in­ cluded this mechanism. Since this noticeably affected performance only in the noisy artificial domain, we re­ port COBWEB' results only in that section.

After each system had processed the complete training set on each run, we ran the final hierarchies through our assessor of tree quality, which reported the number of concepts found and the percentage of well-placed nodes. Since we devised these measures especially for our arti­ ficial data sets, which had known, clearly-defined con­ cepts, we did not attempt to apply them in the natural domains we .tested.

3.4 Behavior on Natural Domains

We now consider some hypotheses about the relative be­ havior of CoBWEB and ARACHNE, and the experiments we carried out to test them using the dependent mea­ sures and procedure described above. Our first step in evaluating ARACHNE was to examine its behavior on some standard problems from the machine learning liter­ ature. For this purpose, we selected the domain of Congressional voting records, which Fisher (1987) has used in tests of CoBWEB, and the domain of soybean diseases, which Michalski and Chilausky (1980) used in their ex­ periments on supervised learning. The prediction in this case is straightforward:

2 The soybean results are one exception to this rule; in this case our averages are based on five runs.

Hypothesis: ARACHNE will show better predictive ac­ curacy than COBWEB in natural domains.

The congressional voting domain contains 435 instances of sixteen Boolean attributes each (corresponding to yea or nay votes), with each falling into one of two classes (Democrat and Republican). In contrast, the soybean data set contains 683 instances from 19 classes, each de­ scribed in terms of 35 symbolic attributes. 3 Thus, the two data sets differ in the number of attributes and di­ verge even more in the number of prespecified classes.

To evaluate our hypothesis, we presented both CoBWEB and ARACHNE with random samples of 100 training instances and a test set of 25 instances from the congressional domain and 150 training instances and a test set of 95 instances (five from each class) from the soybean domain. The results, averaged over ten runs for the first domain and five for the latter, reveal simi­ lar accuracies in class prediction throughout the course of learning. On the congressional records, ARACHNE reaches its asymptote slightly earlier than CoBWEB, at about 20 instances rather than 40 instances. On the soy­ bean data, CoBWEB reaches asymptote earlier, at about 120 instances rather than 140 instances. But in both cases the two asymptotes are basically equivalent and, in general, the differences we had anticipated did not emerge, forcing us to reject our hypothesis. However, we should not conclude too swiftly that ARACHNE and CoBWEB always perform at comparable levels; these two domains simply may not have characteristics that bring out their differences. This suggests another approach, to which we now turn.

3 This data set i.s much more complex than the four-class version used by Stepp (1984) and Fisher (1987).

3.5 Effects of Attribute Noise

Although studies with natural domains show relevance to real-world problems, artificial domains are more use­ ful for understanding the reasons for an algorithm's be­ havior. A common use of such domains involves vary­ ing the noise level. Noise in a training set confounds a learning system; it blurs boundaries between classes, making misclassification of instances more likely and the underlying concepts more difficult to discern. A sys­ tem trained on noisy data is susceptible to overfitting, predicting attributes at a more specific concept than it should.

We designed ARACHNE's performance and learning al­ gorithms to be robust in noisy domains, and this suggests a simple prediction about its behavior:

Hypothesis: ARACHNE will be less affected by noise than CoBWEB w.r.t. both accuracy and tree structure.

Intuitively, ARACHNE should build better trees because of its more powerful reorganization operators and con­ cern with constraints, and it should be less subject to overfitting because of its ability to predict from well­ formed internal nodes.

To test this hypothesis, we designed artificial data sets at two levels of noise. Each contained instances with four attributes, each of which could take on ten distinct val­ ues. The attributes had a prototypical value but could take on other "noise" values at some specified probabil­ ity. In the low-noise data set (noise level I), the modal value for each attribute occurred with probability 0.7, while three "noise" values occurred with probability 0.1. In the noisier data set (noise level II), the modal value for each attribute occurred with probability 0.5, while five noise values occurred with probability 0.1. Because a noise value appearing in one class was the modal value of some other class, class descriptions overlapped to some extent. About 24% of the noise level I instances and only about 6% of the noise level II instances should con­ form perfectly to the modal class description, with the remainder being noisy variants.

We carried out ten runs at each of these · noise levels, presenting CoBWEB and ARACHNE with 100 training ex­ amples in each case. Figure 2 shows the learning curves for noise level II; similar results were achieved at noise level I. The graph plots the average predictive accuracy against the number of instances seen. At noise level II, ARACHNE asymptotes at 76% accuracy, while CoBWEB asymptotes at 55% and CoBWEB', which predicts from internal nodes, at 65%. In this domain, tree quality was lower for CoBWEB (5.5 target concepts and 37% well­ placed nodes) than for ARACHNE (6.6 target concepts and 52% well-placed nodes). Accuracy differences were significant at the .001 level for ARACHNE and COBWEB and at the .01 level for ARACHNE and CoBWEB'. Differ­ ences in tree quality were significant at the .025 level.

These results only partly agree with our hypothe­ sis. ARACHNE's asymptotic accuracy is higher than CoBWEB's at both noise levels, with the difference in­ creasing with noise. By predicting from well-formed in­ ternal nodes, ARACHNE is less susceptible to overfitting. However, the picture is more ambiguous with respect to tree quality. Both systems lose tree quality as noise increases, but ARACHNE suffers less than CoBWEB, pre­ sumably because of its restructuring operators. This ex­ periment lends evidence to the view that predictive abil­ ity and tree quality are not perfectly correlated. Good tree structure does not guarantee good prediction, and good predictive performance does not mean the under­ lying hierarchy is organized to contain concepts inherent in the data, but both are important factors.

3.6 Effects of Priming in Noisy Domains

Our explanation of the previous results supposed that noise in early training instances could mislead both sys­ tems, but that CoBWEB was more susceptible to this effect than ARACHNE. If so, we should be able to elim­ inate this difference by priming both systems with well­ ordered, noise-free training instances from each class. This is equivalent to giving them background knowledge about idealized categories. This suggests a third predic­ tion about their behavior:

Hypothesis: ARACHNE and COBWEB will behave sim­ ilarly on both accuracy and tree structure when primed with well-ordered, noise-free training data.

The intuition here is that, with less need to reorga­ nize memory to recover from misleading observations, ARACHNE's restructuring operators become less impor­ tant and differences between the systems should be re­ duced. To test this prediction, we provided each system with 40 noise-free instances at the start of each run, four identical prototypes from each class, producing an ide­ alized hierarchy. We followed these data with the same noisy training sets used for the second experiment.

Figure 3 shows the results of this experiment at noise­ level II, which are somewhat surprising; results at noise­ level I are analogous though less pronounced. Priming improves ARACHNE's predictive accuracy significantly, raising it to 90% from 76% without priming. COBWEB shows an accuracy of only 63%, as did CoBWEB'. This was an improvement over CoBWEB's former level of 55%, but still below ARACHNE's performance. For both sys­ tems, priming improves tree quality. ARACHNE's quality, initially higher than CoBWEB's, improves from 52% well­ placed nodes without priming to 89%; the latter's tree quality rises from 37% to 79% with priming. Between­ system differences in predictive accuracy were statisti­ cally significant at the .001 level; tree quality differences were significant at the .01 level.

This experiment disconfirms our hypothesis. Though priming generally improves the predictive accuracy of the systems, ARACHNE still performs significantly bet­ ter than CoBWEB. Furthermore, with priming ARACHNE builds better trees at both noise levels. This suggests that ARACHNE can make better use of the background knowledge encoded in a primed tree. This may be partly due to COBWEB's greater tendency to misplace instances (incorporate them into an inappropriate concept), which affects both the accuracy of the concept description (it obtains superfluous noise) and presumably the system's ability to index and retrieve the object. Notably, al­ though priming led both systems to higher accuracy ini­ tially, ARACHNE reached the same asymptote as without priming, whereas CoBWEB's accuracy actually dropped as it saw noisy training instances. This provides further evidence that ARACHNE benefits from its ability to pre­ dict from well-formed internal nodes, thus avoiding the overfitting to which CoBWEB is susceptible.

3. 7 Effects of Instance Order

Another one of our concerns in designing ARACHNE was stability with respect to different orders of training in­ stances. Order effects are apparent in CoBWEB when different presentations of the same data produce hier­ archies with different structure. ARACHNE's operators for merging and promotion should enable recovery from nonrepresentative training orders, and this leads to an­ other prediction:

Hypothesis: COBWEB will suffer more from order ef­ fects than ARACHNE w.r.t. tree quality but not accuracy.

Gennari (1990) has reported that training order affects the structure of CoBWEB trees but does not alter their accuracy, so we did not expect ARACHNE to outperform its predecessor on the latter measure. However, we did expect it to construct well-structured concept hierarchies regardless of the training order. Our experience with CoBWEB suggested it has difficulty when every member of a class is presented at once, followed by every mem­ ber of a new class, and so forth. Thus, we tested the above hypothesis by presenting both systems with ten random orderings and ten "bad" orderings of 200 train­ ing instances from the low-noise data set described ear­ lier. The bad orderings were strictly ordered by class, so the systems saw 20 examples of each class in turn.

In this experiment our hypothesis was confirmed. In­ stance order did not affect predictive accuracy, although naturally the learning rate for the bad ordering was slower, since the systems did not see a representative of the final class until the 181st instance. Random and bad orderings produce hierarchies capable of analogous predictive accuracy, approximately 90% for ARACHNE and 80% for CoBWEB. However, tree quality differs sig­ nificantly in the two situations. Both systems locate most or all of the concepts at some level, but CoBWEB is vulnerable to misplaced instances with the pathological ordering. Whereas ARACHNE arrives at 88% well-placed nodes with the bad ordering, and a similar 86% with ran­ dom ordering, CoBWEB averages only 74% well-placed nodes when learning from the bad ordering, compared to 84% for the random ordering. Differences in predic­ tive accuracy were significant for both conditions at the .001 level. Differences in tree quality between the two systems were not significant for random orderings, but were significant at the .001 level for bad orderings.

This experiment provides additional evidence that predictive accuracy is not an adequate measure of tree quality. Apparently order effects that lead to a decrease in tree quality do not affect COBWEB's ability to index instances and predict accurately. This is consistent with Gennari's results and with our hypothesis.

3.8 Cost of Classification

Analysis of CoBWEB reveals an average-case assimilation cost that is logarithmic in the number of objects in the tree and quadratic in the branching factor (Fisher, 1987). Analysis of ARACHNE is confounded by the fact that in theory its restructuring of the hierarchy is not guaran­ teed to halt. Such cases are pathological and ARACHNE's behavior on all our data sets was tractable.

To quantify each system's efficiency in practice, we measured the number of attribute values inspected as a function of n, the number of objects incorporated, over five runs of the soybean data set, the more challenging of the natural domains we tested. Both systems appeared linear in n; CoBWEB with a correlation of 0.999 and ARACHNE with one of 0.976. However, ARACHNE ac­ tually inspected more attributes than CoBWEB, having a linear coefficient thirty times that of its predecessor. We believe that a heuristic cutoff mechanism that limits reorganization of the hierarchy would reduce cost with­ out loss of predictive accuracy or tree quality.

4 Discussion

In this paper we identified some problems with Fisher's (1987) CoBWEB, a concept formation system that achieves high predictive accuracy but does not always create well-structured concept trees. In response, we de­ veloped ARACHNE, an algorithm with explicitly-stated constraints for well-formed probabilistic concept hierar­ chies, which incrementally constructs such trees from unsupervised training data. We also reported four ex­ periments that compared ARACHNE with CoBWEB on both predictive accuracy and tree quality. We found the systems achieved comparable accuracy on two natu­ ral domains, but we found significant differences in both accuracy and tree quality using artificial data. In par­ ticular, CoBWEB tends to overfit more than ARACHNE when trained and tested on noisy instances, and it ben­ efits less from priming with noise-free data with respect to tree quality. Also, the quality of CoBWEB trees suf­ fers from misleading orders of training instances, while ARACHNE's tree structure is relatively unaffected.

Despite these encouraging results, we need more com­ parative studies before drawing firm conclusions about one system's superiority over the other. Also, ARACHNE has clear limitations that should be removed in future work. Preliminary studies suggest that the current sim­ ilarity metric has difficulty distinguishing irrelevant at­ tributes from relevant ones. However, since relevance can be estimated from stored conditional probabilities, we are confident that a different similarity function will add this capability. Also, the existing system can handle numeric attributes, but only by using Euclidean distance between means as its distance metric; future versions of ARACHNE should employ a probabilistic measure that lets it combine symbolic and numeric data in a unified manner. The system still tends to form "junk" con­ cepts; avoiding them may require additional constraints or more powerful operators for restructuring the con­ cept tree. We should also compare ARACHNE's behav­ ior to other noise-tolerant learning algorithms, includ­ ing Fisher's (1989) variant on CoBWEB and supervised methods for pruning decision trees (Quinlan, 1986).

Nevertheless, we believe the present work has shown the importance of examining the structural quality of concept hierarchies in addition to their predictive ac­ curacy. It has also shown that explicit constraints on tree structure, combined with restructuring operators for correcting violated constraints, can produce well-formed trees with high predictive accuracy despite noise and misleading orders of training instances. We expect fu­ ture work in this paradigm will lead to even more robust systems for incremental, unsupervised concept learning.

Acknowledgements

We thank W. lba, J. Allen, K. Thompson, D. Kulkarni, and W. Buntine for discussions that led to many of the ideas in this paper. The above also provided comments on an earlier draft, as did M. Drummond and L. Leedom. J. Allen formatted the figures.