Theorem 2 An internal node, whi h prior to pruning had no leaves as its hildren, wil l not be pruned by rep if it has a non-trivial subtree when the bottom-up pruning sweep rea hes it.

Proof For an internal node N we have two possible ases in whi h it has non-trivial subtrees; either both its subtrees are non-trivial (non-leaf ) or one of them is trivial. Let us review these ases.

Let rT denote the error of (sub)tree T with respe
t to the part of the pruning set that rea hes the root of T . By rL we denote the mis
lassi
ation rate of the ma jority leaf L that would repla e T , if T was hosen to be pruned.

Case I: Let the two subtrees of T , T0 and T1, be non-trivial. Hen
e, both of them have been

retained when the pruning sweep has passed them. Thus, rT0 < rL0 and rT1 < rL1

,

where L0 and L1 are the ma jority leaves that would repla
e T0 and T1, respe
tively, if pruned. Be ause rT = rT0 + rT1

, it must be that rT < rL0 + rL1

.

If T0 and T1 have the same the ma jority 
lass, then it is also the ma jority 
lass of T .

Then rL = rL0 + rL1

, where L is the ma jority leaf orresponding to T . Otherwise, rL  rL0 + rL1

. In any ase, rL  rL0 + rL1

. Combining this with the fa t that rT < rL0 + rL1 means that rT < rL. Hen
e, T is not pruned.

Case II: Let T have one trivial subtree, whi h was produ ed by pruning, and one nontrivial subtree. We assume, without loss of generality, that T0 is non-trivial and L1 is a ma jority leaf whi h has repla ed T1 in the pruning pro
ess. Then, rT0 < rL0

. Hen e, we have that rT = rT0 + rL1 < rL0 + rL1

.

In the same way as in the Case I, we an dedu e that rL  rL0 + rL1

. Therefore, rT < rL and T will be retained in the pruned tree.

T 
annot be pruned in either ase, and the pruning pro ess an be stopped on the bran h ontaining T unless an original leaf appears along the path from the root to T . 2 If node N has an original leaf, then it may be pruned even if the other subtree of N

is non-trivial. Also when N has two trivial subtrees, it may be pruned. Whether pruning takes pla e depends on the lass distribution of examples rea hing N and its subtrees.

In the analysis of Oates and Jensen (1999) it was shown that the prerequisite for pruning a node N from the tree is that all its des endants at depth d have been pruned. d is the depth just above the rst (original) leaf in the subtree rooted at N. If we apply the above result to this situation, we an orroborate their nding that N will not be pruned if one or more of its des endants at depth d are retained. Applying Theorem 2 re ursively gives the result.

Corollary 3 A tree T rooted at node N wil l be retained by rep if one or more of the des endants of N at depth d are not pruned.

To avoid the analysis being restri ted by the leaf globally losest to the root, we need to be able to onsider the set of leaves losest to the root on all bran hes of the tree. Let us dene that the fringe of a de ision tree ontains any node that prior to pruning had a leaf
