included empty subtrees in the equation for a tree's pruning probability.  Taking empty subtrees into account gives a more realistic bound for the pruning probability of a tree.

Unfortunately, one cannot draw very definite general conclusions on the two-phased topdown induction of decision trees on the basis of analyses on the REP algorithm, because its bias is quite unique among pruning algorithms. The fact that REP does not penalize the size of a tree, but only rests on the classification error on the pruning examples makes the method sensitive to small changes in the class distribution of the pruning set.  Other decision tree pruning algorithms also have their individual aracteristics.  Therefore, unified analysis of decision tree pruning may be impossible.

The version of REP, in which one is allowed to relabel original leaves, as well, is used as the performance objective in Kearns and Mansour's (1998) pruning algorithm. Thus, the performance of pruning algorithms that use both error and size penalty is related to those that use only error estimation. In the version of REP used by Kearns and Mansour our analysis based on safe nodes applies with leaves in place of safe nodes. Hence for this algorithm the derived bounds are stricter.

We leave the detailed analysis of other important pruning algorithms as future work.

Only through such investigation is it possible to disclose the differences and similarities of pruning algorithms. Empirical examination has not managed to reveal clear performance differences between the methods. Also, the relationship of the number of safe nodes and leaves of a tree ought to be examined analytically and empirically. In particular, one should study whether the number of safe nodes does increase linearly with a growing training set, as conjectured in this paper.  Deeper understanding of existing pruning algorithms may help to overcome the problems associated with the pruning phase of decision tree learning.

## References

Almuallim, H. (1996). An efficient algorithm for optimal pruning of decision trees. Artificial Intelligence, 83, 347-362.

Bohanec, M., & Bratko, I. (1994). Trading accuracy for simplicity in decision trees. Machine Learning, 15 (3), 223–250.

Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984).  Classification and Regression Trees. Wadsworth, Pacific Grove, CA.

Breiman, L. (1996). Some properties of splitting criteria. Machine Learning, 24 (1), 41–47. Catlett, J. (1991). Overpruning large decision trees. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, pp. 764–769, San Mateo, CA. Morgan K aufmann .

Cestnik, B., & Bratko, I. (1991). On estimating probabilities in tree pruning. In Kodratoff, Y. (Ed.), Machine Learning—EWSL-91: Proceedings of the Fifth European Working Session, Vol. 482 of Lecture Notes in Artificial Intelligence, pp. 138-150, Berlin, Heidelberg, New York. Springer-Verlag.

Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23 (4), 493–507.