First-Order Inductive Learner (FOIL) Algorithm

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).

• AKA: Quinlan's FOIL Algorithm.
• Context:
  • It was initially developed by Quinlan (1990).
  • It is the precursor to FOCL Algorithm.
  • It produces rules in first-order logic.
  • It can be implemented by a FOIL System to solve a FOIL Task.
  • It can discover patterns in the data expressed as First-Order Rules.
  • It can also be implemented as a Rule Induction Algorithm by a Rule Induction System.
  • …
• Example(s)
  • LUCS-KDD FOIL Algorithm,
  • Wikipedia Foil Algorithm Pseudocode.
  • …
• Counter-Example(s):
  • CN2 Algorithm,
  • FINDBESTRULE Algorithm,
  • FURIA Algorithm,
  • LEM-based Algorithms,
  • PROGOL Algorithm,
  • RIPPER Algorithm,
  • Rulearner Algorithm,
  • RULEX Algorithm.
• See: Inductive Logic Programming Algorithm, ID3 Algorithm, Sequential-Covering Alogrithm, Top-Down Learning, Pattern Mining Algorithm, Decision Tree Induction Algorithm, Inductive Logic Programming, If-Then Rule, Firs-Order Logic Rule.

---

---

References

2021

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/First-order_inductive_learner 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.

2004a

• (Melli, 2004) ⇒ Gabor Melli. (2004). “Scribe Notes on FOIL and Inverted Deduction.” In: Scribe Notes for the 2004 SFU course on Machine Learning (SFU CMPT-882 2004).

2004b

• (Coenen, 2004) ⇒ Frans Coenen (2004). Overview Of Foil Algorithm].
  • QUOTE: The FOIL algorithm (Quinlan and Cameron-Jones 1993) takes as input a (space separated) binary valued data set R and produces a set of CARs. The classifier, as generated by the LUCS-KDD FOIL algorithm described here, comprises a linked-list of rules ordered according to their Laplace accuracy (Clark and Boswell 1991).

1990

• (Quinlan, 1990) ⇒ J. Ross Quinlan. (1990). “Learning Logical Definitions from Examples.” In: Machine Learning, 5(3). doi:10.1007/BF00117105
  • QUOTE: This paper describes FOIL, a system that learns Horn clauses from data expressed as relations. FOIL is based on ideas that have proved effective in attribute-value learning systems, but extends them to a first-order formalism. This new system has been applied successfully to several tasks taken from the machine learning literature.

---