An Analysis of Reduced Error Pruning
  Top-down induction of decision trees has been observed to suffer from the
inadequate functioning of the pruning phase. In particular, it is known that
the size of the resulting tree grows linearly with the sample size, even though
the accuracy of the tree does not improve. Reduced Error Pruning is an
algorithm that has been used as a representative technique in attempts to
explain the problems of decision tree learning. In this paper we present
analyses of Reduced Error Pruning in three different settings. First we study
the basic algorithmic properties of the method, properties that hold
independent of the input decision tree and pruning examples. Then we examine a
situation that intuitively should lead to the subtree under consideration to be
replaced by a leaf node, one in which the class label and attribute values of
the pruning examples are independent of each other. This analysis is conducted
under two different assumptions. The general analysis shows that the pruning
probability of a node fitting pure noise is bounded by a function that
decreases exponentially as the size of the tree grows. In a specific analysis
we assume that the examples are distributed uniformly to the tree. This
assumption lets us approximate the number of subtrees that are pruned because
they do not receive any pruning examples. This paper clarifies the different
variants of the Reduced Error Pruning algorithm, brings new insight to its
algorithmic properties, analyses the algorithm with less imposed assumptions
than before, and includes the previously overlooked empty subtrees to the
analysis.
