Developed in 1990 by Ross Quinlan,[1] FOIL learns function-free Horn clauses, a subset of first-order predicate calculus.
Like the ID3 algorithm, FOIL hill climbs using a metric based on information theory to construct a rule that covers the data.
Unlike ID3, however, FOIL uses a separate-and-conquer method rather than divide-and-conquer, focusing on creating one rule at a time and collecting uncovered examples for the next iteration of the algorithm.
[2] Several extensions of the FOIL theory have shown that additions to the basic algorithm may reduce this search space, sometimes drastically.
Additionally, typing can improve the accuracy of the resulting rule by eliminating from consideration impossible literals such as livesAt(A,B) which may nevertheless appear to have a high information gain.
Rather than implementing trivial predicates such as equals(X,X) or between(X,X,Y), FOCL introduces implicit constraints on variables, further reducing search space.
If a literal with the most information gain in an iteration of FOCL is non-operational, it is operationalized and its definition is added to the clause under construction.