Suppose R1 is covered by 350 positive examples and 150 negative ex- amples, while R2 is covered by 300 positive examples and 50 negative examples. Compute the FOIL’s information gain for the rule R2 with respect to R1.

The RIPPER algorithm (by Cohen [1]) is an extension of an earlier algorithm


called IREP (by F ?urnkranz and Widmer [3]). Both algorithms apply the


reduced-error pruning method to determine whether a rule needs to be


pruned. The reduced error pruning method uses a validation set to estimate


the generalization error of a classifier. Consider the following pair of rules:





R2 is obtained by adding a new conjunct, B, to the left-hand side of R1. For


this question, you will be asked to determine whether R2 is preferred over


R1 from the perspectives of rule-growing and rule-pruning. To determine


whether a rule should be pruned, IREP computes the following measure:





where P is the total number of positive examples in the validation set, N is


the total number of negative exampl

For this problem, p0 = 350, n0 = 150, p1 = 300, and n1 = 50. There-

fore, the FOIL’s information gain for R2 with respect to R1 is: