Concept Learning and the Problem of Small Disjuncts

1 The Problem of Small Disjuncts

Systems that learn from examples do not usually suc­ ceed in creating a purely conjunctive definition for each concept. Instead, they create a definition that consists of several disjuncts, where each disjunct is a conjunc­ tive definition of a subconcept of the original concept. Table 1 (column 2) shows the number of disjuncts in definitions induced by several different systems.

The "coverage" of a disjunct is defined as the number of training examples it correctly classifies. A disjunct is called "small" if its coverage is low. Table 1 (column 3) shows the coverage of disjuncts in induced definitions .

There are several reasons for paying special attention to the methods by which small disjuncts are created. First, many concepts include rare or exceptional cases and it is desirable for induced definitions to cover these cases, even if they can only be covered by augmenting

·support for this research was provided by the Army Re­ search Office under grant ARO-DAAG29-84-K-0060 and the National Science Foundation under grants IRI-8620052 and IRI-8858802.

!This research conducted while visiting The University of Texas at Austin Department of Computer Sciences.

Liane E. Acker and Bruce W. Porter

Department of Computer Sciences University of Texas at Austin Austin, Texas 78712

the definitions with small disjuncts. Secondly, small dis­ juncts constitute a significant portion of an i?duced def­ inition, in the sense that often they collectively match more than 20% of the examples that satisfy a definition.

The problem with small disjuncts, and the main rea­ son for reviewing the methods by which they are created, is that they are much more error prone than large dis­ juncts. Table 2 illustrates this phenomenon with the definitions created by CN2 [Clark and Niblett , 1987] in a chess endgame domain [Shapiro, 1987] . The error rate of small disjuncts is high, whereas the error rate of large disjuncts is almost zero. Disjuncts of coverage 10 or less commit 95% of the errors (column 6) even though they match only 41% of the examples (column 5). This pat­ tern of errors is not unique to CN2, or to this domain. A similar pattern occurs in the definitions created by ID3 [Quinlan, 1986] in this domain, and in the definitions created by CN2 in the lymphography domain [Clark and Niblett , 1987] (see Table 3).

Ideally, induced definitions should consist of all, and only, disjuncts that are meaningful (e .g., as measured by a statistical significance test) and have a low error rate. Definitions created by existing methods are ideal with regard to large disjuncts, but far from ideal with regard to small disjuncts. The remainder of this paper evalu­ ates three approaches to eliminating error-prone small disjuncts from a definition without adversely affecting other disjuncts in the definition.

2 Approach 1: Eliminate All Small Disjuncts

The most direct means of eliminating error-prone small disjuncts is to eliminate all small disjuncts by explicitly refusing to create disjuncts whose coverage is below a certain threshold. 1 An immediate objection to this pol­ icy is that it has the undesirable effect of creating defini­ tions that do not include the unusual cases of a concept (represented by small but significant disjuncts).

A second objection to eliminating all small disjuncts from a definition is that doing so may significantly increase the definition's error rate. The net effect of elimi­ nating all small disjuncts is difficult to predict, because it depends on the fate of the "emancipated" examples - the examples that were classified by the disjuncts that have been deleted . Table 2 (column 5) and Table 3 (columns 3 and 6), indicate the percentage of examples emancipated by eliminating all disjuncts up to a certain coverage.

1 The Nmin parameter in CART [Breiman et al., 1984) is this type of threshold. ASSISTANT [Cestnik et al., 1987) specifies this threshold as a percentage of the original training set. In both CART and ASSISTANT this cutoff is used in building a decision tree that is subsequently pruned.

Some emancipated examples will match disjuncts that have not been deleted. These may be classified correctly or incorrectly, and a disjunct's error rate on emancipated examples may be much higher than its original error rate. Emancipated examples that fail to match any disjunct may be assigned a default classification, or allowed to pass as errors of omission. Most existing systems have rules, called default rules, for assigning a default clas­ sification. These rules often have very high error rates. Consequently, in these systems, there is a considerable chance that emancipated examples will be misclassified. The only examples that ought to be emancipated are those that match disjuncts with high error rates, say, 25% or more. Small disjuncts, although much more error-prone than large disjuncts, do not consistently have error rates high enough to justify a policy of eliminating all small disjuncts.

An error of omission occurs when a test example is not assigned a classification. It is a indication that sev­ eral classifications of the example are equally strongly supported by the training set. In many circumstances, errors of omission are more desirable than extremely error-prone default classifications. For this reason, the discussion of "approach 3" gives equal consideration to definitions with default rules and those without.

3 Approach 2: Eliminate Undesirable Disjuncts

Techniques that directly measure, or estimate, the signif­ icance and error rate of disjuncts are used in several sys­ tems (e.g., CN2, CART (Breiman et al., 1984], ASSIS- TANT [Cestnik et al., 1987], and recent versions of ID3). These techniques reliably eliminate undesirable large dis­ juncts (i.e., ones that are not meaningful, or have a high error rate), but, as currently used, do not reliably elimi­ nate undesirable small disjuncts. This section considers the prospects of strengthening these techniques so that they reliably eliminate undesirable disjuncts, small and large alike.

3.1 Significance Testing

Tests of statistical significance are used in some systems to determine whether or not to include a disjunct in a definition. Definitions produced using these tests tend to have fewer disjuncts, larger disjuncts, and slightly lower error rates than definitions produced without using them.

Disjuncts whose coverage is too low do not pass sig­ nificance tests. The coverage at which disjuncts become "insignificantly small" is determined by the significance threshold chosen for the test (typically 90-99%), the number of concepts, and the distribution of training ex­ amples among concepts. For example, if a training set has an equal number of examples of two concepts, a dis­ junct is 99% significant if and only if its coverage is 7 or more. Because significance tests eliminate all small dis­ juncts, they are subject to the objections raised in the preceding section.

A further problem arises with systems that do not use true significance tests. Most systems use tests that accu­ rately approximate significance tests only for large dis­ juncts. Some of these systems, such as CN2, apply the approximate tests to small disjuncts despite their inaccu­ racy. Others, such as ID3, refrain from testing the signif­ icance of small disjuncts 2 . In any case, the significance of small disjuncts is not reliably estimated, with the un­ desirable result that significant small disjuncts may be eliminated and insi~nificant ones retained. This problem is not insuperable: [Niblett , 1987] gives an exact test for significance.

2 [Quinlan, 1986, page 154]. The action taken in lieu of a significance test is not described.

3.2 Error-Rate Estimation

Error rate cannot be tested exactly: it can only be es­ timated. Like approximate tests of significance, tech­ niques for estimating error rate are not entirely reliable for small disjuncts. For example, [Cestnik et al., 1987] reports that the technique of Niblett and Bratko 3 "seems to make rather pessimistic estimation about the informa­ tion contained in learning data (it overestimates the er­ ror rate of subtrees) ... post-pruning is too drastic when the number of learning examples per class per attribute is low." (page 43).

3.3 The Need for Both Significance and Error-Rate Testing

No existing system tests both significance and error rate. "Pre-pruning" systems use significance testing; "post­ pruning" systems use error-estimation [Niblett, 1987]. Indeed, post-pruning systems have a rather strong disre­ gard for the significance of disjuncts, their sole objective being to eliminate from a definition as many disjuncts as possible without suffering too great an increase in er­ ror rate. A one-test approach is sufficient to eliminate undesirable large disjuncts, because for large disjuncts, significance and error rate are highly correlated.

However, in order to eliminate all undesirable small disjuncts, it is necessary to test both significance and er­ ror rate. This is because, for small disjuncts, error rate is not related to significance in any simple way. Nei­ ther is it related to "entropy", a measure that is often used in conjunction with significance tests. The lack of a simple relation between error rate and entropy is evi­ dent in the definitions produced by CN2 4 . CN2 creates disjuncts one at a time, evaluating, at each step, the entropy of all possible new disjuncts on the portion of the training set not covered by existing disjuncts. The new disjunct with the lowest entropy is included in the definition only if it passes a significance test. Thus, the disjunct selected at a given step had lower entropy, at that step, than the disjuncts selected at later steps, and it was statistically significant. If error rate were related to entropy, disjuncts in neighbouring steps would have similar error rates. That this does not occur is evident in the following data, which describes a typical definition.

3 This and other error-estimation techniques are described in [Niblett, 1987].

4 Clark and Niblett have observed empirically that rules of low entropy tend to have high significance ([Clark and Niblett, 1987, page 18] mistakenly reports this as a relation between rules of high entropy and high significance). Thus, if error rate is not related to entropy, then neither is it related to significance.

4 Approach 3: Make Small Disjuncts Highly Specific

The techniques considered in the previous sections have all been based on properties (coverage, significance, en­ tropy, and error rate) that are defined in terms of the set of training examples that match a disjunct. There will usually be many different disjuncts that match the same set of training examples, and these will all be indistin­ guishable by the previous techniques. That is, they will all have identical estimates of error rate, significance, entropy, and so on.

To select among disjuncts that are indistinguishable on the basis of the training set, inductive systems em­ ploy an extra-evidential preference criterion, or "bias" [Mitchell, 1980] . Definitions produced using different bi­ ases, will usually have different error rates and different distributions of errors across disjuncts. It is possible that the problem of error-prone small disjuncts is caused by the use of the "maximum generality" bias (defined be­ low). This bias is used by many inductive systems, in­ cluding ID3 and CN2. The use of a different bias might result in definitions in which all disjuncts, large and small alike, have low error rates . This approach has been ex­ plored experimentally, by comparing the definitions pro­ duced by CN2 when it is biased in different ways.

Three biases are compared in this section. All are defined in terms of a disjunct's "specificity", which is defined as the number of conditions in a disjunct (re­ call that a disjunct is the conjunction of one or more conditions). "Generality" is the opposite of specificity. To compare the definitions produced by the different bi­ ases, a training set of about 200 examples was drawn at random from the 3196 examples in the KPa7KR (chess endgame) dataset. CN2, using each bias, was run on the training set. The definitions produced were evaluated using the entire dataset. This procedure was repeated for 9 independently drawn training sets. The cumulative results of these 9 runs are given in Table 4 (see [Acker, 1988] for more details).

CN2's original bias is the maximum generality bias. An inductive system using this bias, having decided to create a disjunct that matches a particular set of train­ ing examples, selects a maximally general disjunct that matches those examples and no others. The definitions produced by CN2 using this bias are described in Table 2 and the top .row of Table 4. The problem of error-prone small disjuncts is evident in this data. Small disjuncts (coverage 5 or less) have an error rate of 16%, whereas large disjuncts have an error rate of 6.1 %. Ignoring ex­ amples classified by the default rule, small disjuncts com­ mit about 25% of the errors even though they match only about 10% of the examples.

The maximum generality bias works well for large dis­ juncts, but not for small disjuncts. This suggests re­ stricting its use to large disjuncts, and using a differ­ ent bias for small disjuncts. The maximum specificity bias seems, on the face of it , to be appropriate for small disjuncts. An inductive system using this bias, having decided to create a disjunct that matches a particular (small) set of training examples, selects the disjunct consisting of all the conditions that are satisfied by those examples.

The middle row in Table 4 describes the definitions produced by CN2 using the maximum generality bias for large disjuncts and the maximum specificity bias for small disjuncts. In these definitions, the large disjuncts are identical to those in the original definitions, but the small disjuncts are maximally specific instead of being maximally general. The small disjuncts created using this bias match many fewer examples than are matched by the small disjuncts created using the original bias (1707 compared to 3128). The error rate of small dis­ juncts has decreased considerably, indicating that the 1421 examples emancipated by using maximally specific disjuncts were a major source of error.

Unfortunately, use of the maximum specificity bias for small disjuncts has adverse affects on other parts of the definition. The emancipated examples, 75% of which are classified by large disjuncts, are misclassified at a rate of almost 50%, which is double the rate at which they were misclassified by the small disjuncts . Consequently, there is a net increase in the error rate of the definitions that is unacceptably large.

The maximum specificity bias moves in the right di­ rection, but it goes too far . Using a "selective speci­ ficity" bias , an inductive system, having decided to cre­ ate a disjunct that matches a particular (small) set of training examples, would select the disjunct consisting of the conditions that are satisfied by those examples and that meet certain other requirements. These other requirements are what make the specificity selective. A disjunct produced using this type of bias may be maxi­ mally specific, maximally general , or neither, depending on whether all, none, or some of the conditions meet the requirements.

The particular selective specificity bias used in this experiment required the conditions in the disjunct for subset S of training set T to match no more than 25% of the examples in T- S whose class differs from that of the majority of S. For example, suppose there are two classes, CI and C2 , that the majority of examples in S are in CI, and that · G is a maximally general disjunct for S. Then a condition matching all the examples in S is added to G, according to this selective specificity bias, if and only if it matches fewer than 25% of the c2 examples in T- S .

The bottom row in Table 4 describes the definitions produced by CN2 using the maximum generality bias for large disjuncts and the selective specificity bias for small disjuncts. The small disjuncts produced using the selec­ tive specificity bias are superior to those produced using the other biases. They have a reasonably low error rate, which they did not have when the maximum generality bias was used, and they are doing a significant amount of the classification, which they did not do when the maximum specificity bias was used. When the selective specificity bias is used for small disjuncts, large disjuncts have a slightly higher error rate than when the maximal generality bias is used. Likewise, the error rate of defini­ tions is slightly higher using the selective specificity bias than it is using the maximum generality bias. However, this difference is due entirely to the error rates of the default rules . Ignoring the default rules, the definitions produced by both biases match almost the same number of examples (95% of the test set) and have almost identi­ cal error rates (7.2%) . Thus, the problem of error-prone small disjuncts is solved, to a significant degree, by using the maximum generality bias for large disjuncts and the selective specificity bias for small disjuncts .

The success of this approach depends, to some extent, on having defined "small" as coverage ~ 5. Table 5 gives the results of repeating the preceding experiments with "small" defined as coverage ~ 9. These results are sim­ ilar to the previous ones in three important ways. First, the error rate of small disjuncts is reasonably low when the selective specifity bias is used for small disjuncts but not when the maximal generality bias is used. Secondly, both biases produce large disjuncts with low error rates. Thirdly, the error rate of definitions is higher when the selective specifity bias than when the maximal general­ ity bias is used, and this difference is entirely due to the increased use and error rate of the default rule.

There are also significant differences between the definitions produced using the different definitions of "small". The error rate of definitions is considerably lower using coverage ~ 5. However, if default rules are ignored, the opposite is true. Using coverage ~ 9, the collective error rate of large and small disjuncts is only

5.2%, compared to 7.2% using coverage ~ 5. On the other hand , using coverage ~ 9, the large and small dis­ juncts collectively match only 90% of the test examples, compared to 95% using coverage ~ 5.

5 Conclusions

This paper has demonstrated that existing concept learning systems do well at creating large disjuncts, but poorly at creating small ones. Some of the causes of this poor behaviour have been identified. Improvements that are suggested by this analysis are (1) use exact sig­ nificance tests; (2) test both significance and error-rate; and (3) use errors of omission instead of default classi­ fications whenever possible. A fourth suggestion, that different biases ought to be used for large and small dis­ juncts, was investigated experimentally. The use of the maximum generality bias for large disjuncts and a se­ lective specificity bias for small disjuncts partly solved the problem of small disjuncts. This result is relatively insensitive to the exact definition of "small" .

Acknowledgements

We are especially grateful to Peter Clark, of the Thr­ ing Institute (Glasgow), who provided the source for CN2, the definitions it produced on the lymphography dataset, and the KPa7KR dataset generated by Alen Shapiro[Shapiro, 1987]. Peter also answered many ques­ tions, and gave helpful criticism of early drafts of this paper. We also wish to to thank Ray Mooney, for his re­ construction of ID3, Ray Bareiss, for providing the def­ initions produced by Protos, and Larry Rendell, for his comments on an early draft of this paper.