consistently with their earlier considerations, that even though the probability of pruning a node that fits noise prior to pruning beneath it is close to 1, pruning that occurs beneath the node reduces its pruning probability close to 0. In particular, this model shows that if even one descendant of node N at depth d is not pruned, then N will not be pruned (assuming there are no leaves until depth d +1). The consequence of this result is that increasing depth d leads to an exponential decrease of the node's pruning probability.

The first part of Oates and Jensen's (1999) analysis is easy to comprehend, but its significance is uncertain, because this situation does not rise in any bottom-up pruning strategy. The statistical model is based on the assumption that the number, n, of pruning instances that pass through the node under consideration is large, in which case - independence assumptions prevailing - the errors committed by the node can be approximated by the normal distribution. The expected error of the original tree is the mean of the distribution, while, if pruned to a leaf, the tree would misclassify a proportion of the n examples that corresponds to that of the minority class. Oates and Jensen show that the latter number is always less than the mean of the standard distribution of errors. Hence, the probability of pruning is over 0.5 and approaches 1 as n grows.

In the second part of the analysis, in considering the pruning probability of a node N
after pruning has taken place beneath it, Oates and Jensen assume that the proportion of positive examples in any descendant of N at depth d is the same as in N . In this setting, assuming further that N has a positive majority, all its descendants at level d also have a positive majority. It directly follows that if all descendants at level d are pruned, they are all replaced by a positive leaf.  Hence, the function represented by this pruning is identically positive. The majority leaf that would replace N also represents the same function and is smaller than the above pruning. Therefore, REP will choose the single leaf pruning. On the other hand, if one or more of the descendants of N at depth d are not pruned, then the pruning of the tree rooted at N , in which these subtrees are maintained and all other nodes at level d are pruned into positive leaves, is more accurate than the majority leaf. In this case the tree will not be pruned.

Oates and Jensen (1999) also assume that starting from any node at level d the probability of routing an example to a positive leaf is the same. In the following analyses we try to rid all unnecessary assumptions; the same results can be obtained without any knowledge of the example distribution.

## 4. Basic Properties Of Rep

Before going to the detailed probabilistic analysis of the REP algorithm, we examine some of its basic algorithmic properties. Throughout this paper we review the binary case for simplicity. The results, however, also apply with many-valued attributes and several classes.

Now that the processing control of the REP algorithm has been settled, we can actually prove Quinlan's (1987) claim of the optimality of the pruning produced by REP. Observe that the following result holds true independent of the leaf labeling strategy.

Theorem 1 Applying REP with a set of pruning examples, S, to a decision tree T produces T ′ - a pruning of T - such that it is the smallest of those prunings of T that have minimal error with respect to the example set S