Occam's Razor Just Got Sharper

Saher Esmeir, Shaul MarkovitchIJCAI 2007

Introduction

In machine learning, Occam’s Razor is often invoked as a justification for preferring simpler models, assuming they will generalize better to unseen data. However, this principle has been the subject of intense debate. While researchers like Schaffer have argued that no single bias can outperform others across all possible tasks, empirical evidence for the "simpler is better" heuristic has remained inconclusive due to the sheer size of the "version space"—the set of all possible models consistent with a training set.

Previous studies were limited to tiny datasets because they attempted exhaustive enumeration. This paper addresses the gap by moving from enumeration to statistical sampling, allowing for robust testing of Occam’s Razor on complex, high-dimensional, real-world problems.

Methodology

The authors propose testing Occam’s Razor by sampling the version space ($TDIDT_A(E)$), which consists of all trees obtainable via top-down induction that are consistent with the training data. The core induction procedure is shown below:

The general TDIDT procedure used as the basis for the sampling algorithms.

To explore this space, three distinct sampling techniques were employed:

  1. Random Tree Generator (RTG): A baseline sampler that builds trees by selecting splitting attributes at random, providing a broad look at the version space.
  2. SID3 (Stochastic ID3): A sampler where the probability of choosing an attribute is proportional to its information gain, biasing the sample toward smaller trees.
  3. LSID3 (Lookahead Stochastic ID3): A computationally intensive sampler that estimates subtree sizes before splitting to find the most compressed trees possible.

Experimental Setup

The study evaluated 20 datasets, including 18 real-world datasets from the UCI Machine Learning Repository (e.g., Breast-W, Glass, Iris) and 2 artificial datasets (XOR-5 and 20-bit Multiplexer) designed to challenge greedy heuristics.

Results and Insights

The "Bell Curve" of Simplicity

When sampling the version space, the distribution of tree sizes follows a bell-shaped curve. Biased samplers like SID3 and LSID3 successfully shifted this curve toward the smaller end of the spectrum, as illustrated in the figure below.

Tree size distributions for different samplers, illustrating how biased methods shift the population toward simpler models across various domains.

Statistically Significant Correlation

Using the Spearman correlation coefficient ($\rho$), the authors found a strong negative correlation between tree size and accuracy in almost all 20 domains. In most cases, this correlation was statistically significant ($p = 0.95$) across all 10 folds of cross-validation. This trend held true even after pruning to handle noise; trees that were smaller before pruning generally remained more accurate after pruning.

Exceptions to the Rule

The "Scale" dataset was a notable outlier where a positive correlation was found (larger was better). This suggests that while Occam's Razor is a powerful general rule, it is not a universal law of nature. Additionally, the correlation was sometimes weaker in LSID3 samples due to the "tighter" range of sizes; when all trees are already very small, the marginal benefit of further compression is harder to measure.

Conclusion

This study provides strong empirical evidence that simplicity correlates with accuracy in common induction tasks. While it does not provide a mathematical proof that simplicity must lead to accuracy, it demonstrates that the preference for simplicity is a trend that holds across the entire space of valid models. Future work may explore other complexity measures, such as description length, and investigate why specific datasets like "Scale" defy the Razor.

Summary updated

BibTeX
@inproceedings{esmeir2007occam,
  author = {Saher Esmeir and Shaul Markovitch},
  title = {{Occam's Razor Just Got Sharper}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure