Process-Oriented Estimation of Generalization Error

Pedro M. DomingosIJCAI 1999

Abstract

This paper introduces Process-Oriented Evaluation (POE), a novel framework for estimating a model's generalization error by accounting for the intensity of the search process used to find it. By treating the "amount of search" as a factor in model uncertainty, the authors derive a simple formula that helps learners avoid overfitting. This approach results in significantly simpler models (smaller "theory sizes") without sacrificing predictive accuracy, offering a robust alternative to traditional data-oriented or representation-oriented methods.

Introduction

Overfitting remains a fundamental challenge in machine learning, where a model fits training data perfectly but fails to generalize to unseen data. Traditional mitigation strategies generally fall into two categories:

  1. Data-oriented methods: Techniques like cross-validation split data into training and validation sets. While effective, they are computationally expensive and reduce the amount of data available for training.
  2. Representation-oriented methods: Principles like Minimum Description Length (MDL) or Occam’s Razor penalize complex models. However, these assume that simplicity is inherently superior, which is not always the case.

Pedro Domingos argues that both approaches overlook a critical variable: the search process. If a learner tests a vast number of random models, it is statistically likely to find one that fits the data by chance. Current methods often ignore the "failed" candidates discarded during search. POE bridges this gap by making the expected error a function of the search intensity.

Methods

The core contribution of this work is a mathematical derivation for the expected true error rate ($E$) of a chosen hypothesis based on the search effort.

The POE Formula

The paper derives a closed-form approximation for the expected error: $$E[\epsilon_m | n, e_m] = \frac{\epsilon_m^{ML} + (m-1)\epsilon_m^{Prior}}{m}$$ In this formula, $\epsilon_m^{ML}$ represents the training error (Maximum Likelihood), $\epsilon_m^{Prior}$ is the prior expected error, and $m$ is the number of hypotheses searched. As $m$ increases, the formula shifts weight from the observed training error toward the prior error (the error expected by chance). This encourages skepticism toward low training errors found after extensive searching.

Effective Search and Application

In practical algorithms like beam search, candidate models are often dependent. To account for this, the author proposes using an "effective" number of hypotheses, $m' = \log(m)$. This framework was integrated into CN2, a classic rule-induction algorithm, where it serves as a stopping criterion for adding conditions to rules.

Key Results

The POE framework was evaluated using 11 benchmark datasets from the UCI Repository, including Breast Cancer, Heart Disease, and Thyroid datasets. The performance of the new POE variant (CN2-POE2) was compared against the original CN2 and a previous iteration (CN2-POE1).

Comparison of Error Rate and Theory Size across various datasets for CN2 and POE variants.

As shown in the table above, the primary findings include:

  • Accuracy Maintenance: CN2-POE2 maintained predictive accuracy comparable to the original CN2, with an average error rate only 0.2% higher. This indicates that the pruning process successfully removed noise without discarding valuable logic.
  • Model Simplicity: There was a significant reduction in "theory size" (the total number of conditions in the rules). On average, POE-based models were substantially more concise. For instance, in the "Breast" dataset, the theory size was reduced from 114.5 to 104.9.
  • Computational Efficiency: The simplified algebraic expression in CN2-POE2 is much faster to compute than the complex integrals required by earlier versions of POE.

Discussion and Conclusion

The POE framework suggests that search is not "free"; every additional model tested increases the risk of finding a "fluke." This perspective moves beyond the philosophical debate of Occam's Razor, viewing simplicity not as a rule, but as a byproduct of limited search.

While successful in rule induction, several avenues for future work remain. The current derivation assumes hypothesis independence, necessitating the $m' = \log m$ heuristic. Future research will focus on determining the "effective $m$" for different learners and testing the framework's universality on neural networks and genetic algorithms. Additionally, the statistical properties of the exact formula for smaller sample sizes warrant further investigation.

Summary updated

BibTeX
@inproceedings{domingos1999process,
  author = {Pedro M. Domingos},
  title = {{Process-Oriented Estimation of Generalization Error}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}

Loading related content...

Figure