LS (t,x). Then we define the heuristic "penalty" (proof omitted: it is a rough upperbound of Kearns & Mansour (1998), Lemma 1):

$$\begin{array}{r c l}{{\alpha_{(t,\vec{v})}^{\prime}}}&{{=}}&{{\sqrt{\frac{\left(\operatorname{Set}\left(\left(t,\vec{v}\right)\right)+2\right)\log\left(n\right)+\log1/\delta}{\left|L S_{(t,\vec{v})}\right|}\right.}\;.}}\end{array}$$

$$\left({8}\right)$$

Set((t, v)) denotes the maximum number of literals of all rules except (t, v) in the current DC, that an arbitrary example could satisfy.  The fast calculability of o ( t , r) is obtained at the expense of a greater risk of overpruning, whose effects on some small datasets were experimentally dramatic for the accuracy. In our experiments, which contain very small datasets, we have chosen to tune a parameter limiting the effects of this combinatorial upperbound. More precisely, We have chosen to uniformly resample LS into a larger subset of 5000 examples, when the initial LS contained less than 5000 examples. By this, we artificially increase [ LS ( t,g) ] and mimic for the small domains new domains with an identical larger size, with the additional benefits that reasonable comparisons may be made on pruning.

The value of Criterion((t,v)) is therefore "TRUE" iff E(t,v) + O'(t,v) ≥ EO.

## 6. Experiments

Following are three experimental sections, aimed at testing WIDC on three issues. The first presents extensive results on the tradeoff simplicity-accuracy obtained by W IDC, and compares the results with those obtained for state-of-the-art algorithms. The second goes on in depth analyzes for the mining/interpretability issue, and the third presents results on nis tolerance.

## 6.1 Tradeoff Simplicity-Accuracy

Experiments were carried out using three variants of WIDC: with optimistic pruning
(), with pessimistic pruning (p), and without pruning (0). Table 1 presents some results on various datasets, most of which were taken from the UCI repository of machine learning database (Blake et al., 1998). For each dataset, the eventual discretization of attributes was performed following previous recommendations and experimental setups (de Carvalho Gomes & Gascuel, 1994). The results were computed using a ten-fold stratified cross validation procedure (Quinlan, 1996). The least errors for WIDC are underlined for each domain. For the sake of comparisons, column "Others" points out various results for other algorithms, intended to help getting a general picture of what can be the performances of efficient approaches with different outputs (decision lists, trees, committees, etc.), in terms of errors (and, when applicable, sizes). Some of the most relevant results for WIDC are summarized in the scatterplots of Table 2.

The interpretation of Table 1 using only errors gives the advantage to WIDC with pessimistic pruning, all the more as WIDC(p) has the advantage of providing simpler formulas than WIDC(0), and has a mu simpler pruning stage than WIDC(0). Results also compare favorably to the "Other" results, building either DLs, DTs, or DCs. They are all the more interesting if we compare the errors in the light of the sizes obtained. For the "Echo" domain, WIDC with pessimistic pruning beats improved CN2 by two points,