Lookahead and Pathology in Decision Tree Induction

1 Introduction

The standard algorithm for constructing decision trees from a set of examples is greedy induction - a tree is induced top-down with locally optimal choices made at each node, without lookahead or backup. As the greedy approach can produce suboptimal trees in terms of tree size and depth , it is naturally of interest to explore ways to improve the greedy strategy.

Fixed-depth lookahead search is a standard technique for improving greedy algorithms [Sarkar et a/., 1994] . Lookahead is largely unexplored in the decision tree lit­ erature barring a few scattered attempts discussed in Section 5. The advantages, or lack thereof, of looka­ head search have not been systematically quantified in the context of decision tree or rule induction.

With the rapid increases in computing power in recent years, limited lookahead is now feasible for moderately large data sets. The question that therefore arises is, what are the benefits (if any) that we might gain from employing this more costly approach? In the current pa­ per, we attempt to answer this question empirically. We compare greedily induced trees with those induced with one-level lookahead, using two large classes of synthetic

Steven Salzberg

Department of Computer Science Johns Hopkins University Baltimore, MD 21218. U. S. A.

salzberg@cs.jhu. edu

data and eight real-world data sets from the UCI ma­ chine learning repository [Murphy and Aha, 1994]. The results suggest that:

• Limited lookahead search does not produce signifi­ cantly better decision trees. On average, it produces trees with approximately the same classification ac­ curacy and size as greedy induction .
• Limited lookahead search produces inferior decision trees in a significant number of cases; i.e., decision tree induction exhibits the same pathology that has been observed in game trees [Nau , 1983].
• Tree post-processing techniques such as pruning are at least as beneficial as limited lookahead for a va­ riety of real-world data sets. In this context, we describe a new post-processing technique, decision tree balancing.

Section 2 describes our experimental method. Sec­ tions 3 and 4 present the results of our experiments with synthetic and real world data respectively. Section 5 summarizes related work in the literature and discusses open questions.

2 Experimental method

The algorithms we used in all our experiments, Greedy and Look, are described below. Look performs one level of lookahead to decide what test to use at a decision tree node, while Greedy decides based only on local consider­ ations. In the pseudocode below, S is the set of training examples, where each example is assumed to comprise a set of numeric features and a class label.

Algorithm GREEDY(S)

1. If S contains examples from only one class, halt.
2. Consider all distinct tests T of the form x < k on the features of S. The ks are chosen to be the midpoints between adjacent feature values. Choose the test T* that is the best according to a pre-defined goodness measure.
3. Split S into two subsets S1 and S2 using T* .
4. Recursively run this procedure on S1 and S2.

Algorithm LOOK(S)

1. Execute step 1 of GREEDY.
2. For each test T of the form x < k, do:

• (a) SplitS into sets S1 and S2 using T .
• (b) Find the best split of S1 into sets Sll and S12, using steps 1-3 of algorithm GREEDY.
• (c) Repeat (b) on S2 , forming sets S21 and S22.
• (d) Compute the goodness of spli tting S into Sll , S12, S21 , and S22, using the same goodness measure as GREEDY. This is T's goodness.

3. Execute steps 3,4 of GREEDY.

We experimented with two pre-defined goodness mea­ sures namely the Gini index of diversity [Breiman et al., 1984] and, information gain [Quinlan, 1986] . 1 This gave us four algorithms for our experiments, which we named Greedy-Gini, Greedy-Info, Look-Gznz, and Look­ Info. Note that Greedy-Gini is essentially identical to the CART algorithm [Breiman et al., 1984] and Greedy-Info to the ID3 algorithm [Quinlan, 1986].

Our experiments with synthetic data (Section 3) sys­ tematically compare the trees induced with one level lookahead to those induced greedily, over entire classes of decision trees. 2 We define below two classes of deci­ sion trees that are small enough to be amenable to sys­ tematic experimentation on the entire class, and general enough to be interesting. We first generated a training set TRAIN and a test set TEST. TRAIN has 500 exam­ ples and TEST has 5000 examples, with two real-valued attributes for each example. All attribute values were generated uniformly at random in the interval (0 , 1~). The same unlabeled training and test sets are used m all the experiments. Each experiment tested a different element of the concept class, and the examples were la­ beled accordingly. Trees built on TRAIN were tested on TEST for every concept in each class.

Trees are compared to each other throughout this pa­ per using three quality measures - accuracy, size_ and depth. Accuracy is the percentage of correct classifica­ tion on TEST. Size is the number of leaf nodes. Depth is the length of the longest path in the tree.

3 Experiments with Synthetic Data

3.1 C: Exhaustive vs. greedy search

We designed our first set of experiments to measure h?w close to optimal are the trees produced by greedy m­ duction on a fixed concept class. More precisely, we con­ sider a class of concepts C in which one-levellookahead is equivalent to exhaustive search; for t_his class, l?okah~ad always gives us the optimal tree, wht!e greedy ~nductwn may not . We systematically evaluate the effectiveness of greedy induction over this entire class . . .

Cis a class of binary decision trees defined as m F1g. 1, and has a total of 5844 distinct trees. (Trees that are equivalent except for having their class labels swapped are not considered distinct. ) One level of lookahead from the root in class C will always find the optimal decision tree in terms of both size and depth. Trees in this class realistically occur in many ·situations as subtrees of a larger tree , and it is reasonable to ask if we should con­ stantly check one level ahead while building such a tree in order to see if we can "finish off" a subtree. Because even one level of lookahead is very costly, we wish to quantify its possible advantages. More specifically, the complex­ ity of the standard greedy algorithm is 0( dn log n) at a node for d attributes and n examples. One level looka­ head,has complexity O(d 2 n 2 ) .

1 We chose Gini index and information gain because they have been widely used for real world applications. Experi­ ments with other goodness measures may be interesting, but we suspect the results would be similar.

2 This style of empirical investigation is made possible by the existence of extremely fast , inexpensive computers. See [Murphy and Pazzani, 1994] for another example of this style.

Using the experimental method defined in Section 2, we built 5844 trees on the set TRAIN with each of the four algorithms . Thus one tree was induced by each algo­ rithm for every possible element of C. As one levellooka­ head is the same as exhaustive search on C, Look-Info and Look-Gini produce identical trees. Figure 2 summa­ rizes the differences between the decision trees induced by Greedy-Gini, Greedy-Info, and exhaustive search ( ei­ ther Look-Info or Look-Gini) over the entire class C. The figure shows the mean and one quartile ranges of the ~c­ curacy, tree size and maximum depth. (One quartt!e range is the interval that includes 25% of the samples above and below the mean.)

As the figure shows, the differences between Greedy­ Gini, Greedy-Info, and Look are quite small , in spite of the fact that greedy induction uses only about 0.004 times as much search as exhaustive search . The average number of candidate splits evaluated per tree in C are: Greedy-Gini: 1798, Greedy-Info: 1718, Look: 419,301. The differences in accuracy between the greedy algo­ rithms and Look are negligible. The difference in tree size between Greedy-Info and exhaustive search is 0.36 nodes less than one standard deviation. The difference of 0.63 between the average tree size of Greedy-Gini and Look is slightly more pronounced but still not significant . The only measure for which greedily induced trees are significantly worse than the optimal trees is maximum depth . Exhaustive search produces trees whose longest paths are on average one level shorter than what is pro­ duced with the greedy algorithms. 3

Figure 3 shows the effects of one-level lookahead (equivalently, exhaustive search) for class C in more de­ tail. The horizontal axis plots the improvement due to lookahead. The line for accuracy shows the increase in accuracy, whereas the lines for tree size and depth show the decrease in these measures when lookahead is used. The vertical axis plots the number of trees in which lookahead causes a particular improvement. For points on X = 0, lookahead had no effect, and for points to the right of X = 0, lookahead was beneficial. For points to the left of the line X = 0, greedy induction was better than lookahead. Only the measurements for information gain are shown due to space constraints.

Fig. 3 offers several interesting insights. First, each of the three lines has a single, prominent peak. The peaks at X = 0 for accuracy and tree size lines show that for a large number of trees, lookahead did not make any difference in terms of these measures. The depth peak at X = 1 shows that the maximum depth of most of the greedily induced trees is exactly one more than op­ timal. To understand why the greedy approach builds trees with unnecessarily long paths, we looked at sev­ eral of these trees individually, and found that many trees were unbalanced. That is, there were several trees in which nodes could be moved around, without alter­ ing the original partitioning and accuracy, to cut short the maximum depth of the tree. Appendix A describes a simple post-processing step to rebalance a greedily in- Improvement Due To Lookaheed duced tree, in order to reduce its worst-case classification cost. Use of this decision tree balancing procedure filled some of the gap between the greedy and lookahead trees in all our experiments.

3 Note that the effect of lookahead on average or expected depth may not be the same as that on maximum depth. The expected depth of a greedily induced decision tree has been observed to be very close to that of the optimal tree [Murthy and Salzberg, 1995].

Figure 3: Effect of one levellookahead in trees produced with information gain, for class C. Improvements in ac­ curacy, size and maximum depth are shown, along with the number of trees in which these improvements occur. Negative values on the X-axis mean that lookahead pro­ duced inferior trees.

Second, it is interesting to note that lookahead ac­ tually hurts accuracy in almost as many trees as those in which it enhances accuracy. This property, where lookahead search finds inferior solutions, is known as pathology in the context of game trees [Nau, 1983; Mutchler, 1993]. We discuss pathology for decision trees further in Section 3.2, where this trend is exhibited more prominently. Pathology cannot occur for tree size or depth for class C, because one-levellookahead is equiva­ lent to exhaustive search. However, our next class Cs in­ cludes deeper trees, and limited lookahead can and does produce trees that are worse in terms of size and depth.

Third, we can see from Figure 3 that there are some greedily induced trees that have as many as 4 leaves more than the optimal. We looked at all such large trees, and found that they always had several "minimally useful" splits , splits that were separating very few points. Such splits can be easily avoided with a simple stop-splitting rule, narrowing the gap between lookahead and greedy induction further.

3.2 Cs: A class of larger trees

This section extends class C to a class Cs, which contains slightly larger trees. Each tree in Cs is obtained from a different tree in C, as follows:

1. Remove T from C.
2. Randomly choose a leaf node L ofT.

1. Split L with a randomly chosen, non-trivial split S of the form x; < k, where k is an integer in the range (0, 10). If no valid split exists, go to step 2 and choose a different L.
2. Assign one side of S to class 1 randomly, and assign the other side to class 2.
3. Add T to Cs .

Each decision tree in Cs is a binary tree with four test (internal) nodes and has a maximum depth of 3. For these trees, one level lookahead is not sufficient to find the optimal tree. Note that while Cs has 5844 trees, the same as C, another run of the above procedure would create a different definition of Cs because of the ran­ domized steps. Using exhaustive enumeration in place of these random choices would produce a class that is vastly larger, too large for systematic experimentation. The experimental method used for Cs was identical to that used for C. One important difference is, since one­ levellookahead is not equivalent to exhaustive search on Cs , Look-Gini and Look-Info do not produce identical trees for this class.

The experimental results with class Cs strengthen the conclusions drawn from experiments with class C. Fig­ ure 4 summarizes the differences in accuracy, tree size and maximum depth between Greedy-Gini, Look-Gini, Greedy-Info, and Look-Info on class Cs. It can be seen that there is no significant improvement in accuracy due to lookahead. The differences in accuracy due to looka­ head are actually smaller here than they were for class C, despite the fact that the relative cost of lookahead search was higher for this class. The average number of candidate splits considered per tree in Cs were: Greedy­ Gini: 1952, Greedy-Info: 1847, Look-Gini: 745,689 and Look-Info: 747,037. Despite these enormous differences in computational effort, the differences in tree size are less than one standard deviation. The only quantity for which one-level lookahead caused any noticeable im­ provement was maximum depth, where trees were on average 0.6 levels shallower when lookahead was used.

Pathology results: Figure 5 shows the effect of one­ level lookahead for class Cs in more detail for Greedy­ Info . The syntax of this figure is the same as that of Figure 3; i.e., points to the left of 0 on the horizontal axis represent instances of pathology, where lookahead was worse than no lookahead. Lookahead hurt accuracy for a large number of trees in Cs , just as it did for C. In addition, it produced worse trees in terms of tree size and depth. Figure 6 shows a data set in Cs for which information gain exhibits pathology in terms of accuracy, size and depth.

4 Experiments with Real World Data

In addition to the synthetic data, we also experimented with eight real-world data sets, for which the under­ lying concepts are unknown. We augmented our algo­ rithms ( Greedy-Gini, Look-Gini, Greedy-Info and Look­ Info) with pruning for these experiments, using cost complexity pruning with the one standard error rule [Breiman et al., 1984], reserving 10% of the training data as the pruning set. All results for real world data are av­ erages of ten 5-fold cross validation experiments.

The choice of the domains is important. If a greedy method can induce a highly accurate, concise classifier for a domain (e.g., the well-known Iris data), lookahead is not likely to produce significant benefits. We used a survey ofresults [Holte, 1993] to choose six "difficult" do­ mains for our experiments - domains for which the best known accuracy is at most 90%. Though the low accu­ racies may be due to factors other than the inadequacy of greedy induction, such as an overly small or noisy tr~ining set, there is no straightforward way of knowing this a priori. The six "difficult" domains are the breast cancer recurrence database (BC) , the Cleveland heart disease data (CL) [UCI-cleveland-data, ], glass identifi­ cation data (GL), hepatitis diagnosis (HE), Canadian la­ bor negotiations data (LA) and lymphography diagnosis (LY) [UCI-lymph-data, ]. In addition to these domains we expe~imented _with two variants (VO and V1) of th~ congressiOnal votmg records data. VO is used by Nor­ ton [Norton, 1989] for his lookahead experiments. The V1 data [Holte, 1993] is identical to the VO data ex­ cept that the "best" attribute, physician-fee freez~, is removed. All the data sets were taken from the UCI Machine Learning repository [Murphy and Aha, 1994]. Our abbreviations for the data sets are consistent with those of Holte [Holte, 1993].

All experimental results reported in this section were obtained with information gain. Results with Gini index look very similar, and are omitted for space considera­ tions. Figures 7 and 8 summarize the results for accuracy and tree size respectively. The plot for tree depth looks almost identical to that for tree size, and is omitted. In each figure we plot the values of the measure obtained using f~~r induction methods: (i) Greedy-Info, (ii) Look­ I~fo , (m) _Greedy-Info with pruning and (iv) Look-Info with prumng. There are eight lines in each figure, cor­ responding to the eight data sets.

Consider the accuracy plot in Fig. 7. The first obser­ vation is that the accuracies do not vary much between various induction methods. On closer observation ac-, curacy drops for six out of the eight databases (all ex­ cept V1 and GL) when lookahead is used. In addition, Greedy-Info with pruning produces more accurate trees than Look-Info for five data sets. Pruning almost always (7 out of 8 times) works better when it is used with­ out lookahead, as can be seen from the third and fourth columns. Our overall conclusion from the accuracy plot in Fig. 7 is that lookahead doesn't affect accuracy signifi­ cantly for these domains, and that pruning is both much cheaper and more effective at creating accurate trees.

Now consider the tree size plot, shown in Fig. 8. Lookahead does reduce the tree size, by a small amount in most domains. These benefits, however, are over­ shadowed by the benefits of pruning. For all domains except the LA data (which has a very small tree to be­ gin with), pruning helps produce substantially smaller trees than lookahead.

The results of our experiments with real data support our results with the artificial data. 4 Limited lookahead did not help significantly in terms of classification accu­ racy, size or depth, despite the fact that it is enormously more expensive. It helped produce shallower trees but tree post-processing techniques much less expensive 'than lookahead (p7uning in this case) were adequate to reap comparable, If not larger, benefits. Finally, both of the goodness measures we used ( Gini index and informa­ tion gain) exhibited pathology on the real-world domains also.

5 D iscussion

Several versions of the optimal decision tree induction p~oblem are known to be NP-Complete [Hyafil and Rivest, 1976; Murphy and McCraw, 1991]. As a re­ sult, virtually all implemented decision tree systems use a heuristic , greedy approach. There have been, however, some exceptions to this rule. Moret [Moret, 1982] surveys early induction systems that used dynamic programming and branch-and-bound methods to pro­ duce optimal trees. Hartmann et al. [Hartmann et al., 1982] describe Generalized Optimum Testing Algorithm (GOTA), an algorithm based on an information theo­ retic criterion between branching levels in a tree. With the appropriate parameter settings, GOTA can do fixed­ depth lookahead, different depths of lookahead at differ­ ent branching levels or even exhaustive search. Though Hartmann et al. did offer a concise framework for doing arbitrary level lookahead, they did not evaluate the ef­ fects of lookahead on tree quality. The ideas in GOTA motivated Norton's IDX system [Norton, 1989], which is a variant of Quinlan's ID3 that performs lookahead. Nor­ ton conducted experiments on the congressional voting records database (see Section 4), and found that looka­ head reduced decision tree depth on average. With a few exceptions, though, the advantages of lookahead were very small in Norton's experiments. Ragavan and Ren­ dell considered using lookahead for feature construction in symbolic domains [Ragavan and Rendell, 1993], and pointed out that lookahead is beneficial when there is concealed attribute interaction.

4 Note that all of our "difficult" data sets happen to be quite ~mall, pr?bably inherently inadequate for learning. The expenments wtth real data are given only to substantiate the earlier observations on the artificial data. We would not make strong conclusions from the UCI data alone.

The emphasis of the current paper differs significantly from the existing work on lookahead. First, our experi­ ments are aimed to offer insights on whether or not to use lookahead when little is known about domain character­ istics or attribute interactions. Second, though existing papers do contain some remarks about whether looka­ head did or did not help, no work has yet attempted to systematically quantify how often lookahead helped, how often it did not make a difference, and how often it hurt tree quality.

The pathology results are particularly interesting, since they have not been previously reported for decision trees. Intuitively, doing more search (lookahead) should produce better decision trees, just as deeper search in game trees (e.g., for chess) produces better game-playing programs. However, it has been observed that for some games, deeper search can actually produce an inferior program, both with two players [Nau, 1983] and with multiple players [Mutchler, 1993]. Decision trees, one can argue, are analogous to a one-player game tree. Our discovery that deeper search can lead to inferior decision trees thus extends the earlier pathology results to a new domain.

It is possible that pathology is a side-effect of the way heuristic goodness measures are defined. Greedy meth­ ods grow a decision tree by optimizing entropy or class­ divergence based measures at each node of the tree. Our pathology results indicate that each such optimization is not necessarily improving the tree globally, in terms of generalization accuracy, tree size or depth. Goodman and Smyth (1988] showed that greedily maximizing the average mutual information should result in trees that are near optimal in terms of average depth. Although our experimental results are consistent with this work, pathologically deep trees indicate that locally optimizing information gain can in fact make a tree deeper.

We considered only one-levellookahead in this paper. One can attempt to evaluate the benefits of lookahead as a function of search depth . . We feel that such a system­ atic evaluation is not only going to be computationally prohibitive, but also probably not very useful. Norton [Norton, 1989] presents experiments comparing one and two level lookahead on one data set.

Observing incidences of pathology (as we did in this paper) is only the first step in several interesting research directions. Concept classes for which a particular good­ ness measure exhibits pathology can be studied, ana­ lytically or quantitatively, to determine when pathology might occur. On the other hand, one can attempt to iso­ late characteristics of data which have bearing on when lookahead is likely to help. As we have only studied two concept classes, several other interesting concepts remain to be explored. Another interesting question for further study is whether there exist effective goodness measures that guarantee no pathology.

A Decision Tree Balancing

The main benefit of lookahead search for classes C and Cs was that lookahead produced trees with shorter longest paths. On closer observation, we found that several greedily induced trees had identical partitions as the ones induced with lookahead, but the latter were shallower because the trees were better balanced. This trend sug­ gests the following problem. Given a decision tree D for a training set TRAIN, we want to produce a tree Dn that induces the same partitioning as Don TRAIN, but has less worst-case cost (or, maximum depth).

Although little work has been done on balancing de­ cision trees, a great deal of research has considered balanced search trees (e.g.: [Nakamura et al., 1993]). Roughly speaking, this literature deals with techniques to restructure search trees when elements are inserted or deleted, in order to restrict the depth of these trees to a logarithmic function of the number of search keys. An axis-parallel decision tree in a continuous space can be interpreted as a multi-dimensional binary search tree. Such an interpretation makes it possible to use search tree balancing techniques on decision trees.

The main primitives used for rebalancing a tree in bal­ anced search tree methods are rotations. Rotations are operations in which the parent-child links of some nodes in the tree are rearranged locally, while guaranteeing that the functionality of the whole tree remains invari­ ant. We have adopted two simple tree rotation opera­ tors, left-rotate and right-rotate, to decision trees. These operators are illustrated in Figure 9. We found that a heuristic top-down tree balancing procedure, using rota­ tion operators recursively at the tree nodes, significantly reduces the maximum depth of greedily induced trees for classes C and Cs. .