Occam's Razor Just Got Sharper

1 Introduction

Occam's razor, attributed to the 14th-century English logician William of Ockham, is the principle that, given two hypotheses consistent with the observed data, the simpler one should be preferred. This principle has become the basis for many induction algorithms that search for a small hypothesis within the version space [Mitchell, 1982]. Several studies attempted to justify Occam's razor with theoretical and empirical arguments [Blumer et al., 1987; Quinlan and Rivest, 1989; Fayyad and Irani, 1990]. But a number of recent works have questioned the utility of Occam's razor, and provided theoretical and experimental evidence against it.

Schaffer [1994] proved that no learning bias can outperform another bias over the space of all possible learning tasks. This looks like theoretical evidence against Occam's razor. Rao et al. [1995], however, argued against the applicability of this result to real-world problems by questioning the validity of its basic assumption about the uniform distribution of possible learning tasks.

Domingos [1999] argued that the disagreement about the utility of Occam's razor stems from the two different interpretations given to it: the first is that simplicity is a goal in and of itself, and the second is that simplicity leads to better accuracy. While accepting the first interpretation, Domingos questioned the second one.

Webb [1996] presented C4.5X, an extension to C4.5 that uses similarity considerations to further specialize consistent leaves. Webb reported an empirical evaluation which shows that C4.5X has a slight advantage in a few domains and argued that these results discredit Occam's thesis.

Murphy and Pazzani [1994] reported a set of experiments in which all possible consistent trees were produced and their accuracy was tested. Their findings were inconclusive. They found cases where larger trees had, on average, better accuracy. Still, they recommend using Occam's principle when no additional information about the concept is available. The major limitation of their work is the exhaustive enumeration of the version space. Such an approach is only applicable to domains with very few features.

In this work we present an alternative approach that performs statistical testing of Occam's thesis on a sample of the version space. This approach allows us to use highdimensional domains and complex concepts. One problem with random sampling of the version space is the rarity of small trees in the sample. We therefore use, in addition to random sampling, biased sampling methods based on modern anytime induction algorithms [Esmeir and Markovitch, 2004]. These methods produce samples with much higher concentrations of small trees.

The major contribution of this work is to provide convincing empirical evidence for Occam's razor in the context of classification trees. Furthermore, the various sampling techniques we applied help to better understand the space of consistent decision trees and how top-down induction methods explore it. Note that this empirical demonstration of the utility of Occam's principle does not pretend to provide a philosophical proof for Occam's thesis.

2 Occam's Empirical Principle

In the context of machine learning, the widely accepted interpretation of Occam's razor is that given two consistent hypotheses, the simpler one is likely to have a lower error rate. Fayyad and Irani [1990] have formally defined this notion: for two decision trees T1 and T2 and a fixed ϵ, 0 < ϵ < 1, T1 is likely to have a lower error rate than T2 if Pr {P (T1, ϵ) < P (T2, ϵ)} > 0.5, where P (T, ϵ) is the probability that T has an error rate greater than ϵ.

Fayyad and Irani [1990] also provided theoretical support for favoring smaller trees. They showed that under a set of assumptions, given two trees T1 and T2 consistent with the observed data, T1 is likely to have a lower error rate than T2 if T1 has fewer leaves. Berkman and Sandholm [1995], however, have questioned this set of assumptions and argued that the opposite conclusion can be drawn from it.

The main challenge we face in this work is to empirically test the validity of Occam's razor in decision tree induction. We therefore define the Occam's empirical principle:

Definition 1 Let Etrain and Etest be a training and a testing set respectively. Let H be a set of hypotheses consistent with Etrain. We say that H satisfies Occam's empirical principle with respect to Etrain and Etest if, for any h1, h2 drawn from H × H,

where |h| is the size of hypothesis h and 0 ≤ Acc(h, E) ≤ 1 is the accuracy of h on a test set E.

3 Sampling the Version Space

Given a learning problem, we would like to produce all the possible trees consistent with the observations and test whether their size and accuracy are correlated. Such an exhaustive enumeration, however, is not practical for most realworld domains. Therefore, in what follows we propose sampling as an alternative. First we define the population, i.e., the space of decision trees we sample from, and then we describe 3 different sampling techniques, each of which focuses on a different part of the sampled space.

3.1 Defining the Version Space

Given a set of attributes A, the hypothesis class we deal with is the set of decision trees over A, denoted by DTA. Let E be a set of examples. Because Occam's razor is applicable only to hypotheses that can explain the observations, we limit our discussion to the version space-the set of all trees consistent with E, denoted by DTA(E). Furthermore, since most decision tree learners build a tree top-down, we focus on a subset of the consistent trees-the trees obtainable by top-down induction, denoted by TDIDTA(E). Under the TDIDT scheme, the set of examples is partitioned into subsets by testing the value of an attribute and then each subset is used to recursively build a subtree. The recursion stops when all the examples have the same class label. Figure 1 formalizes the basic procedure for top-down induction.

While TDIDTA(E) is a strict subset of DTA(E), we claim that the trees in DTA(E) that are not in TDIDTA(E) are not interesting for the purpose of model learning. There are two types of trees in DTA(E) -TDIDTA(E):

1. A tree containing a subtree with all leaves marked with the same class. Obviously, such a subtree could have been replaced by a single node marked with the class.
2. A tree with an internal node that has no associated examples from E. The subtree rooted at this node is not supported by training examples and is therefore not interesting for induction.

Note that including the above trees could unjustly distort the results. In the first case, larger trees that are logically equivalent will be included, arbitrarily weakening the negative correlation. In the second case, the extra branches are not supported by any training example. Thus, their leaves must be labeled randomly, lowering the accuracy and hence arbitrarily strengthening the negative correlation.

While we restrict the definition of Occam's empirical principle to consistent hypotheses, in our experiments we also examine its applicability to pruned TDIDTA(E) trees. This allows us to draw conclusions for noisy datasets as well.

3.2 Sampling Techniques

Our goal is to sample the TDIDTA(E) space in order to test Occam's empirical principle. Our first proposed sampling technique uses TDIDT with a random selection of the splitting attribute (and cutting point, where the attribute is numeric). We refer to this method as the Random Tree Generator (RTG). Observe that although it has no bias with respect to generalization quality, RTG does not uniformly sample TDIDTA(E). For example, if the concept was a1 and the attributes were {a1, a2, a3}, the probability of constructing the smallest tree (with a single split) is much higher than that of constructing a specific large tree. We will later show that the non-uniform sampling should not affect the validity of our conclusions.

One problem with random sampling is the rarity of small trees. Many induction methods, however, are likely to concentrate on small trees. Theoretically, the correlation could have been statistically significant when sampling the TDIDT space but not when sampling a subspace consisting of small trees. To test this hypothesis we need a sample of small trees. Such a sample could be obtained by repeatedly invoking RTG and keeping the smaller trees. Nevertheless, the number of RTG invocations needed to obatin a reasonable number of small trees is prohibitively high. Another alternative is to use ID3. Repeated invocations of ID3, however, result in similar trees that can vary only due to different tie-breaking decisions. Esmeir and Markovitch [2004] introduced SID3, a stochastic version of ID3 that is designed

Procedure SID3-CHOOSE-ATTRIBUTE(E, A) Foreach a ∈ A p (a) ← gain-1(E, a) If ∃a such that entropy-1(E, a) = 0 a∗ ← Choose attribute at random from {a ∈ A | entropy-1(E, a) = 0} Else a∗ ← Choose attribute at random from A; for each attribute a, the probability of selecting it is proportional to p (a) Return a∗

Procedure LSID3-CHOOSE-ATTRIBUTE(E, A, r) If r = 0 Return ID3-CHOOSE-ATTRIBUTE(E, A) Foreach a ∈ A Foreach vi ∈ domain(a) Ei ← {e ∈ E | a(e) = vi} mini ← ∞ Repeat r times T ← SID3(Ei, A - {a}) mini ← min (mini, |T |) totala ← ∑|domain(a)| i=1 mini Return a for which totala is minimal

to sample the version space semi-randomly, with a bias to smaller trees. In SID3, instead of choosing an attribute that maximizes the information gain, we choose the splitting attribute semi-randomly. The likelihood that an attribute will be chosen is proportional to its information gain. 1 However, if there are attributes that decrease the entropy to zero, then one of them is picked randomly. The attribute selection procedure of SID3 is listed in Figure 2.

For many hard learning tasks such as parity concepts, ID3's greedy heuristic fails to correctly estimate the usefulness of the attributes and can mislead the learner to produce relatively large trees. In such cases, SID3 can, in theory, produce significantly smaller trees. The probability for this, however, is low and decreases as the number of attributes increases. To overcome this problem, we use a third sampling technique that is based on the recently introduced LSID3 algorithm for anytime induction of decision trees [Esmeir and Markovitch, 2004]. LSID3 adopts the general TDIDT scheme, and invests more time resources for making better split decisions. For every candidate split, LSID3 attempts to estimate the size of the resulting subtree were the split to take place, and favors the one with the smallest expected size. The estimation is based on a biased sample of the space of trees rooted at the evaluated attribute. The sample is obtained using SID3. LSID3 is parameterized by r, the sample size. When r is greater, the sample is larger and the resulting estimate is expected to be more accurate. Therefore, LSID3 is expected to improve with the increase in r. Figure 3 lists the procedure for attribute selection as applied by LSID3. Because our goal is to sample small trees and not to always obtain the smallest tree, we use LSID3(r = 1) as a sampler. Observe that LSID3 is stochastic by nature, and therefore we do not need to randomize its decisions.

1 SID3 ensures that attributes with gain of zero will have a positive probability to be selected.

4 Experimental Results

We tested Occam's empirical principle, as stated in Definition 1, on 20 datasets, 18 of which were chosen arbitrarily from the UCI repository [Blake and Merz, 1998], and 2 which are artificial datasets that represent hard concepts: XOR-5 with 5 additional irrelevant attributes, and 20-bit Multiplexer. Each dataset was partitioned into 10 subsets that were used to create 10 learning problems. Each problem consisted of one subset serving as a testing set and the union of the remaining 9 as a training set, as in 10-fold cross validation. We sampled the version space, TDIDTA(E), for each training set E using the three methods described in Section 3 and tested the correlation between the size of a tree (number of leaves) and its accuracy on the associated testing set. The size of the sample was ten thousand for RTG and SID3, and one thousand for LSID3 (due to its higher costs). We first present and discuss the results for consistent trees and then we address the problemof pruned, inconsistent trees.

4.1 Consistent Decision Trees

Figure 4 plots size-frequency curves for the trees obtained by each sampling method for three datasets: Nursery, Glass, and Multiplexer-20 (for one fold out of the 10). Each of the three methods focuses on a different subspace of TDIDTA(E), with the biased sampling methods producing samples consisting of smaller trees. In all cases we see a bell-shaped curve, indicating that the distribution is close to normal. Recall that RTG does not uniformly sample TDIDTA(E): a specific small tree has a better chance of being built than a specific large tree. The histograms indicate, however, that the frequency of small trees in the sample is similar to that of large trees (symmetry). This can be explained by the fact that there are more large trees than small trees. To further verify this, we compared the distribution of the tree size in an RTG sample to that of all trees, as reported in [Murphy and Pazzani, 1994] (Mux-11 dataset). The size-frequency curves for the full space and the sampled space were found to be similar.

Occam's empirical principle states that there is a negative correlation between the size of a tree and its accuracy. To test the significance of the correlation, we used the nonparametric Spearman correlation test on each of the samples. 2 Spearman's coefficient ρ measures the monotonic association of two variables, without making any assumptions about their frequency distribution. For a paired sample of X and Y , ρ is defined as 1 - 6 ∑ di/(n(n2 - 1)), where di is the difference in the statistical rank of xi and yi. There is a special correction for this formula in the presence of ties.

Table 4.1 lists summarizing statistics for the RTG, SID3, and LSID3 samplers. The validity of Occam's empirical principle, tested by Spearman's method, is listed in the rightmost column. For each sampling method, for each dataset, we count how many times, out of the 10 folds, the null hypothesis H0 (which states that the variables are not correlated) can be rejected at an α = 5% significance level, against the alternative hypothesis that the correlation is negative.

2 All statistics were computed using the The R Project package [R Development Core Team, 2005].

The results indicate that when random sampling (RTG) in used, Occam's empirical principle, as measured by Spearman's test, is valid for almost all problems, except for Scale. The results for the SID3 sampling method indicate that even when focusing on smaller trees, simplicity is beneficial as a bias for accuracy. Again, except for the Scale dataset, there is a strong inverse correlation between size and accuracy. The numbers indicate that the correlation is weaker than the RTG case, yet still significant across most domains.

The LSID3 samples focus on very small trees. In several cases, LSID3 could reach the smallest tree possible. Again the negative correlation was found to be significant for most domains. 3 However, the number of cases where the null hypothesis could not be rejected is higher than in the previous samplers. One possible reason for this phenomenon is that LSID3 samples trees from a much tighter size-range. Hence, there is an increased probability for finding two trees, T 1 and T2, with the size and accuracy of T1 being greater than T2.

3 Note that in some cases, significance tests could not be computed due to the large number of ties (indicated by NA in the table).

As indicated by the frequency curves, the different sampling methods cover different portions of the space, but sometimes overlap. An interesting question is whether the conclusions hold if we analyze all samples together. Note that it is not statistically valid to merge the samples of RTG, SID3, and LSID3 due to their different distributions. Nevertheless, we measured the correlation statistics for the combined samples and found that the results are very similar, with a strong negative correlation between the size of a tree and its accuracy.

To illustrate the correlation between the size of a tree and its accuracy, we grouped the trees from a single run into bins, according to their size, and calculated the average accuracy for each bin. We did this for each of the sampling methods. Bins with less than 5 observations were discarded. Figure 5 plots the results for the Nursery, Glass, and Multiplexer-20 datasets. The error bars represent confidence intervals, with α = 5%.

Again, the graphs show a strong correlation between size and accuracy, confirming Occam's empirical principle. For the Nursery and Multiplexer-20 datasets the correlation is strong for all 3 samplers. For Glass, the correlation is weaker when the trees are very small. These graphs, which represent each size range in its own bin, indicate that the positive support we showed for Occam's principle is not a result of a size bias in our sampling methods.

4.2 Pruned Decision Trees

Formally, Occam's empirical principle, as defined in Section 2, is applicable only to consistent hypotheses. Most decision tree learners, however, do not necessarily produce consistent models because they output a pruned tree in attempt to avoid overfitting the data. This is usually done in two phases: first a tree is grown top-down and then it is pruned. In our second set of experiments, we examine whether taking simplicity as a bias in the first stage is beneficial even when the tree is later pruned. Therefore, we measure the correlation between the size of unpruned trees and their accuracy after pruning.

Table 4.2 summarizes the results. The same statistics were measured with a single change: the accuracy was measured after applying error-based pruning [Quinlan, 1993]. As in the case of consistent trees, examining the overall correlation between the size of a tree and its accuracy indicates that for most datasets the inverse correlation is statistically significant.

Table 4.2 also gives the percentages of pruned leaves. While the trees produced by RTG were aggressively pruned, the percentage of pruned leaves in LSID3 was relatively low. This is due to the stronger support for the decisions made at the leaves of smaller consistent trees.

5 Conclusions

Occam's razor states that given two consistent hypotheses, the simpler one should be preferred. This principle has been the subject for a heated debate, with theoretical and empirical arguments both for and against it. In this work we provided convincing empirical evidence for the validity of Occam's principle with respect to decision trees. We state Occam's empirical principle, which is well-defined for any learning problem consisting of a training set and a testing set, and show experimentally that the principle is valid for many known learning problems. Note that our study is purely empirical and does not attempt to reach an indisputable conclusion about Occam's razor as an epistemological concept.

Our testing methodology uses various sampling techniques to sample the version space and applies Spearman's correlation test to measure the monotonic association between the size of a tree and its accuracy. Our experiments confirm Occam's empirical principle and show that the negative correlation between size and accuracy is strong. Although there were several exceptions, we conclude that in general, simpler trees are likely to be more accurate. Observe that our results do not contradict those reported by Murphy and Pazzani [1994], but complement them: we do not claim that a smaller tree is always more accurate, but show that for many domains smaller trees are likely to be more accurate.

We view our results as strong empirical evidence for the utility of Occam's razor to decision tree induction. It is important to note that the datasets used in our study do not necessarily represent all possible learning problems. However, these datasets are frequently used in machine learning research and considered typical tasks for induction algorithms.

We also examined the applicability of Occam's razor to pruned trees. For most domains we found the correlation between the size of a tree before pruning and its accuracy after pruning to be statistically significant. These results indicate that taking Occam's razor as a preference bias when growing a tree is useful even if the tree is post-pruned.

An interesting research direction that we plan to pursue is to test the correlation between a tree's accuracy and a variety of other measures, such as expected error and description length.

Acknowledgments

This work was partially supported by funding from the ECsponsored MUSCLE Network of Excellence (FP6-507752).