Deconstructing the Digit Recognition Problem

Elsevier eBooksPublished 1 January 1992

Cullen Schaffer

Citations19

TL;DR

This paper analyzes the conditional value of overfitting avoidance and focuses on the effect of one highly-regarded pruning technique in variations of the well-known digit recognition problem.

Abstract

Decision tree pruning techniques and other forms of overfitting avoidance have often been considered statistical means of improving predictive accuracy. Intuitively, they are intended to determine the appropriate level of complexity for an induced model by distinguishing between signal and noise in training data, patterns that reflect the true underlying nature of data generation and those that arise by chance. In fact, however, overfitting avoidance methods simply encode preferences for certain classes of models. These preferences may increase accuracy when they bias induction in favor of predictive models, but they may just as well have the opposite effect if they bias induction away from predictive models. This paper analyzes the conditional value of overfitting avoidance and focuses on the effect of one highly-regarded pruning technique in variations of the well-known digit recognition problem.

Keywords

Computer Science

International Journal of Man-Machine StudiesSimplifying decision trees

2,502 Citations1987J. R. Quinlan

Techniques for simplifying decision trees while retaining their accuracy are discussed, described, illustrated, and compared on a test-bed of decision trees from a variety of domains.

Information and ComputationInferring decision trees using the minimum description lenght principle

665 Citations1989J. R. Quinlan, Ronald L. Rivest

The use of Rissanen's minimum description length principle for the construction of decision trees is explored and empirical results comparing this approach to other methods are given.

Machine LearningAn Empirical Comparison of Pruning Methods for Decision Tree Induction

631 Citations1989John Mingers

This paper compares five methods for pruning decision trees, developed from sets of examples, and shows that three methods—critical value, error complexity and reduced error—perform well, while the other two may cause problems.

View PDF

Machine LearningOverfitting Avoidance as Bias

228 Citations1993Cullen Schaffer

Overfitting avoidance strategies are not better or worse, but only more or less appropriate to specific application domains, suggesting that, as a research community, the authors are not making progress toward developing powerful, general methods for guarding against overfitting in inducing decision trees.

Machine LearningOverfitting avoidance as bias

163 Citations1993Cullen Schaffer

Overfitting avoidance strategies are not better or worse, but only more or less appropriate to specific application domains, which means that, as a research community, the authors are not making progress toward developing powerful, general methods for guarding against overfitting in inducing decision trees.

View PDF

Lecture notes in computer scienceOn estimating probabilities in tree pruning

158 Citations1991Bojan Cestnik, Ivan Bratko

The resulting pruning method improves on the original Niblett-Bratko pruning in the following respects: apriori probabilities can be incorporated into error estimation, several trees pruned to various degrees can be generated, and the degree of pruning is not affected by the number of classes.

Journal of the Operational Research SocietyExpert Systems—Rule Induction with Statistical Data

154 Citations1987John Mingers

Rule induction has been proposed as a way of speeding up the acquisition of knowledge for expert systems but can only deal with determinate data and extensions to deal with statistical data are explored.

Sparse data and the effect of overfitting avoidance in decision tree induction

25 Citations1992Cullen Schaffer

This paper identifies one important factor that affects the degree to which the bias of overfitting avoidance is appropriate--the abundance of training data relative to the complexity of the relationship to be induced--and shows empirically how it determines whether such methods as pessimistic and cross-validated cost-complexity pruning will increase or decrease predictive accuracy in decision tree induction.

Lecture notes in computer scienceWhen does overfitting decrease prediction accuracy in induced decision trees and rule sets?

24 Citations1991Cullen Schaffer

Through detailed analysis of a paradigmatic example, this work attempts to uncover conditions under which overfitting does not decrease predictive accuracy and hence in which it would be a mistake to apply simplification techniques, if predictive accuracy is the key goal.