Proof To begin we show that the two conditions are necessary for the pruning of T. First, we show that if the former condition is not fulfilled, then T cannot be pruned into a single leaf. Second, we prove that neither will T be pruned if the former condition holds, but the latter not. Third, we show the sufficiency of the conditions; i.e., prove that if they both hold, then T will be pruned into a single leaf.

(i): Let us first assume that in T there is a safe node N such that it will not be pruned. By the definition of a safe node, the parent P of N originally had no leaves as its children. Therefore, by Theorem 2, P will not be pruned. It is easy to see, inductively, that nither will the root of T be pruned.

(ii): Let us then assume that all subtrees rooted at safe nodes get pruned and that there are one or more safe nodes in T into which more negative than positive pruning examples fall. Observe that all safe nodes cannot be such. Let us now consider the pruning of T
in which the leaves are situated in place of the safe nodes; the leaves receive the same examples as the original safe nodes. Because safe nodes are internal nodes, in REP
the corresponding pruned leaves are labeled by the majority of the pruning examples.

In particular, the safe nodes that receive more negative than positive examples are replaced by negative leaves. All other leaves are labeled positive. This pruning of the original tree is more accurate than the majority leaf. Hence, by Theorem 1, REP will not prune T into a single-leaf tree.

(iii): Let us now assume that all subtrees rooted at the safe nodes of T are pruned and that at least as many positive as negative pruning examples reach each safe node. Then all interior nodes must also have a majority of positive pruning examples. Otherwise, there is an interior node N in T that has more negative than positive examples. Thus, at least one of the children of N has a majority of negative examples. Carrying the induction all the way to the safe nodes shows that no such node N can exist in T . Hence, all interior prunings of T represent the same function (identically positive) and all of them have the same error with respect to S. The majority leaf is the unique, smallest of these prunings and will, by Theorem 1, be chosen.

口

## 5. A Probabilistic Analysis Of Rep

Let us now turn our attention to the question of what the prerequisites for pruning a decision tree T into a single majority leaf are.  Since, by Theorem 1, REP produces a pruning of T which is the most accurate with respect to the pruning set and such that it is as small as possible, to show that T does not reduce to a single leaf it suffices to find its pruning that has a better prediction accuracy on the pruning examples than the majority leaf has In the following the class of an example is assumed to be independent of its attribute values. Obviously, if in a decision tree there is a node where this assumption holds for the examples arriving to it, we would like the pruning algorithm to turn it into a majority leaf.

We do not make any assumptions about the decision tree. However, similar to the analysis of Oates and Jensen (1999), for the obtained bounds to be tight, the shortest path from the root of the tree to a leaf should not be too short.