\documentstyle[jair,twoside,11pt,theapa]{article} \jairheading{1}{1994}{257-275}{11/93}{3/94} \ShortHeadings{Exploring the Decision Forest}% {Murphy \& Pazzani} \firstpageno{257} \begin{document} \input{psfig} \title{Exploring the Decision Forest: An Empirical Investigation of Occam's Razor in Decision Tree Induction} \author{\name Patrick M. Murphy \email pmurphy@ics.uci.edu \\ \name Michael J. Pazzani \email pazzani@ics.uci.edu \\ \addr Department of Information \& Computer Science \\ University of California, Irvine, CA 92717} \maketitle \begin{abstract} We report on a series of experiments in which all decision trees consistent with the training data are constructed. These experiments were run to gain an understanding of the properties of the set of consistent decision trees and the factors that affect the accuracy of individual trees. In particular, we investigated the relationship between the size of a decision tree consistent with some training data and the accuracy of the tree on test data. The experiments were performed on a massively parallel Maspar computer. The results of the experiments on several artificial and two real world problems indicate that, for many of the problems investigated, smaller consistent decision trees are on average less accurate than the average accuracy of slightly larger trees. \end{abstract} \section{Introduction} The top-down induction of decision trees is an approach to machine learning that has been used on a variety of real world tasks. Decision trees are well-suited for such tasks since they scale fairly well with the number of training examples and the number of features, and can represent complex concepts in a representation that is fairly easy for people to understand. Decision tree induction algorithms \cite{breiman84,quinlan86,fayyad92} typically operate by choosing a feature that partitions the training data according to some evaluation function (e.g., the purity of the resulting partitions). Partitions are then further partitioned recursively until some stopping criterion is reached (e.g., the partitions contain training examples of a single class). Nearly all decision tree induction algorithms create a single decision tree based upon local information of how well a feature partitions the training data. However, this decision tree is only one of a set of decision trees consistent with the training data. In this paper, we experimentally examine the properties of the set of consistent decision trees. We will call the set of decision trees that are consistent with the training data a {\it decision forest}. Our experiments were run on several artificial concepts for which we know the correct answer and two naturally occurring databases from real world tasks available from the UCI Machine Learning Repository \cite{murphy} in which the correct answer is not known. The goal of the experiments were to gain insight into how factors such as the size of a consistent decision tree are related to the error rate on classifying unseen test instances. Decision tree learners, as well as most other learners, attempt to produce the smallest consistent hypothesis.\footnote{We say ``attempt to produce the smallest consistent hypothesis'' because most systems use some form of limited look-ahead or greedy search. As a result, the smallest consistent tree is rarely found.} Occam's razor is often used to justify this bias. Here, we experimentally evaluate this bias towards simplicity by investigating the relationship between the size of a consistent decision tree and its accuracy. If the average error of decision trees with $N$ test nodes is less than the average error of decision trees of size $N+i$ (for $i>0$), an appropriate bias for a learner attempting to minimize average error would be to return the smallest decision tree it can find within its resource constraints. In this paper, we restrict our attention to decision trees that are consistent with the training data and ignore issues such as pruning which trade off consistency with the training data and the simplicity of the hypothesis. For the purposes of this paper, a consistent decision tree is one that correctly classifies every training example.\footnote{The artificial and natural problems we study here have consistent training sets.} We also place two additional constraints on decision trees. First, no discriminator can pass all instances down a single branch. This insures that the test made by the decision tree partitions the training data. Second, if all of the training instances at a node are of the same class, no additional discriminations are made. In this case, a leaf is formed with class label specified by the class of the instances at the leaf. These two constraints are added to insure that the decision trees analyzed in the experiments correspond to those that could be formed by top down decision tree induction algorithms. In this paper, we will not investigate problems that have continuous-valued features or missing feature values. In Section 2 (and the appendix), we will report on some initial exploratory experiments in which the smallest consistent decision trees tend to be less accurate than the average accuracy of those slightly larger. Section 3 provides results of additional experiments that address this issue. Section 4 addresses the implication of our findings to the policy a learner should take in deciding which of the many consistent hypotheses it should prefer. Section 5 relates this work to previous empirical and theoretical research. \section{Initial Experiments} We will investigate the relationship between various tree characteristics and error. In particular, we will look at node cardinality (i.e., the number of internal nodes in a tree) and leaf cardinality (i.e., the total number of leaves in a tree). It should be noted that even when using a powerful massively parallel computer, the choice of problems is severely constrained by the computational complexity of the task. The number of trees of any node cardinality that might be generated is $O(d^{c})$ where $d$ is the number of discriminators and $c$ is the node cardinality. Even on a massively parallel computer, this precluded the use of problems with many features or any continuous-valued features. The first experiment considered learning from training data in which there are 5 boolean features. The concept learned was $XYZ \vee AB$. This concept was chosen because it was of moderate complexity, requiring a decision tree with at least 8 nodes to represent correctly. With 5 boolean features, the smallest concept (e.g., True) would require 0 test nodes and the largest (e.g., parity) would require 31. We ran 100 trials, creating a training set by randomly choosing without replacement 20 of the 32 possible training examples and using the remaining 12 examples as the test set. For each trial, every consistent decision tree was created, and we computed the average error rate made by trees with the same node cardinality. Figure 1 plots the mean and 95\% confidence interval of these average errors as a function of the node cardinality. Figure 1 also plots the number of trials on which at least one decision tree of a given node cardinality is consistent with the training data. \vspace*{0.3cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/figure1.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 1. The average error of 100 trials as a function of node cardinality and the number of trials for each node cardinality.\\ \parindent 0.6cm \parskip 0.0cm From node cardinality 7 to node cardinality 16, there is a monotonic increase in error with increasing node cardinality. For the range from 2 to 3 nodes, the error is varied; however there is little evidence for these error values because they are based on only 2 and 1 trials, respectively. For the range of node cardinalities between 4 and 7, average error is definitely not a monotonically increasing function of node cardinality. As seen in the curve, 5 node trees are on the average more accurate than 4 node trees, and 7 node trees are on the average more accurate than trees with 6 nodes. This last result is somewhat surprising since one gets the impression from reading the machine learning literature \cite{muggleton92} that the smaller hypothesis (i.e., the one that provides the most compression of the data \cite{rissanen78}) is likely to be more accurate. We will explore this issue in further detail in Section 3. Appendix 1 presents data showing that this result is not unique to this particular concept. A final, interesting finding that we will not explore further in this paper is that for very large node cardinalities, error begins to decrease as the node cardinality increases. Table 1 lists the average number of consistent trees for each node cardinality and the average number of correct trees (i.e., those trees consistent with the training data that make no errors on the unseen test examples). There are no correct trees with fewer than 8 nodes, since at least 8 nodes are required to represent this concept. Clearly, since there are many trees consistent with the training data, a learner needs some policy to decide which tree to return. We will return to this issue in Section 4. \vspace{0.7cm} \hspace{3.3cm} \begin{tabular}{||c|c|c||} \hline {\it Nodes} & {\it Number of} & {\it Number of}\\ & {\it Consistent Trees} & {\it Correct Trees}\\ \hline 2 & 2.0 & 0.0 \\ \hline 3 & 4.0 & 0.0 \\ \hline 4 & 3.3 & 0.0 \\ \hline 5 & 12.3 & 0.0 \\ \hline 6 & 27.6 & 0.0 \\ \hline 7 & 117.1 & 0.0 \\ \hline 8 & 377.0 & 17.8 \\ \hline 9 & 879.4 & 37.8 \\ \hline 10 & 1799.9 & 50.2 \\ \hline 11 & 3097.8 & 41.6 \\ \hline 12 & 4383.0 & 95.4 \\ \hline 13 & 5068.9 & 66.6 \\ \hline 14 & 4828.3 & 37.7 \\ \hline 15 & 3631.5 & 31.3 \\ \hline 16 & 1910.6 & 14.8 \\ \hline 17 & 854.4 & 4.0 \\ \hline 18 & 308.6 & 3.6 \\ \hline 19 & 113.8 & 0.0 \\ \hline \end{tabular}\\ \vspace{0.4cm} \parindent 0.0cm Table 1. The average number of trees consistent with 20 training examples of the $XYZ \vee AB$ concept.\\ \parindent 0.6cm \vspace*{-0.5cm} \section{Further Experimentation} For most of the problems studied, we found that on average, the smallest decision trees consistent with the training data had more error on unseen examples than slightly larger trees. We ran additional experiments to make sure that this result is not an artifact of the experimental methodology that we used, as reported in the next sections. \subsection{Representative Train/Test Partitions} One possible explanation for the finding of the previous section is that the smaller decision trees are formed from unrepresentative samples. For example, there are 11 positive and 21 negative examples of the concept $XYZ \vee AB$. If all or most of the examples in the training set are negative, a very small tree may be learned which would probably do very poorly on the mostly positive test set. To insure that the results are not caused by unrepresentative training sets, we eliminated all training data that was not reasonably representative. In particular, since there is a $\frac{11}{32}$ probability that a training instance is positive, a representative training set of size 20 would have about 7 positive instances. Since one standard deviation would be $\sqrt{20*\frac{11}{32}*(1-\frac{11}{32})}$, we eliminated from analysis those training sets with greater than 8 or fewer than 5 positive instances. Similarly, there is a 0.5 probability that each binary feature takes on a true value, so we eliminated from analysis any training data which has any feature that is true in greater than 13 or fewer than 7 instances. Figure 2 is based on the 69 of 100 trials of the $XYZ \vee AB$ concept that met this representative test. Notice that the two trials that formed the only 2 and 3 node trees were removed. Even when only the more representative training sets are considered, the average error of trees of size 4 is greater than the average error of size 5 trees. \vspace*{0.3cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/figure5.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 2. Error rate of consistent trees from representative training sets as a function of node cardinality.\\ \parindent 0.6cm \parskip 0.0cm By regrouping the results of 100 trials for the $XYZ \vee AB$ concept so that trials with the same minimum-sized trees are grouped together, a set of five curves, each associated with a subgroup, was formed (Figure 3). The intent of the grouping is to allow us to determine whether the minimum-sized trees for any given trial are on average more accurate than larger trees. \vspace*{0.3cm} \hspace{0.0cm} \centerline{\psfig{figure=eps/dnf10-offset.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 3. Error as a function of node cardinality for the $XYZ \vee AB$ concept when first grouped by minimum-sized trees built.\\ \parindent 0.6cm \parskip 0.0cm Note that in Figure 3, for most minimum tree sizes, error is not a monotonically increasing function of node cardinality. Furthermore, the average error of the smallest trees found is not the most accurate when the smallest tree has 4 or 6 nodes. In addition, regardless of the size of the smallest tree found, the average accuracy of trees of size 8 (the size of the smallest correct tree) rarely has the minimum average error. Another interesting finding becomes apparent with this way of viewing the data: the average error rates of trees for training sets that allow creation of smaller consistent trees tends to be higher than for those training sets that can only form larger trees. For example, the error rate for those training sets whose minimum-sized trees have 4 nodes is higher than the error rate on trials whose minimum-sized trees has 7 nodes. \vspace*{0.3cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/figure-last.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 4. Error rate of consistent trees with 2 examples per leaf of some correct 8 node tree as a function of node cardinality.\\ \parindent 0.6cm \parskip 0.0cm The definition of representative that we used earlier in this section used global characteristics of the training data to determine representativeness. Here, we consider a more detailed view of representativeness that takes the structure of the correct concept into account. It is unreasonable to expect a decision tree learner to learn an accurate concept if there are no examples that correspond to some of the leaves of some correct decision tree. To generate training data for the next experiment, we first randomly selected one of the 72 trees with 8 nodes that is consistent with all the data. Next, for each leaf of the tree, we randomly selected two examples (if possible) to include in the training set. If a leaf only had one example, that example was included in the training set. Finally, we randomly selected from the remaining examples so that there were 20 training examples and 12 test examples. We had anticipated that with representative training sets formed in this manner, very small consistent trees would be rare and perhaps the error rate would monotonically increase with node cardinality. However, the results of 100 trials, as displayed in Figure 4, indicate the same general pattern as before. In particular, the average error of trees with 7 nodes is substantially less than the average error of those with 6 nodes. Another experiment with one randomly selected example per leaf had similar results. \subsection{Training Set Size and Concept Complexity} The minimum-sized decision tree for the concept $XYZ \vee AB$ has 8 tests and 9 leaves. Since the correct tree does not provide much compression\footnote{The exact amount of compression provided depends upon the particular scheme chosen for encoding the training data. See \cite{quinlan89,wallace93} for two such schemes.} of a set of 20 examples used to induce the tree, one might argue that the sample used was too small for this complex a concept. Therefore, we increased the number of training examples to the maximum possible. Figure 5 plots the average error of 32 trials in which we formed all decision trees consistent with 31 examples. Each tree was evaluated on the remaining unseen example. Figure 5 shows that the smaller trees formed from samples of size 31 have more error than the slightly larger trees. Since the minimum correct decision tree has 8 nodes and the consistent trees classify all 31 training examples correctly, any decision tree with fewer than 8 nodes classifies the test example incorrectly. \vspace*{0.3cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/figure6.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 5. Error rate of consistent trees with leave-one-out testing as a function of node cardinality.\\ \parindent 0.6cm \parskip 0.0cm To refute further the hypothesis that the results obtained so far were based on using too small a training set for a given concept complexity, we considered two less complex concepts. In particular, we investigated a single attribute discrimination, $A$ with four irrelevant features (Figure 6) and a simple conjunction, $AB$ with three irrelevant features (Figure 7). \hspace{0.6cm} \centerline{\psfig{figure=eps/dnf1.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 6. Error as a function of node cardinality for the single attribute discrimination $A$ concept.\\ \parindent 0.6cm \hspace{0.6cm} \centerline{\psfig{figure=eps/dnf2.eps,rheight=5.5cm,height=20.0cm}} \vspace*{0.2cm} \parindent 0.0cm Figure 7. Error as a function of node cardinality for the simple conjunction $AB$ concept.\\ \parindent 0.6cm \parskip 0.0cm For each concept, 100 trials were run in which 20 examples were used for training and the remaining 12 for testing. For these simpler concepts, though the smallest trees are the most accurate, error again is not a monotonically increasing function of node cardinality. \subsection{Training and Testing using the Same Probability Distribution.} In our previous experiments, we used a methodology that is typical in empirical evaluations of machine learning systems: the training data and the test data are disjoint. In contrast, most theoretical work on the PAC model \cite{valiant84} assumes that the training and test data are generated from the same probability distribution over the examples. For this section, we ran an experiment in which training and test examples were selected with replacement from the same distribution to ensure that our results were not dependent on a particular experimental methodology. \vspace*{0.0cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/dnf10b.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 8. Error as a function of node cardinality when the training and test examples are generated by the same distribution for the $XYZ \vee AB$ concept.\\ \parindent 0.6cm \parskip 0.0cm Once again, the target concept was $XYZ \vee AB$. By randomly choosing 31 training examples with replacement from the set of 32 possible instances, on average approximately 20 distinct training examples are selected. Error is estimated by randomly choosing 1000 examples with replacement from the set of possible instances. Figure 8 graphs the mean error (averaged over 100 trials) as a function of node cardinality. This testing methodology produces much smaller values for the proportion of test examples misclassified than the disjoint training and test set methodology because those test examples which also were training examples are always classified correctly. However, the same basic pattern of results is observed. Error is not at a minimum for the smallest decision trees nor at decision trees with 8 nodes (the minimum-sized correct tree). Error monotonically increases starting at trees with 7 nodes and then begins to decrease again for very large node cardinalities. Note that on some trials, it is possible to build decision trees with up to 21 nodes since some training sets contained 22 distinct examples. \subsection{Average Path Length} The information gain metric of ID3 is intended to minimize the number of tests required to classify an example. Figure 9 reanalyzes the data from Figure 1 by graphing average error as a function of average path length for the $XYZ \vee AB$ concept. \vspace*{0.3cm} \hspace{0.95cm} \centerline{\psfig{figure=eps/dnf10-apl.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm \begin{center} Figure 9. Error as a function of average path length for the $XYZ \vee AB$ concept.\\ \end{center} \parindent 0.6cm \parskip 0.0cm The results are similar to those obtained when relating the number of test nodes to the error rate: error is not a monotonically increasing function of average path length. Similar analyses were performed and similar results have been obtained for other concepts which are presented in the Appendix. \section{The Minimum-Sized Decision Tree Policy} A designer of a learning algorithm either explicitly or implicitly must decide which hypothesis to prefer when multiple hypotheses are consistent with the training data. As Table 1 shows, there can be many consistent decision trees. Should the learner always prefer the smallest consistent decision tree? A learner that adopts this strategy can be said to be following the minimum-sized decision tree policy. \newpage In this section, we present results from additional experiments to evaluate this policy. In particular, we gather evidence to address two related questions: \begin{itemize} \item Given any two consistent decision trees with different node cardinalities, what is the probability that the smaller decision tree is more accurate? \item Given the minimum-sized decision tree and a larger consistent decision tree, what is the probability that the smallest decision tree is more accurate? \end{itemize} The first question is of more interest to the current practice of decision tree induction since, for efficiency reasons, no algorithm attempts to find the smallest consistent decision tree for large data sets. Nonetheless, most algorithms are biased toward favoring trees with fewer nodes. \vspace*{0.3cm} \hspace{1.0cm} \centerline{\psfig{figure=eps/diff-any-size-probs.eps,rheight=5.5cm,height=20.0cm}} \hspace{1.1cm} \centerline{\psfig{figure=eps/diff-any-size-trials.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 10. The probability that the accuracy of a smaller decision tree is greater than, equal to, or less than the accuracy of a larger tree as a function of the difference of node cardinalities for the $XYZ \vee AB$ concept (upper). The number of trials out of 1000 on which at least 2 trees had a given difference in node cardinality (lower).\\ \parindent 0.6cm \parskip 0.0cm To address the question of whether a learner should prefer the smaller of two randomly selected consistent trees, we ran 1000 trials of learning the concept $XYZ \vee AB$ from 20 training examples. For each trial, we recorded the node cardinality and accuracy (on the 12 test examples) of every consistent tree. For each pair of consistent trees (with different node cardinalities), we computed the difference in node cardinality and indicated whether the accuracy of the smaller tree was greater than, equal to, or less than the accuracy of the larger tree. From this data, we computed the observed probability that one decision tree was more accurate than another as a function of the difference in node cardinalities (see Figure 10 upper). The graph shows that on this concept, the probability that the smaller of two randomly chosen consistent decision trees will be more accurate is greater than the probability that the larger tree will be more accurate. Furthermore, the probability that the smaller tree is more accurate increases as the difference in node cardinality increases. An exception to this trend occurs for very large differences in node cardinality. However, as Figure 10 lower shows, these exceptions are quite rare. Consistent decision trees whose node cardinalities differed by 16 were found in only 6 of the 1000 trials.\footnote{Four trials had minimum-sized trees with 2 nodes and maximally sized trees with 18 nodes. Two trials had minimum-sized trees with 3 nodes and maximally sized trees with 19 nodes.} The results of this experiment indicate that on average, a learner that prefers the smaller of two randomly selected decision trees has a higher probability of being more accurate on this concept than a learner that selects the larger tree. \vspace*{0.3cm} \hspace{1.2cm} \centerline{\psfig{figure=eps/diff-min-ungrouped.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 11. The probability that the accuracy of a minimum-sized decision is greater than, equal to, or less than the accuracy of a larger tree as a function of the difference of node cardinalities for the $XYZ \vee AB$ concept.\\ \parindent 0.6cm \parskip 0.0cm To address the question of whether a learner should prefer the smallest consistent decision over a randomly selected consistent tree with more test nodes, we reanalyzed the data from the previous experiment. Figure 11 graphs the observed probability that a consistent decision tree with the minimum node cardinality is more accurate than a larger tree as a function of the difference in node cardinalities between the two trees. The graph shows that a learner that chooses randomly among the consistent decision trees with minimum node cardinalities is more likely to find a tree that is more accurate than a learner that randomly selects among larger trees.\footnote{Except for the rare case when an extremely small and an extremely large decision trees is found on the same trial.} Figure 11 clearly shows that for this particular concept, preferring the minimum-sized decision tree policy is on average a better policy than preferring a decision tree that is any fixed size larger than the smallest decision tree. However, it is not clear that the minimum-sized decision tree is the best possible policy for this concept. Indeed, by looking at the data from Figure 3, it is apparent that a better strategy for this concept would be to find the minimum-sized tree and then decide whether to return the minimum-sized tree or a tree of a different node cardinality as a function of the node cardinality of the minimum-sized consistent tree. Table 2 shows which node cardinality has the highest probability of being most accurate as a function of the minimally sized tree, together with the number of trials (out of 1000) on which the minimum-sized tree had a particular node cardinality. \vspace{0.7cm} \hspace{2.4cm} \begin{tabular}{||c|c|c||} \hline {\it Minimum} & {\it Preferred} & {\it Number of}\\ {\it Node Cardinality}& {\it Node Cardinality} & {\it Trials}\\ \hline 2 & 2 & 49 \\ \hline 3 & 5 & 17 \\ \hline 4 & 5 & 300 \\ \hline 5 & 5 & 351 \\ \hline 6 & 8 & 211 \\ \hline 7 & 8 & 71 \\ \hline 8 & 8 & 1 \\ \hline \end{tabular}\\ \vspace{0.4cm} \parindent 0.0cm Table 2. A policy of returning a larger decision tree as a function of the minimum-sized tree for the $XYZ \vee AB$ concept.\\ \parindent 0.6cm Figure 11 provides some of the data that illustrates that the policy in Table 2 will perform better than preferring the minimum-sized decision tree on this concept. Figure 12 graphs the observed probability that a consistent decision tree with a minimum node cardinality of 5 (upper), 6 (middle), or 7 (lower) is more accurate than a larger tree as a function of the difference in node cardinalities between the two trees. The graph shows that when the minimum-sized decision tree has 5 nodes, the probability that a larger tree is more accurate is less than the probability that the smaller tree is more accurate for all node cardinalities. This is particularly interesting because it shows that giving a decision tree learner the size of the correct tree and having the decision tree learner produce an hypothesis of this size is not the best strategy for this concept. However, when the smallest consistent tree has 6 nodes, there is a 0.560 probability that a randomly chosen tree with 8 nodes will be more accurate and a 0.208 probability that a tree with 8 test nodes will have the same accuracy. In addition, when the minimum-sized tree has 7 test nodes, the probability that a tree with 8 nodes is more accurate is 0.345 while the probability that it is less accurate is 0.312. Note that we do not believe that the policy in Table 2 is uniformly superior to preferring the minimum-sized decision tree. Rather, there is probably some interaction between the complexity of the concept to be learned, the number of training examples, and the size of the smallest consistent decision tree. Furthermore, a learner should not be tuned to learn a particular concept, but should perform well on a variety of concepts. Clearly, if extremely simple concepts are to be learned sufficiently frequently, the minimum-sized decision tree policy will be better than the policy in Table 2. Indeed, the minimum-sized decision tree policy would work well on the simple concepts $A$ and $AB$ discussed in Section 3.2. However, if simple concepts are rarely encountered, there may be better policies. The best policy must depend upon the distribution of concepts that are encountered. Clearly, if the only concept \vspace*{0.3cm} \hspace{1.2cm} \centerline{\psfig{figure=eps/5.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.1cm} \hspace{1.8cm} \centerline{\psfig{figure=eps/6.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.1cm} \hspace{1.8cm} \centerline{\psfig{figure=eps/7.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm Figure 12. The probability that the accuracy of a minimum-sized decision tree is greater than, equal to, or less than the accuracy of a larger tree as a function of the difference of node cardinalities for the $XYZ \vee AB$ concept when the minimum-sized decision tree has 5 (upper), 6 (middle), or 7 (lower) test nodes.\\ \parindent 0.6cm \parskip 0.0cm \noindent to be learned is $XYZ \vee AB$, the best policy would be to ignore the training data and return the decision tree representation for $XYZ \vee AB$. It may be that Occam's razor should be viewed as a philosophical statement about the distribution of concepts one is likely to encounter. Occam's razor has not been shown to be a guarantee that when learning a complex concept, the simplest hypothesis consistent with the data is likely to be more accurate than the randomly-chosen more complex hypothesis consistent with the training data. \section{Analysis} \citeB{schaffer92,schaffer93} presents a series of experiments on overfitting avoidance algorithms. Overfitting avoidance algorithms prefer simpler decision trees over more complex ones, even though the simpler decision trees are less accurate on the training data, in hopes that the trees will be more accurate on the test data. Schaffer shows that these overfitting avoidance algorithms are a form of bias. Rather than uniformly improving performance, the overfitting avoidance algorithms improve performance on some distributions of concepts and worsen performance on other distributions of concepts. The results of our experiments go a step further than Schaffer's. We have shown that for some concepts, the preference for simpler decision trees does not result in an increase in predictive accuracy on unseen test data, even when the simple trees are consistent with the training data. Like Schaffer, we do not dispute the theoretical results on Occam's razor \cite{blumer87}, minimum description length \cite{quinlan89,muggleton92}, or minimizing the number of leaves of a decision tree \cite{fayyad90}. Rather, we point out that for a variety of reasons, the assumptions behind these theoretical results mean that the results do not apply to the experiments reported here. For example, \shortcite{blumer87} indicates that if one finds an hypothesis in a sufficiently small hypothesis space (and simpler hypotheses are one example of a small hypothesis space) and this hypothesis is consistent with a sufficiently large sample of training data, one can be fairly confident that it will be fairly accurate on unseen data drawn from the same distribution of examples. However, it does not say that on average this hypothesis will be more accurate than other consistent hypotheses not in this small hypothesis space. The \cite{fayyad90} paper explicitly states that the results on minimizing the number of leaves of decision trees are worst case results and should not be used to make absolute statements concerning improvements in performances. Nonetheless, informal arguments in the paper state: ``This may then serve as a basis for provably establishing that one method for inducing decision trees is better than another by proving that one algorithm always produces a tree with a smaller number of leaves, given the same training data.'' Furthermore, other informal arguments imply that this result is probabilistic because of the existence of ``pathological training sets.'' However, as we have shown in Figures 2 and 4 (as well as a reanalysis of the mux6 data in the Appendix), eliminating pathological (i.e., unrepresentative) training sets does not change the qualitative result that on some concepts, the smaller trees are less accurate predictors than slightly larger trees. \section{Conclusion} We have reported on a series of experiments in which we generated all decision trees on a variety of artificial concepts and two naturally occurring data sets. We found that for many of the concepts, the consistent decision trees that had a smaller number of nodes were less accurate on unseen data than the slightly larger ones. These results do not contradict existing theoretical results. Rather, they serve to remind us to be cautious when informally using the intuitions derived >from theoretical results on problems that are not covered by the theorems or when using intuitions derived from worst-case results to predict average-case performance. We stress that our results are purely experimental. Like the reader, we too would be pleased if there were theoretical results that indicated, for a given sample of training data, which decision tree is likely to be most accurate. However, it is not clear whether this can be done without knowledge of the distribution of concepts one is likely to encounter \cite{schaffer94}. We also note that our results may be due to the small size of the training sets relative to the size of the correct tree. We tried to rule out this possibility by using larger training sets (31 of the 32 possible examples) and by testing simpler concepts. For the simpler concepts, the smallest decision trees were the most accurate, but error did not monotonically increase with node cardinality. Since most decision tree learners that greedily build decision trees do not return the smallest decision tree, our results may be of practical interest even for simple concepts. In the future, experiments with more features and more examples could help to answer this question, but considerably more complex problems cannot be handled even by future generations of parallel supercomputers. In addition, we note that in our experiments, we did not build decision trees in which a test did not partition the training data. This explains why we found relatively few extremely large decision trees and may explain why very large trees made few errors. To our knowledge, all decision tree algorithms have this constraint. However, the theoretical work on learning does not make use of this information. We could rerun all of our experiments without this constraint, but we would prefer that some future theoretical work take this constraint into account. Although we have found situations in which the smallest consistent decision tree is not on average the most accurate and cases in which there is a greater than 0.5 probability that a larger decision tree is more accurate than the smallest, we believe that learning algorithms (and people) with no relevant knowledge of the concept and no information about the distribution of concepts that are likely to be encountered should prefer simpler hypotheses. This bias is appropriate for learning simple concepts. For more complex concepts, the opposite bias, preferring the more complex hypotheses, is unlikely to produce an accurate hypothesis \shortcite{blumer87} and \cite{fayyad90} due to the large number of consistent complex hypotheses. We believe that the only way to learn complex hypotheses reliably is to have some bias (e.g., prior domain knowledge) which favors particular complex hypotheses such as combinations of existing hypotheses learned inductively as in OCCAM \cite{pazzani90}. Indeed, \cite{valiant84} advocates a similar position: ``If the class of learnable concepts is as severely limited as suggested by our results, then it would follow that the only way of teaching more complex concepts is to build them up from simpler ones.'' \acks{We thank Ross Quinlan, Geoffrey Hinton, Michael Cameron-Jones, Cullen Schaffer, Dennis Kibler, Steve Hampson, Jason Catlett, Haym Hirsh, Anselm Blumer, Steve Minton, Michael Kearns, Tom Dietterich, Pat Langley, and David Schulenburg for commenting on various aspects of this research. The research reported here was supported in part by NSF infrastructure grant number MIP-9205737, NSF Grant INT-9201842, AFOSR grant F49620-92-J-0430, and AFOSR AASERT grant F49620-93-1-0569.} \appendix \section*{Appendix A. Experiments on Additional Problems} In this appendix, we provide data on experiments which we ran on additional problems. The experiments show that the basic findings in this paper are not unique to the artificial concept, $XYZ \vee AB$. \subsection*{Mux6} The multiplexor concept we consider, mux6, has a total of 8 binary features. Six features represent the functionality of a multiplexor and 2 features are irrelevant. The minimum sized tree has 7 nodes. This particular concept was chosen because it is difficult for a top-down inductive decision tree learner with limited look ahead to find a small hypothesis \cite{quinlan93}. On each trial, we selected 20 examples randomly and tested on the remaining examples. Since most of the computational cost of building consistent trees is for larger node cardinalities and we are primarily interested in trees with small node cardinalities, we only computed consistent trees with up to 10 nodes for 10 trials and up to 8 nodes for 340 \vspace*{0.3cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/figure2.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm \begin{center} Figure 13. Error as a function of node cardinality for the mux6 concept.\\ \end{center} \parindent 0.6cm \parskip 0.0cm \noindent trials. Figure 13 presents the average error as a function of the node cardinality for these trials. This graph again shows that average error does not monotonically increase with node cardinality. Trees of 4 nodes are on the average 4\% less accurate than trees of 5 nodes. \subsection*{Lenses} The lenses domain has one 3-valued and three binary features, three classes, and 24 instances. Since the lenses domain has one non-binary feature, trees with a range of leaf cardinalities are possible for a particular node cardinality. The minimum-sized tree has 6 nodes and 9 leaves. Separate analyses for leaf and node cardinalities were performed. We used training set sizes of 8, 12, and 18 for this domain, built all consistent trees, and measured the error rate on all unseen examples. \vspace*{0.3cm} \hspace{2.5cm} \centerline{\hbox{ \psfig{figure=eps/figure3a.eps,rheight=5.5cm,rwidth=7.0cm,height=20.0cm} \psfig{figure=eps/figure3b.eps,rheight=5.5cm,height=20.0cm}}} \vspace{0.2cm} \parindent 0.0cm Figure 14. Error as a function of node cardinality (left) and error as a function of leaf cardinality (right).\\ \parindent 0.6cm \parskip 0.0cm Figure 14 (left) shows the error as a function of the node cardinality for the 3 training set sizes averaged over 50 trials. These curves indicate that the smallest consistent trees are not always the most accurate. When observing the larger node cardinalities for the training set sizes 12 and 18, error monotonically decreases with increasing node cardinality. Similar statements can be said for the curve in Figure 14 (right), which relates average error as a function of leaf cardinality. \subsection*{Shuttle Landing} The shuttle landing domain has four binary and two 4-valued features, two classes, and 277 instances. The minimum-sized consistent tree has 7 nodes and 14 leaves. We used training sets of size 20, 50, and 100 for the shuttle domain, generating all consistent decision trees with fewer than 8, 10, and 12 nodes, and measured the error of these trees on all unseen examples. Figure 15 presents the error as a function of leaf cardinality, averaged over 10 trials. For this domain, there is a monotonically increasing relationship between node cardinality and error. \vspace*{0.3cm} \hspace{0.6cm} \centerline{\psfig{figure=eps/figure4.eps,rheight=5.5cm,height=20.0cm}} \vspace{0.2cm} \parindent 0.0cm \begin{center} Figure 15. Error as a function of node cardinality for the Shuttle concept.\\ \end{center} \parindent 0.6cm \parskip 0.0cm \bibliography{explore} \bibliographystyle{theapa} \end{document}