The high level control of Kearns and Mansour's (1998) pruning algorithm is the same bottom-up sweep as in REP . However, the pruning criterion in their method is a kind of a cost-complexity condition (Breiman et al., 1984) that takes both the observed classification error and (sub)tree complexity into account. Moreover, their pruning scheme does not require the pruning set to be separate from the training set. Both Mansour's (1997) and Kearns and Mansour's (1998) algorithms are pessimistic : they try to bound the true error of a (sub)tree by its training error.  Since the training error is by nature optimistic, the pruning criterion has to compensate it by being pessimistic about the error approximation.

Consider yet another variant of REP , one which is otherwise similar to the one analyzed above, with the exception that the original leaves are not put to a special status, but can be relabeled by the majority of the pruning examples just like internal nodes. This version of REP produces the optimal pruning with respect to which the performance of Kearns and Mansour's (1998) algorithm is measured. Their pessimistic pruning produces a decision tree that is smaller than that produced by REP.

Kearns and Mansour (1998) are able to prove that their algorithm has a strong performance guarantee.  The generalization error of the produced pruning is bounded by that of the best pruning of the given tree plus a complexity penalty. The pruning decisions are local in the same sense as those of REP and only the basic pruning operation of replacing a subtree with a leaf is used in this pruning algorithm.

## 8. Conclusion

In this paper the REP algorithm has been analyzed in three different settings. First, we studied the algorithmic properties of REP alone, without assuming anything about the input decision tree nor pruning set. In this setting it is possible to prove that REP fulfills its intended task and produces an optimal pruning of the given tree. The algorithm proceeds to prune the nodes of a branch as long as both subtrees of an internal node are pruned and stops immediately if even one subtree is kept. Moreover, it prunes an interior node only if al its descendants at level d have been pruned. Furthermore, REP either halts before the safe nodes are reached or prunes the whole tree only in case all safe nodes have the same majority class.

In the second setting the tree under consideration was assumed to fit noise; i.e., it was assumed that the class label of the pruning examples is independent of their attribute values. In this setting the pruning probability of the tree could be bound by an equation that depends exponentially on the size of the tree and linearly on the number and class distribution of the pruning examples. Thus, our analysis corroborates the main finding of Oates and Jensen (1999) that REP fails to control the growth of a decision tree in the extreme case that the tree fits pure noise. Moreover, our analysis opened a possibility to initially explain why the learned decision tree grows linearly with an increasing data set. Our bound on the pruning probability of a tree is based on bounding the probability that all safe nodes have the same majority class. Surprisingly, essentially the same property, whose probability we try to bound close to 0, is assumed to hold with probability 1 in the analysis of Oates and Jensen (1999).

In REP it may happen that no pruning examples are directed to a given subtree. Such subtrees have not been taken into account in earlier analyses. In our final analysis we