be ause when the event yi = 1 has probability p, at the same time the event yi+1 = 0 has probability 1  p, and vi
e versa. Now the number of 
lass alternations is A = Pt1 i=1 Ai and its expe tation is

$${\bf E}A\,=\sum_{i\,=\,1}^{t-1}{\bf E}A_{i}\,=\sum_{i\,=\,1}^{t-1}2p(1-p)=2p(1-p)\sum_{i\,=\,1}^{t-1}1=2(t-1)p(1-p).\tag{3}$$

$$\mathbb{D}$$

Let T be a de ision tree that has been grown on the sample S. The growing has been ontinued until the training error is 0. Ea h leaf in T 
orresponds to a half open interval

[a; b) in [0; 1). If yi 6= yy+1, then xi and xi+1 must fall into dierent leaves of T , be
ause otherwise one or the other example is falsely lassied by T . Thus, the upper boundary b of the interval orresponding to the leaf into whi h xi falls in must have a value less than xi+1.

Repetitively applying this observation when s anning through the examples from left to right, we see that T must at least have one leaf for x1 and one leaf for ea
h 
lass alternation; i.e., A + 1 leaves in total. By using Equation 3 we see that the expe ted number of leaves in T is

$$\mathbf{E}A\,+\,1\,=\,2(t\,-\,1)p(1\,-\,p)\,+\,1.$$
In particular, this is linear in the size of the sample $\,S;\,|S|=t\,$. 
ular, this is linear in the size of the sample S; jSj = t. 2

The above theorem only on erns zero training error trees built in the rst phase of de ision tree indu tion. The empiri al observations of Catlett (1991) and Oates and Jensen

(1997, 1998), however, on ern de ision trees that have been pruned in the se ond phase of indu tion. We ome ba k to the topi of pruned trees shortly.

Consider how rep is used in pra ti e. There is some amount of (
lassied) data available from the appli ation domain. Let there be a total of t examples available. Some part  of the data is used for tree growing and the remaining portion 1   of it is reserved as the separate pruning set; 0 <  < 1. Quite a ommon pra ti e is to use two thirds of the data for growing and one third for pruning or nine tenths for growing and one tenth for pruning when (ten-fold) 
ross-validation is used. In the de ision tree onstru tion phase the tree is tted to the t examples as perfe tly as possible. If we hypothesize that the previous result holds for noisy real-world data sets, whi h by empiri al eviden e would appear to be the ase, and that the number of safe nodes also grows linearly with the number of leaves, then the tree grown will ontain 
t safe nodes, where  > 0. Sin
e the pruning set size also is a linear fra tion of the training set size, the ratio r = 2n=k stays 
onstant in this setting.

Hen e, by Equation 2, the growing data set size for es the pruning probability to zero, even quite fast, be ause the redu tion in the probability is exponential.

## 5.4 Limitations Of The Analysis

Empty subtrees, whi h do not re eive any pruning examples, were left without attention above; we assumed that ni > 0 for ea
h i. Empty subtrees, however, de
isively ae
t the analysis; they are automati ally pruned away. Unfortunately, one annot derive a non-trivial upper bound for the number of empty subtrees. In the worst ase all pruning examples are routed to the same safe node, whi h leaves k  1 empty safe nodes to the tree. Subsequently we review the ase where the examples are distributed uniformly to the safe nodes. Then better approximations an be obtained.

