First-Order Inductive Learner (FOIL) Algorithm

Jump to: navigation, search

A First-Order Inductive Learner (FOIL) Algorithm is an rule-based learning algorithm that can learn Horn clauses and that uses a top-down greedy search based on a sequential covering algorithm (directed by an information gain heuristic).



  • (Wikipedia, 2021) ⇒ Retrieved:2021-4-4.
    • In machine learning, first-order inductive learner (FOIL) is a rule-based learning algorithm.
    • Developed in 1990 by Ross Quinlan,J.R. Quinlan. Learning Logical Definitions from Relations. Machine Learning, Volume 5, Number 3, 1990. [1] FOIL learns function-free Horn clauses, a subset of first-order predicate calculus. Given positive and negative examples of some concept and a set of background-knowledge predicates, FOIL inductively generates a logical concept definition or rule for the concept. The induced rule must not involve any constants (color(X,red) becomes color(X,Y), red(Y)) or function symbols, but may allow negated predicates; recursive concepts are also learnable.

      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.