Constructive Induction On Decision Trees

1 Introduction

Good representations are often crucial for solving diffi­ cult problems in AI. Finding suitable problem represen­ tations, however, can be difficult and time consuming. This is especially true in machine learning: learning can be relatively easy if the training examples are presented in a suitable form, but when the features used in describ­ ing examples are inappropriate for the target concept, learning can be difficult or impossible using selective in­ duction methods. To overcome this problem a learning system needs to be capable of generating appropriate features for new situations.

This paper is concerned with the automated construc­ tion of new features to facilitate concept learning, an issue closely related to the "problem of new terms" [Di­ etterich et al., 1982] and constructive induction [Michal­ ski, 1983]. We begin by defining "feature construction" in the context of concept learning from examples, and then proceed to identify four inherent aspects: detection, selection, generalization, and evaluation. These aspects comprise an analytical framework for studying feature construction which we describe through examples drawn from the existing systems of BACON. l, BOGART, DUCE, PLSO, and STAGGER. This framework serves as the ba­ sis for the design of CITRE, a system that performs fea­ ture construction on decision trees using simple domain knowledge. The results of our initial experiments demon­ strate CITRE's ability to improve learning through fea­ ture construction in a tic-tac-toe classification problem. Extensions of CITRE for this and other problems are also discussed.

·This research was funded by a University of illinois Cognitive Science/ Artificial Intelligence Fellowship and ONR Grant N00014-88K-0124.

2 The Problem

We state the following definition offeature construction 1 in concept learning:

Feature Construction: the application of a set of constructive operators { o1 , 02, ··· on} to a set of existing features {ft, fl, ... fm}, resulting in the construction of one or more new features {/~, /;, ... f~} intended for use in describing the target concept.

This definition emphasizes the notion of a construc­ tive operator, defined as a function mapping a tuple of existing features into a new feature. A construc­ tive operand is a tuple of features to which a con­ structive operator is applied. For convenience, an oper­ ator/operand pair will be referred to as a constructor, up until the time it becomes a new feature. The con­ structor and{ big(i}, red(i) }, for example, consists of the two place operator and{ binary, binary} and the operand tuple ( big(i}, red(i} ).

Additional implications of this definition include: 1) A feature is a function mapping instances into values. 2) All new features are defined in t.erms of ~xis~ing fea­ tures, such that no inherently new mformatwn 1s added through feature construction. 3) The definition can be applied iteratively: after a new feature is created, it may serve as part of an operand in a subsequent round of con­ struction. 4) A separate, selective induction algorith~ is assumed to make use of the constructed features m attempting to describe the target concept.

1 Feature construction is often referred to as "constructive induction." We, however, reserve the term constructive in­ duction to refer to the prediction of unobserved, disjunctive regions in instance space (see section 3.3).

3 Four Inherent Aspects

Representative examples of systems that perform fea­ ture construction include FRINGE [Pagallo, 1989], BA­ CON (Langley et al., 1987), STAGGER (Schlimmer, 1987), DUCE (Muggleton, 1987), PLSO (Rendell, 1985) and BOG­ ART [Newman and Uhr, 1965]. These systems employ a variety of techniques to a wide range of learning prob­ lems, making it difficult to identify exactly when, where, and how feature construction is performed. Through our effort to understand feature construction in such systems we have discovered some common issues and concerns. In particular, we have identified the following four as­ pects believed to be inherent to the problem of feature construction:

1. detection of when construction is required
2. selection of constructors
3. generalization of selected constructors
4. evaluation of the new features.

These four aspects are not necessarily present in ev­ ery system performing feature construction. Nor do they necessarily delineate sharply defined phases of the fea­ ture construction process. Instead, they represent four identifiable issues inherent to the general problem of fea­ ture construction that account for much of the perceived variability between systems. As a result, these aspects have proven useful as a framework for the analysis and comparison of systems (see [Matheus, 1989]), as well as in the development of CITRE. We now consider each as­ pect in detail.

3.1 Detecting the Need

If the original feature set is sufficient for the selective in­ duction algorithm to acquire the target concept, feature construction is unnecessary. Because the constructive process can be computationally expensive, it is often de­ sirable to determine when feature construction is needed. There are at least three general approaches to determin­ ing when to perform construction:

• no detection (i.e., always perform construction)
• analysis of the initial data set
• analysis of a concept description.

Some systems have no detection mechanism because they continually perform construction. The sole purpose ofBACON.l, for example, is to construct new features. A system might base detection on an analysis of the initial training set, for example using cluster or factor analysis (although none of the observed systems fully develop this approach). More typically, systems perform detection by observing the results of the selective induction system, i.e., the concept description it produces. Feature con­ struction may be deemed necessary if the learning sys­ tem fails to produce a description, or if the description fails to satisfy some measurable quality (e.g., accuracy, conciseness, comprehensibility). Using failure to trig­ ~er construction is employed, for example, by STAGGER lSchlimmer, 1987]. The presence of excessive disjuncts in a concept description can also be used for detection, as suggested in [Rendell, 1988]. We return to this last approach in section 4 to discuss its use in CITRE.

3.2 Selecting Constructors

After determining the need for feature construction, a system must select one or more constructors to use in the creation of new feature(s). The difficulty with this selec­ tion process is that the space of potential constructors is generally intractably large. Even in the simple case of a problem represented by N Boolean features the num­ ber of potential constructors is 2 2 N. For more complex problems, such as those involving numerical features, the search space can be infinite. The task of selection is to pick out a small subset of these potential constructors satisfying the representational requirements of the cur­ rent problem. This selection process can be analyzed in terms of two phases: initial and runtime selection.

The first step in reducing the constructor space is to reduce the set of potential operators to a more manageable size. This initial selection has been ap­ proached in two ways. Either a small set of simple, domain-independent operators is chosen (e.g., {AND, OR, NOT}), or a set of problem- or domain-specific operators is developed (e.g., "counting the number of wheels on a box car"). Simple operators have the ad­ vantage of being applicable to a wide range of problems, but they require multiple iterations of the constructive process in order to build up complex new features (e .g., STAGGER, PLSO). Problem-specific operators can reduce the complexity of the constructive process and thereby decrease construction time, but at the expense of be­ ing limited in application and also requiring effort and knowledge for their development.

The reduced set of constructive operators obtained from initial selection represents a system's "candidate" operator set. In every system we have encountered, the "candidate" operator set is significantly smaller than the "potential" set. Even so, this set is still intractably large in most cases, and further selection is required at runtime to choose which operators to apply, and which operands to apply them to. This runtime selection amounts to ordering the set of candidate constructors. We have ob­ served four approaches to ordering candidate constructor sets related to the following biases:

• algorithm biases
• training set biases
• concept-based biases
• domain-based biases.

Algorithm biases occur when the implementation of a feature construction algorithm arbitrarily selects one constructor over another. These biases are typically un­ desirable, being unjustified by the data or the model. Some systems use information in the training set in­ stances to help guide selection. STAGGER takes this ap­ proach by using instances that fail to agree with the con­ cept as the basis for suggesting new features. Likewise, in BOGART individual instances are used as templates for new features. Similarly, concept descriptions can be used to bias constructor selection; this approach can be espe­ cially useful if a concept description is close to the target concept (we show how this approach can be used on de­ cision trees in section 4). Domain knowledge can also serve as a selection bias, either as a set of heuristics for selecting useful constructors, or as a set of filters for re­ jecting undesirable candidate features. Our experiments with CITRE suggest that even simple domain knowledge can be a powerful selection bias (section 4).

3.3 Generalizing Constructors

The set of selected constructors may be highly specific to a set of instances or a concept depending upon the selection biases employed. Specific constructors can be generalized in ways analogous to how descriptions are generalized in learning concepts, e.g., changing constants to variables, dropping terms (see [Michalski, 1983]}. If a feature construction algorithm does not generalize be­ yond its input data, then it is only able to "compile" ob­ served features and feature values into new terms. Were­ fer to this form of feature construction as constructive compilation. If generalization is performed during fea­ ture construction, the features generated may "predict" regions of positive and negative instances that have not been observed. We call this form of feature construction constructive induction.

Figure 1 depicts a situation in which observed pairs of pieces on a checkers board (the dark pieces) have been mapped into disjunctive regions in an instance space of two abstract features. A constructive algorithm that merges these three regions, RJ, R2, and R3, into a new feature or{Rl, R2, R3}, is performing constructive com­ pilation. If on the other hand, the algorithm generalizes this new feature to or{Rl, R2, R3, R4), thereby predict­ ing the unobserved pair of pieces (the white pieces), the algorithm is performing constructive induction.

For certain learning algorithms, constructive compila­ tion alone can significantly improve learning. Consider a system that describes concepts by selecting one fea­ ture at a time (e.g., a decision tree inducer). Problems can arise when the target concept depends on the cor­ relation of two or more features, because a feature that splits the data poorly by itself may provide a very good split when paired with another feature. If a constructor is able to find this pair and compile it into a new fea­ ture, the construction of a more accurate and/or concise concept becomes possible. This result is observed in our experiments with CITRE (see also [Pagallo, 1989]).

Constructive induction is potentially more powerful than constructive compilation because it can produce new features with far fewer observed instances (an im­ portant quality when the training set is sparse). The problem with constructive induction is that it requires strong biases in order to produce valid generalizations. Strong and appropriate generalization biases are most readily available in the form of domain knowledge. The strong bias for the generalization or(RJ, R2, R3, R4} in Figure 1, for example, might have come from knowl­ edge that in checkers a feature useful at one board lo­ cation can often be translated to other board locations. As our preliminary results suggest, the use of relevant domain knowledge can significantly affect the quality of constructed features (section 4).

3.4 Evaluating Features

If the number of new features grows too large, it may be necessary to evaluate and discard some. The evaluation of new features can be approached in at least three ways:

• ignore the problem (keep all features)
• request evaluation from the user
• order the features and keep the best ones.

The first approach (e.g., in BACON .1, PLSO, and BOG­ ART) is the simplest but most limited in that it is only appropriate if the number of new features remains rela­ tively small. The second approach (e.g., inDUCE) places the burden on the user who must be sufficiently knowl­ edgeable to judge the quality of new features. The third approach (e.g., in STAGGER and CITRE) is autonomous, but it requires a measurement of feature "quality" (i.e., the credit assignment problem). One solution is to use the measure employed for selecting features during con­ cept formation as the measure for new feature evalua­ tion; we consider this technique further in the next sec­ tion. Other measures of feature evaluation have been considered (see [Seshu et al., 1989]}.

4 CITRE

The framework defined by these four aspects was used in the development of CITRE, a new system for performing constructive induction on decision trees using simple do­ main knowledge. 2 CITRE is similar to FRINGE [Pagallo, 1989] in its use oflearned decision trees to suggest useful constructors. Both systems iterate between tree learning and feature construction: a decision tree is learned, the tree is used to construct new features, the new features are used in the creation of a new tree, and the process is repreated until no new features are created. CITRE differs in its use of domain knowledge, feature general­ ization, and feature evaluation.

As suggested above, the key to tractable and effective feature construction is the use of strong biases to help the system converge to an appropriate set of new fea­ tures. CITRE uses three primary biases: concept-based operand selection, domain-knowledge constructor prun­ ing, and an information-theoretic evaluation measure. These biases, depicted in Figure 2, will now be described in terms of how CITRE handles each of the four aspects in the context of a tic-tac-toe classification problem (i.e., classifying boards as winning or losing instances).

Detection: Feature construction is performed any time disjunctive regions are detected in a candidate decision tree, as evidenced by the presence of more than one pos­ itively labeled terminal node.

Selection: The initial selection of operators was based on two criteria: First, we wanted to minimize the amount of domain-specific information present in the construc­ tive operators. Second, we wanted to test the hypothesis that useful, higher-level features can be constructed in­ crementally through the iterative application of simple constructive operators. We consequently selected the simple, generic, binary operator and{ binary, binary). The and(_, _) operator used in conjunction with the negation implicit in decision trees provides complete rep­ resentational capability for new features.

The primitive features used in the tic-tac-toe prob­ lem are the contents of the nine board positions: F = {posll, pos12, pos13, pos21, pos22, pos23, pos31, pos32, pos33}. These are nominal features having values x, o, or blank. In order to accommodate the binary operand slots of the and(_,_) operator these nominal features are converted into boolean expressions as necessary dur­ ing runtime selection (e.g., equal(pos11,z)). The size of the class of potential operands in this case ( 9 fea­ tures, 3 values) is thus 27 * 26 = 702. If N new features are actually created in round one, then round two has (N +27)*(N +26) = N 2 +53N +702 potential new fea­ tures; the number of new features will similarly increase for all subsequent rounds.

2 CITRE currently operates in conjunction with COGENT [Matheus, 1988], a decision tree induction program function­ ally comparable to ID3 [Quinlan, 1986]. Both CITRE and co­ GENT are implemented in Quintus Prolog running on Sun3 workstations.

The main bias used by CITRE in selecting the ap­ propriate operand is concept based, and is derived from the idea of "merging disjunctive regions" [Rendell, 1988]. Disjunctive regions in the decision tree are de­ scribed by the branches leading from the root to the positively labeled terminal nodes. CITRE collects the feature-value pairs (e.g., posll=x) at nodes along these positive branches and proposes all pairs of these bi­ nary feature-value pairs (e.g., equals{pos11,z}) as can­ didate operands. In a complete tree of depth D, this method results in 2D-l candidate operands. In tic­ tac-toe where D is typically less than 6, this bias re­ sults in fewer than 35 operands being proposed out of greater than 700 potential operands. This large reduc­ tion (> 700 to < 35) gives a good indication of how strong this bias is (as implied by the heavy arrows in Figure 2) . For each operand selected a new candidate feature is constructed by applying the and() operator (e .g., and{ equal( pos11, z },equal( pos12, z ))).

Domain knowledge can serve as an additional bias to filter out less promising candidate features (see Fig­ ure 2). In CITRE, domain knowledge is limited to simple facts (ground literal clauses) defining permissible rela­ tionships between constructive operands. For the tictac-toe problem we have implemented a small amount of general knowledge ·about board games: knowledge about adjacency of pieces being important (i.e., only consider new features having adjacent constituent features), and knowledge about the significance of piece type (i.e., only consider new features composed of the same type pieces). When CITRE uses this domain knowledge, the construc­ tor and{ equal( po611, z), equal( po&32, o)) would be re­ jected on both grounds.

Generalization: In the experiments described in this paper we used the single generalization operator "chang­ ing constants to variables." If a constructor's operand consists of two features having the same value, a gen­ eralized feature is proposed with its values replaced by a variable. For example, the generalization of and( equal( po&11, z }, equal( po&12, z) } becomes and( equal( po&JJ, VARIABLE), equal( po&12, VARIABLE}). Both the original candidate feature and its generaliza­ tion are added to the set of features. When a candidate feature is generalized, the resulting new feature is nomi­ nal, rather than binary, and its domain is (x,o,true). For a particular instance, the value of a generalized feature is false if the logical and{) relationship does not hold, or the variable's value otherwise (i.e., x oro).

Evaluation: Although CITRE may generate hundreds of constructors while working on a given problem, it only keeps a maximum of 27 (9 primitive + 18 constructed) features at a time. Its criterion for evaluation of features is the same as that used in deciding which feature to se­ lect during tree formation, i.e., an information theoretic measure. The "utility" of each feature is measured in terms of the information gained by using the feature to split the entire training set into disjoint subsets. They are then ordered by utility, and those features (excluding the primitives) with the lowest utilities are deleted until the total feature count is again down to 27. As shown in Figure 2, this evaluation is the final bias used in pruning the set of potential new features.

Evaluating features by their ability to effectively split the current data set works well in CITRE because the feature with the highest utility necessarily becomes the first node in the subsequent decision tree. This greedy approach can fail, however, if a new feature having a poor utility on the entire data set exhibits a relatively high utility sometime after the first split. For this reason, other forms of "deeper" evaluation are being considered.

4.1 Experimental Results

We conducted four series oftests in which we varied the use of generalization and domain knowledge as shown in Table 1. All four series were run on an identical collec­ tion of fifteen data sets. Each data set consisted of 100 randomly-generated tic-tac-toe instances, labeled either as "win for x" or "win for o." Each run iterated be­ tween tree construction and feature construction until no new features could be constructed. All decision trees constructed during a test were analyzed for accuracy on classifying a test set of 200 randomly chosen boards.

Table 1 summarizes the results for all four test se­ ries. Columns two and three indicate the use of domain knowledge and generalization for each test. The col­ umn labeled "First" lists the accuracies for the original decision trees averaged over the 15 data sets. Corre­ sponding accuracies for the final decision trees are in the column labeled "Last." The difference between the these two columns appears in the "Difference" column. The ± values indicate the 95 percent confidence intervals as determined by at-test. Under "New Terms" are the av­ erage number of new features considered per data set (measured after selection and generalization but before evaluation), with the highest number in any single run shown in parentheses. In the last column is the average difference between the number of nodes in the original trees and the number in the final trees.

On average, feature construction resulted in improved classification accuracy. For the last three tests - those making use of domain knowledge and/ or generalization - this result is significant with 95 percent confidence, with an average improvement of around six percent. Whereas there is no significant difference among the accuracy im­ provements of these three tests, the use of generalization resulted in a greater variance in accuracy. This obser­ vation reflects the fact that although generalization on average improves performance, it can lead to decreased performance on individual runs when invalid generaliza­ tions are made.

Another difference between the use of generalization and domain knowledge is evident in the number of new features considered. Without domain knowledge an av­ erage of over 360 new features were considered per data set, with a single worst case occurring in the generaliza­ tion test with the production of 941 candidate features. With the addition of the domain knowledge described above, the average drops below 40, and in the worst case is still less then 60. This difference translates directly into a significant improvement in efficiency.

In terms of number of internal decision tree nodes, the average difference does not change significantly between tests. Because the number of nodes in the trees remains constant while the accuracy is improving the difference can be attributed to the use of better features when do­ main knowledge or generalization is used.

4.2 Extensions and Other Applications

In addition to tic-tac-toe, CITRE has been applied to the problem of learning random boolean functions. Even on the simple problems thus far tested (e.g., 4 term, 3 features/term DNF functions), accuracy improvements of greater than ten percent have been observed. De­ tailed experiments in this domain are proving useful in the analysis of several aspects of CITRE's algorithm, in­ cluding variations on the concept-bias, enhanced opera­ tor sets, and the effect of various evaluation methods.

Our preliminary work on tic-tac-toe is being extended in several ways: 1) larger training sets are being used to demonstrate that generalizations tend to be more valid when based on larger samples of the instance space, 2) new operators are being explored (e.g., or(-,-), and(_,_,_)) 3) additional domain knowledge regarding board games is being used to help focus the feature construction (e.g., emphasizing corners, straight lines, etc.), and 4) more powerful generalization rules are be­ ing tested including reflection, translation, and rotation generalizers.

We intend to apply the results obtained from the tic­ tac-toe problem to more difficult board game problems such as knight-fork and chess endgames. Towards this end, domain knowledge and generalization rules are be­ ing developed specifically for the spatial properties of board games. Our ultimate goal is to develop a more general approach appropriate for the larger class of spa­ tial problems that includes, for example, LED classifica­ tion, the blocks world, protein folding, etc.

5 Conclusion

The four aspects of feature construction presented here have proven useful as a framework for analyzing existing systems and guiding the development of new construc­ tive techniques. In particular, this framework guided the design of CITRE, a new system that performs fea­ ture construction on decision trees using limited domain knowledge and simple generalization. Results on a board game classification problem suggest the appropriateness of CITRE's three strong biases: concept-based selection, domain-knowledge pruning, and an information theo­ retic evaluation measure. More specifically, our results suggest the potential importance of domain knowledge and generalization for effective feature construction - two areas to which current feature construction systems have paid little attention (see [Matheus, 1989]).

Acknowledgment

We would like to thank Gunnar Blix, Gregg Gunsch, Carl Kadie, Doug Medin, and David Wilkins for their helpful discussion and comments on the issues developed in this paper.