FOIL

FOIL(target-predicate, predicates, examples)
  pos = those examples for which target-predicate is true
  teg = those examples for which target-predicate is false
  learnedRules = {}
  while pos do
    ;learn a new rule
    newRule = the rule that predicts target-predicate with no preconditions
    newRuleNeg = neg
    while newRuleNeg do
      ;add a new literal to specialize newRule
      candidateLiterals = candidate new literals for newRule based on predicates
      bestLiteral = $\argmax_{l \in \text{candidateLiterals}}$ Foil-gain(l, newRule)
      add bestLiteral to preconditions of newRule
      newRuleNeg = subset of newRuleNeg that satisfies newRuleNeg preconditions
    learnedRules = learnedRules + newRule
    pos = pos - {member of pos covered by newRule}
  return learnedRules

• Its a natural extension of Sequential-Covering and Learn-One-Rule.
• Each iteration of the outer loop adds a new rule to its disjunctive hypothesis Learned-rules (specific-to-general).
• In the inner loop we add conjunctions that form the preconditions of the rule (general-to-specific hill-climbing).