EVC (extreme value correction) is a method that corrects optimistic estimates in search algorithms. We applied it to the rule induction, as one of main problems in rule induction is that the state-of-the-art rule evaluation measures do not take searching into account. This problem has been addressed by several authors (see [1] and [2]).

Perhaps the easiest to illustrate the problem will be with an experiment on artificial data set (see [3] for more ellaborate description of experiments and results).

We induced several rules using m-estimate of probability as evaluation measure. As data is artificial we knew for each rule the correct probability (x axis) and estimated (y axis), therefore we would like to have dots in the above graphs put on the diagonal axis. As you can see relative frequency is completly optimistic - the algorithm will always find a 100% pure rule, although that is not true for the whole population. Using higher settings of m does improve the slope, however not completly and, eventually, all estimates will become pesimistic.

The following graph shows results of EVC corrected relative frequency on the same data set. As you can see, the result is much better than with plain m-estimate.

EVC induction of rules is implemented within Argumentation module in Orange. You can get the newevest version from Orange CVS (get Argumentation module) or here (usually a bit old). (installation: put it in Argumentation folder within Orange and run setup.py in Argumentation/Widgets directory.

See example python file EVCcn2-sample.py for an example how this module can be used.**1. Best Rule **

**2. Minimax **

**3. Logit and Logit_simplify **

According to the nomogram, the most important rule is IF capital-gain > 6849 THEN class=">50", even though it is not the best rule according to quality (on the right image, rules are sorted according to quality). As you can see, the best rule according to quality is only at the fourth place in the nomogram, therefore the quality of rule itself does not necessary imply that the rule is the most important for classification in a nomogram.

**4. Alternative learners **

[1] David D. Jensen and Paul R. Cohen. Multiple comparisons in induction algorithms. Machine Learning, 38(3):309–338, March 2000.

[2] Quinlan, J. R. and Cameron-Jones, R. M. Oversearching and layered search in empirical learning. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, pages 1019--1024, Montreal, Canada, August 1995.

[3] Martin Mozina, Janez Demsar, Jure Zabkar, Ivan Bratko. Why is Rule Learning Optimistic and How to Correct It. European Conference on Machine Learning (2006). Download

[4] Martin Mozina, Jure Zabkar, Ivan Bratko. Implementation of and experiments with ABML and MLBA. ASPIC deliverable D3.4. Download