Current Slide

• Start with the most general rule possible: condition = empty
• Adding new attributes by adopting a greedy depth-first strategy
• Picks the one that most improves the rule quality
• Rule-Quality measures: consider both coverage and accuracy
• Foil-gain (in FOIL & RIPPER): assesses info_gain by extending condition

\[FOIL-Gain=pos{'} \times \left ( log_{2}\frac{pos'}{pos'+neg'}-log_{2}\frac{pos}{pos+neg} \right )\]

• favors rules that have high accuracy and cover many positive tuples
• Rule pruning based on an independent set of test tuples

\[FOIL-Prune(R)=\frac{pos-neg}{pos+neg} \right )\]

• Pos/neg are # of positive/negative tuples covered by R.
• If FOIL_Prune is higher for the pruned version of R, prune R