Inductive logic programming: Difference between revisions

Content deleted Content added

Inline

Revision as of 17:11, 27 November 2023

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical (i.e. suggesting a theory to explain observed facts) rather than mathematical (i.e. proving a property for all members of a well-ordered set) induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

Schema: positive examples + negative examples + background knowledge ⇒ hypothesis.

Inductive logic programming is particularly useful in bioinformatics and natural language processing.

History

Building on earlier work on Inductive inference, Gordon Plotkin was the first to formalise induction in a clausal setting around 1970, adopting an approach of generalising from examples.^[1]^[2] In 1981, Ehud Shapiro introduced several ideas that would shape the field in his new approach of model inference, an algorithm employing refinement and backtracing to search for a complete axiomatisation of given examples.^[1]^[3] His first implementation was the Model Inference System in 1981:^[4]^[5] a Prolog program that inductively inferred Horn clause logic programs from positive and negative examples.^[1] The term Inductive Logic Programming was first introduced in a paper by Stephen Muggleton in 1990, defined as the intersection of machine learning and logic programming.^[1] Muggleton and Wray Buntine introduced predicate invention and inverse resolution in 1988.^[1]^[6]

Several inductive logic programming systems that proved influential appeared in the early 1990s. FOIL, introduced by Quinlan in 1990^[7] was based on upgrading propositional learning algorithms AQ and ID3.^[8] Golem, introduced by Muggleton and Feng in 1990, went back to a restricted form of Plotkin's least generalisation algorithm.^[8]^[9] The Progol system, introduced by Muggleton in 1995, first implemented inverse entailment, and inspired many later systems.^[8]^[10]^[11] Aleph, one of the descendants of Progol introduced by Ashwin Srinivasan in 2001, is still one of the most widely used systems as of 2022.^[update]^[10]

At around the same time, the first practical applications emerged, particularly in bioinformatics, where by 2000 inductive logic programming had been successfully applied to drug design, carcinogenicity and mutagenicity prediction, and elucidation of the structure and function of proteins.^[12] Unlike the focus on automatic programming inherent in the early work, these fields used inductive logic programming techniques from a viewpoint of relational data mining. The success of those initial applications and the lack of progress in recovering larger traditional logic programs shaped the focus of the field.^[13]

Formal definition

The background knowledge is given as a logic theory $B$ , commonly in the form of Horn clauses used in logic programming. The positive and negative examples are given as a conjunction $E^{+}$ and $E^{-}$ of unnegated and negated ground literals, respectively. A correct hypothesis $h$ is a logic proposition satisfying the following requirements.^[14]

{\begin{array}{llll}{\text{Necessity:}}&B&\not \models &E^{+}\\{\text{Sufficiency:}}&B\land h&\color {blue}{\models }&E^{+}\\{\text{Weak consistency:}}&B\land h&\not \models &{\textit {false}}\\{\text{Strong consistency:}}&B\land h\land E^{-}&\not \models &{\textit {false}}\end{array}}

"Necessity" does not impose a restriction on $h$ , but forbids any generation of a hypothesis as long as the positive facts are explainable without it. "Sufficiency" requires any generated hypothesis $h$ to explain all positive examples $E^{+}$ . "Weak consistency" forbids generation of any hypothesis $h$ that contradicts the background knowledge $B$ . "Strong consistency" also forbids generation of any hypothesis $h$ that is inconsistent with the negative examples $E^{-}$ , given the background knowledge $B$ ; it implies "Weak consistency"; if no negative examples are given, both requirements coincide. Džeroski ^[15] requires only "Sufficiency" (called "Completeness" there) and "Strong consistency".

Example

The following well-known example about learning definitions of family relations uses the abbreviations

par : parent

,

fem : female

,

dau : daughter

,

g : George

,

h : Helen

,

m : Mary

,

t : Tom

,

n : Nancy

, and

e : Eve

.

It starts from the background knowledge (cf. picture)

{\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)

,

the positive examples

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

,

and the trivial proposition $true$ to denote the absence of negative examples.

Plotkin's ^[16]^[17] "relative least general generalization (rlgg)" approach to inductive logic programming shall be used to obtain a suggestion about how to formally define the daughter relation $dau$ .

This approach uses the following steps.

Relativize each positive example literal with the complete background knowledge:
${\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}$ ,
Convert into clause normal form:
${\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}$ ,
Anti-unify each compatible ^[18] pair ^[19] of literals:
- ${\textit {dau}}(x_{me},x_{ht})$ from ${\textit {dau}}(m,h)$ and ${\textit {dau}}(e,t)$ ,
- $\lnot {\textit {par}}(x_{ht},x_{me})$ from $\lnot {\textit {par}}(h,m)$ and $\lnot {\textit {par}}(t,e)$ ,
- $\lnot {\textit {fem}}(x_{me})$ from $\lnot {\textit {fem}}(m)$ and $\lnot {\textit {fem}}(e)$ ,
- $\lnot {\textit {par}}(g,m)$ from $\lnot {\textit {par}}(g,m)$ and $\lnot {\textit {par}}(g,m)$ , similar for all other background-knowledge literals
- $\lnot {\textit {par}}(x_{gt},x_{me})$ from $\lnot {\textit {par}}(g,m)$ and $\lnot {\textit {par}}(t,e)$ , and many more negated literals
Delete all negated literals containing variables that don't occur in a positive literal:
- after deleting all negated literals containing other variables than $x_{me},x_{ht}$ , only ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ remains, together with all ground literals from the background knowledge
Convert clauses back to Horn form:
- ${\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}}(x_{me})\land ({\text{all background knowledge facts}})$

The resulting Horn clause is the hypothesis $h$ obtained by the rlgg approach. Ignoring the background knowledge facts, the clause informally reads " $x_{me}$ is called a daughter of $x_{ht}$ if $x_{ht}$ is the parent of $x_{me}$ and $x_{me}$ is female", which is a commonly accepted definition.

Concerning the above requirements, "Necessity" was satisfied because the predicate $dau$ doesn't appear in the background knowledge, which hence cannot imply any property containing this predicate, such as the positive examples are. "Sufficiency" is satisfied by the computed hypothesis $h$ , since it, together with ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ from the background knowledge, implies the first positive example ${\textit {dau}}(m,h)$ , and similarly $h$ and ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ from the background knowledge implies the second positive example ${\textit {dau}}(e,t)$ . "Weak consistency" is satisfied by $h$ , since $h$ holds in the (finite) Herbrand structure described by the background knowledge; similar for "Strong consistency".

The common definition of the grandmother relation, viz. ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ , cannot be learned using the above approach, since the variable $y$ occurs in the clause body only; the corresponding literals would have been deleted in the 4th step of the approach. To overcome this flaw, that step has to be modified such that it can be parametrized with different literal post-selection heuristics. Historically, the GOLEM implementation is based on the rlgg approach.

Inductive Logic Programming system

An inductive logic programming system is a program that takes as an input logic theories $B,E^{+},E^{-}$ and outputs a correct hypothesis $H$ with respect to theories $B,E^{+},E^{-}$ . Search-based ILP systems consist of two parts: hypothesis search and hypothesis selection. First a hypothesis is searched with an inductive logic programming procedure, then a subset of the found hypotheses (in most systems one hypothesis) is chosen by a selection algorithm. A selection algorithm scores each of the found hypotheses and returns the ones with the highest score. An example of score function include minimal compression length where a hypothesis with a lowest Kolmogorov complexity has the highest score and is returned. An ILP system is complete if and only if for any input logic theories $B,E^{+},E^{-}$ any correct hypothesis $H$ with respect to these input theories can be found with its hypothesis search procedure.

Hypothesis search

The ILP systems Progol,^[11] Hail ^[20] and Imparo ^[21] find a hypothesis $H$ using the principle of the inverse entailment^[11] for theories $B$ , $E$ , $H$ : $B\land H\models E\iff B\land \neg E\models \neg H$ . First they construct an intermediate theory $F$ called a bridge theory satisfying the conditions $B\land \neg E\models F$ and $F\models \neg H$ . Then as $H\models \neg F$ , they generalize the negation of the bridge theory $F$ with anti-entailment.^[22] However, the operation of anti-entailment is computationally more expensive since it is highly nondeterministic. Therefore, an alternative hypothesis search can be conducted using the operation of the inverse subsumption (anti-subsumption) instead which is less non-deterministic than anti-entailment.

Questions of completeness of a hypothesis search procedure of specific ILP system arise. For example, Progol's hypothesis search procedure based on the inverse entailment inference rule is not complete by Yamamoto's example.^[23] On the other hand, Imparo is complete by both anti-entailment procedure ^[24] and its extended inverse subsumption ^[25] procedure.

Implementations

1BC and 1BC2: first-order naive Bayesian classifiers:
ACE (A Combined Engine)
Aleph
Atom Archived 2014-03-26 at the Wayback Machine
Claudien^{[permanent dead link]}
DL-Learner
DMax
FastLAS (Fast Learning from Answer Sets)
FOIL (First Order Inductive Learner)
Golem
ILASP (Inductive Learning of Answer Set Programs)
Imparo^[24]
Inthelex (INcremental THEory Learner from EXamples) Archived 2011-11-28 at the Wayback Machine
Lime
Metagol
Mio
MIS (Model Inference System) by Ehud Shapiro
PROGOL
RSD
Warmr (now included in ACE)
ProGolem ^[26]^[27]

References

^ ^a ^b ^c ^d ^e Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Foundations of inductive logic programming. Lecture notes in computer science Lecture notes in artificial intelligence. Berlin Heidelberg: Spinger. pp. 174–177. ISBN 978-3-540-62927-6.
^ Plotkin, G.D. (1970). Automatic Methods of Inductive Inference (PDF) (PhD). University of Edinburgh. hdl:1842/6656.
^ Shapiro, Ehud Y. (1981). Inductive inference of theories from facts (PDF) (Technical report). Department of Computer Science, Yale University. 192. Reprinted in Lassez, J.-L.; Plotkin, G., eds. (1991). Computational logic : essays in honor of Alan Robinson. MIT Press. pp. 199–254. ISBN 978-0-262-12156-9.
^ Shapiro, Ehud Y. (1981). "The model inference system" (PDF). Proceedings of the 7th international joint conference on Artificial intelligence. Vol. 2. Morgan Kaufmann. p. 1064.
^ Shapiro, Ehud Y. (1983). Algorithmic program debugging. MIT Press. ISBN 0-262-19218-7.
^ Muggleton, S.H.; Buntine, W. (1988). "Machine invention of first-order predicate by inverting resolution". Proceedings of the 5th International Conference on Machine Learning. pp. 339–352. doi:10.1016/B978-0-934613-64-4.50040-2. ISBN 978-0-934613-64-4.
^ Quinlan, J. R. (August 1990). "Learning logical definitions from relations". Machine Learning. 5 (3): 239–266. doi:10.1007/bf00117105. ISSN 0885-6125.
^ ^a ^b ^c Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Foundations of inductive logic programming. Lecture notes in computer science Lecture notes in artificial intelligence. Berlin Heidelberg: Spinger. pp. 354–358. ISBN 978-3-540-62927-6.
^ Muggleton, Stephen H.; Feng, Cao (1990). Arikawa, Setsuo; Goto, Shigeki; Ohsuga, Setsuo; Yokomori, Takashi (eds.). "Efficient Induction of Logic Programs". Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings. Springer/Ohmsha: 368–381.
^ ^a ^b Cropper, Andrew; Dumančić, Sebastijan (2022-06-15). "Inductive Logic Programming At 30: A New Introduction". Journal of Artificial Intelligence Research. 74: 808. doi:10.1613/jair.1.13507. ISSN 1076-9757.
^ ^a ^b ^c Muggleton, S.H. (1995). "Inverting entailment and Progol". New Generation Computing. 13 (3–4): 245–286. CiteSeerX 10.1.1.31.1630. doi:10.1007/bf03037227. S2CID 12643399.
^ Džeroski, Sašo (2001), Džeroski, Sašo; Lavrač, Nada (eds.), "Relational Data Mining Applications: An Overview", Relational Data Mining, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 339–364, doi:10.1007/978-3-662-04599-2_14, ISBN 978-3-642-07604-6, retrieved 2023-11-27
^ De Raedt, Luc (2008), Logical and Relational Learning, Cognitive Technologies, Berlin, Heidelberg: Springer, p. 14, Bibcode:2008lrl..book.....D, doi:10.1007/978-3-540-68856-3, ISBN 978-3-540-20040-6
^ Muggleton, Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence. 114 (1–2): 283–296. doi:10.1016/s0004-3702(99)00067-3.; here: Sect.2.1
^ Džeroski, Sašo (1996). "Inductive Logic Programming and Knowledge Discovery in Databases" (PDF). In Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.). Advances in Knowledge Discovery and Data Mining. MIT Press. pp. 117–152 See §5.2.4. Archived from the original (PDF) on 2021-09-27. Retrieved 2021-09-27.
^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "A Note on Inductive Generalization". Machine Intelligence. 5: 153–163. ISBN 978-0-444-19688-0.
^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "A Further Note on Inductive Generalization". Machine Intelligence. 6. Edinburgh University Press: 101–124. ISBN 978-0-85224-195-0.
^ i.e. sharing the same predicate symbol and negated/unnegated status
^ in general: $n$ -tuple when $n$ positive example literals are given
^ Ray, O.; Broda, K.; Russo, A.M. (2003). "Hybrid abductive inductive learning". Proceedings of the 13th international conference on inductive logic programming. LNCS. Vol. 2835. Springer. pp. 311–328. CiteSeerX 10.1.1.212.6602. doi:10.1007/978-3-540-39917-9_21. ISBN 978-3-540-39917-9.
^ Kimber, T.; Broda, K.; Russo, A. (2009). "Induction on failure: learning connected Horn theories". Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning. LNCS. Vol. 575. Springer. pp. 169–181. doi:10.1007/978-3-642-04238-6_16. ISBN 978-3-642-04238-6.
^ Yamamoto, Yoshitaka; Inoue, Katsumi; Iwanuma, Koji (2012). "Inverse subsumption for complete explanatory induction" (PDF). Machine Learning. 86: 115–139. doi:10.1007/s10994-011-5250-y. S2CID 11347607.
^ Yamamoto, Akihiro (1997). "Which hypotheses can be found with inverse entailment?". International Conference on Inductive Logic Programming. Lecture Notes in Computer Science. Vol. 1297. Springer. pp. 296–308. CiteSeerX 10.1.1.54.2975. doi:10.1007/3540635149_58. ISBN 978-3-540-69587-5.
^ ^a ^b Kimber, Timothy (2012). Learning definite and normal logic programs by induction on failure (PhD). Imperial College London. ethos 560694. Archived from the original on 2022-10-21. Retrieved 2022-10-21.
^ Toth, David (2014). "Imparo is complete by inverse subsumption". arXiv:1407.3836 [cs.AI].
^ Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). "ProGolem: a system based on relative minimal generalization". International Conference on Inductive Logic Programming. Springer. pp. 131–148. CiteSeerX 10.1.1.297.7992. doi:10.1007/978-3-642-13840-9_13. ISBN 978-3-642-13840-9.
^ Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). "Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study". BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. PMC 3458898. PMID 22783946.

@@ Line 10: / Line 10: @@
 Building on earlier work on [[Inductive inference]], [[Gordon Plotkin]] was the first to formalise induction in a [[Horn clause|clausal]] setting around 1970, adopting an approach of generalising from examples.<ref name=":0">{{Cite book |last=Nienhuys-Cheng |first=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Spinger |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |location=Berlin Heidelberg |pages=174–177}}</ref><ref>{{cite thesis |first=G.D. |last=Plotkin |title=Automatic Methods of Inductive Inference |date=1970 |type=PhD |publisher=University of Edinburgh |url=https://www.era.lib.ed.ac.uk/bitstream/handle/1842/6656/Plotkin1972.pdf |hdl=1842/6656}}</ref> In 1981, [[Ehud Shapiro]] introduced several ideas that would shape the field in his new approach of model inference, an algorithm employing refinement and backtracing to search for a complete axiomatisation of given examples.<ref name=":0" /><ref>{{cite tech report|first=Ehud Y.|last=Shapiro|title=Inductive inference of theories from facts|id=192|date=1981|publisher=Department of Computer Science, Yale University|url=http://ftp.cs.yale.edu/publications/techreports/tr192.pdf}} Reprinted in {{cite book |title=Computational logic : essays in honor of Alan Robinson |publisher=MIT Press |year=1991 |isbn=978-0-262-12156-9 |editor1-last=Lassez |editor1-first=J.-L. |pages=199–254 |editor2-last=Plotkin |editor2-first=G.}}</ref> His first implementation was the Model Inference System in 1981:<ref>{{cite book |last=Shapiro |first=Ehud Y. |url= |title=Proceedings of the 7th international joint conference on Artificial intelligence |date=1981 |publisher=Morgan Kaufmann |isbn= |volume=2 |location= |pages=1064 |chapter=The model inference system |chapter-url=https://www.ijcai.org/Proceedings/81-2/Papers/100.pdf}}</ref><ref>{{cite book |last=Shapiro |first=Ehud Y. |url= |title=Algorithmic program debugging |date=1983 |publisher=MIT Press |isbn=0-262-19218-7 |location= |pages=}}</ref> a [[Prolog]] program that inductively inferred [[Horn clause]] logic programs from positive and negative examples.<ref name=":0" /> The term ''Inductive Logic Programming'' was first introduced in a paper by [[Stephen Muggleton]] in 1990, defined as the intersection of machine learning and logic programming.<ref name=":0" /> Muggleton and Wray Buntine introduced predicate invention and [[inverse resolution]] in 1988.<ref name=":0" /><ref>{{cite book |last1=Muggleton |first1=S.H. |url= |title=Proceedings of the 5th International Conference on Machine Learning |last2=Buntine |first2=W. |date=1988 |isbn=978-0-934613-64-4 |pages=339–352 |chapter=Machine invention of first-order predicate by inverting resolution |doi=10.1016/B978-0-934613-64-4.50040-2}}</ref>
-Several inductive logic programming systems that proved influential appeared in the early 1990s. [[First-order inductive learner|FOIL]], introduced by Quinlan in 1990<ref>{{Cite journal |last=Quinlan |first=J. R. |date=August 1990 |title=Learning logical definitions from relations |url=http://dx.doi.org/10.1007/bf00117105 |journal=Machine Learning |volume=5 |issue=3 |pages=239–266 |doi=10.1007/bf00117105 |issn=0885-6125}}</ref> was based on upgrading [[Propositional calculus|propositional]] learning algorithms [[AQ (machine learning)|AQ]] and [[ID3 algorithm|ID3]].<ref name=":1">{{Cite book |last=Nienhuys-Cheng |first=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Spinger |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |location=Berlin Heidelberg |pages=354–358}}</ref> [[Golem (ILP)|Golem]], introduced by Muggleton and   Feng in 1990, went back to a restricted form of Plotkin's least generalisation algorithm.<ref name=":1" /><ref>{{Cite journal |last=Muggleton |first=Stephen H. |last2=Feng |first2=Cao |date=1990 |editor-last=Arikawa |editor-first=Setsuo |editor2-last=Goto |editor2-first=Shigeki |editor3-last=Ohsuga |editor3-first=Setsuo |editor4-last=Yokomori |editor4-first=Takashi |title=Efficient Induction of Logic Programs |url=https://dblp.org/rec/conf/alt/MuggletonF90.bib |journal=Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings |publisher=Springer/Ohmsha |pages=368–381}}</ref> The [[PROGOL]] system, introduced by Muggleton in 1995, first implemented inverse entailment.<ref name=":1" /><ref name=":2">{{cite journal |last1=Muggleton |first1=S.H. |year=1995 |title=Inverting entailment and Progol |journal=New Generation Computing |volume=13 |issue=3–4 |pages=245–286 |citeseerx=10.1.1.31.1630 |doi=10.1007/bf03037227 |s2cid=12643399}}</ref>
+Several inductive logic programming systems that proved influential appeared in the early 1990s. [[First-order inductive learner|FOIL]], introduced by Quinlan in 1990<ref>{{Cite journal |last=Quinlan |first=J. R. |date=August 1990 |title=Learning logical definitions from relations |url=http://dx.doi.org/10.1007/bf00117105 |journal=Machine Learning |volume=5 |issue=3 |pages=239–266 |doi=10.1007/bf00117105 |issn=0885-6125}}</ref> was based on upgrading [[Propositional calculus|propositional]] learning algorithms [[AQ (machine learning)|AQ]] and [[ID3 algorithm|ID3]].<ref name=":1">{{Cite book |last=Nienhuys-Cheng |first=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Spinger |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |location=Berlin Heidelberg |pages=354–358}}</ref> [[Golem (ILP)|Golem]], introduced by Muggleton and   Feng in 1990, went back to a restricted form of Plotkin's least generalisation algorithm.<ref name=":1" /><ref>{{Cite journal |last=Muggleton |first=Stephen H. |last2=Feng |first2=Cao |date=1990 |editor-last=Arikawa |editor-first=Setsuo |editor2-last=Goto |editor2-first=Shigeki |editor3-last=Ohsuga |editor3-first=Setsuo |editor4-last=Yokomori |editor4-first=Takashi |title=Efficient Induction of Logic Programs |url=https://dblp.org/rec/conf/alt/MuggletonF90.bib |journal=Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings |publisher=Springer/Ohmsha |pages=368–381}}</ref> The [[Progol]] system, introduced by Muggleton in 1995, first implemented inverse entailment, and inspired many later systems.<ref name=":1" /><ref name=":3">{{Cite journal |last=Cropper |first=Andrew |last2=Dumančić |first2=Sebastijan |date=2022-06-15 |title=Inductive Logic Programming At 30: A New Introduction |url=http://dx.doi.org/10.1613/jair.1.13507 |journal=Journal of Artificial Intelligence Research |volume=74 |page=808 |pages= |doi=10.1613/jair.1.13507 |issn=1076-9757}}</ref><ref name=":2">{{cite journal |last1=Muggleton |first1=S.H. |year=1995 |title=Inverting entailment and Progol |journal=New Generation Computing |volume=13 |issue=3–4 |pages=245–286 |citeseerx=10.1.1.31.1630 |doi=10.1007/bf03037227 |s2cid=12643399}}</ref> [[Aleph (ILP)|Aleph]], one of the descendants of Progol introduced by Ashwin Srinivasan in 2001, is still one of the most widely used systems {{As of|2022.|lc=y|bare=}}<ref name=":3" />
+At around the same time, the first practical applications emerged, particularly in [[bioinformatics]], where by 2000 inductive logic programming had been successfully applied to drug design, carcinogenicity and mutagenicity prediction, and elucidation of the structure and function of proteins.<ref>{{Citation |last=Džeroski |first=Sašo |title=Relational Data Mining Applications: An Overview |date=2001 |url=http://link.springer.com/10.1007/978-3-662-04599-2_14 |work=Relational Data Mining |pages=339–364 |editor-last=Džeroski |editor-first=Sašo |access-date=2023-11-27 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/978-3-662-04599-2_14 |isbn=978-3-642-07604-6 |editor2-last=Lavrač |editor2-first=Nada}}</ref> Unlike the focus on [[automatic programming]] inherent in the early work, these fields used inductive logic programming techniques from a viewpoint of [[relational data mining]]. The success of those initial applications and the lack of progress in recovering larger traditional logic programs shaped the focus of the field.<ref>{{Citation |last=De Raedt |first=Luc |editor-first1=<!-- Deny Citation Bot--> |editor-last1=<!-- Deny Citation Bot--> |url=http://dx.doi.org/10.1007/978-3-540-68856-3 |title=Logical and Relational Learning |series=Cognitive Technologies |page=14|place=Berlin, Heidelberg |publisher=Springer |year=2008 |doi=10.1007/978-3-540-68856-3 |bibcode=2008lrl..book.....D |isbn=978-3-540-20040-6}}</ref>
 ==Formal definition==