Inductive logic programming: Difference between revisions

Revision as of 12:36, 3 December 2023

Revision as of 16:03, 3 December 2023

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 [[Ross 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|doi-access=free }}</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|doi-access=free }}</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]], a descendant 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>

Recently, classical tasks from automated programming have moved back into focus, as the introduction of meta-interpretative learning makes predicate invention and learning recursive programs more feasible. This technique was pioneered with the [[Metagol]] system introduced by Muggleton, Dianhuan Lin, Niels Pahlavi and Alireza Tamaddoni-Nezhad in 2014.<ref>{{Cite journal |last=Muggleton |first=Stephen H. |last2=Lin |first2=Dianhuan |last3=Pahlavi |first3=Niels |last4=Tamaddoni-Nezhad |first4=Alireza |date=2013-05-01 |title=Meta-interpretive learning: application to grammatical inference |url=http://dx.doi.org/10.1007/s10994-013-5358-3 |journal=Machine Learning |volume=94 |issue=1 |pages=25–49 |doi=10.1007/s10994-013-5358-3 |issn=0885-6125}}</ref> This allows ILP systems to work with fewer examples, and brought successes in learning string transformation programs, answer set grammars and general algorithms.<ref>{{Cite journal |last=Cropper |first=Andrew |last2=Dumančić |first2=Sebastijan |last3=Evans |first3=Richard |last4=Muggleton |first4=Stephen |date=2022 |title=Inductive logic programming at 30 |url=https://link.springer.com/10.1007/s10994-021-06089-1 |journal=Machine Learning |language=en |volume=111 |issue=1 |pages=147–172 |doi=10.1007/s10994-021-06089-1 |issn=0885-6125|doi-access=free }}</ref>

==Formal definition==