where Si is the set of those examples that are directed to safe node zi ;

$$S_{i}=\big\{\,h\in\big\{\,1,\ldots,n\,\big\}\,\big|\,\,w_{h}=i\,\big\}.$$

Hence, Q = f ( W 1 , . . , W n ). Moving any one example from one safe node to another (anging the value of any one argument w i ), can change one more safe node z i to fulfill the condition | Si | ≤ r, one less safe node to fulfill it, or both at the same time. Thus, the value of f changes by at most 1. Hence, the function fulfills the Lipschitz condition. Therefore, we can apply McDiarmid's inequality to it by substituting c; = 1 and observing that then L = 1 c 2 = n :

$\Pr\{|f(W_{1},\ldots,W_{n})-\mbox{E}\,f(W_{1},\ldots,W_{n})|\geq\lambda\,\}\leq2\,e^{-2\,\lambda^{2}/n}$.  

## Or Equally

$$\operatorname*{Pr}\left\{\,|Q-\mathbf{E}Q|\geq\,\lambda\,\right\}\leq2\,e^{-2\,\lambda^{2}/n}\,.$$

Unfortunately, this concentration bound is not very tight. Nevertheless, combining the concentration bounds for Q and R we have for P the following deviation from its expected value.

Since | P = EP | = | Q = R = E(Q = R)| = | Q = EQ + ER = R | ≤ | Q = EQ | + | R = ER | ,
|Q - R - E(Q - R)| ≥ λ implies that |Q - EQ| ≥ λ/2 or | R - ER| ≥ λ/2. Thus,

$$\Pr\left\{\left|P-\mathbb{E}P\right|\geq\lambda\right\}=\Pr\left\{\left|Q-R-\mathbb{E}\left(Q-R\right)\right|\geq\lambda\right\}$$ $$\leq\Pr\left\{\left|Q-\mathbb{E}Q\right|\geq\frac{\lambda}{2}\right\}+\Pr\left\{\left|R-\mathbb{E}R\right|\geq\frac{\lambda}{2}\right\}$$ $$\leq2\exp\left(-\frac{\lambda^{2}}{2n}\right)+2\exp\left(-\frac{\lambda^{2}(k-1/2)}{4(k^{2}-\mathbb{E}^{2}R)}\right).$$

## 7. Related Work

Traditional pruning algorithms —like cost-complexity pruning (Breiman et al., 1984), pessimistic pruning (Quinlan, 1987), minimum error pruning (Niblett & Bratko, 1986; Cestnik & Bratko, 1991), critical value pruning (Mingers, 1989a), and error-based pruning (Quinlan, 1993) - have already been covered extensively in earlier work (Mingers, 1989a; Esposito et al., 1997; Frank, 2000). Thus we will not touch on these methods any further. Instead, we review some of the more recent work on pruning.

REP produces an optimal pruning of the given decision tree with respect to the pruning set. Other approaches for producing optimal prunings have also been presented (Breiman et al., 1984; Bohanec & Bratko, 1994; Oliver & Hand, 1995; Almuallim, 1996). However, often optimality is measured over the training set. Then it is only possible to maintain the initial accuracy, assuming that no noise is present. Neither is it usually possible to reduce the size of the decision tree without sacrificing the classification accuracy. For example, in the work of Bohanec and Bratko (1994) it was studied how to efficiently find the optimal pruning in the sense that the output decision tree is the smallest pruning which satisfies a given accuracy requirement. A somewhat improved algorithm for the same problem was presented subsequently by Almuallim (1996).