Inductive logic programming: Difference between revisions

Revision as of 17:51, 10 December 2023

Revision as of 09:49, 11 December 2023

Line 59:

Inverse resolution is an [[inductive reasoning]] technique that involves [[wiktionary:invert|inverting]] the [[Resolution (logic)|resolution operator]].

Inverse resolution takes information about the [[Resolvent (logic)|resolvent]] of a resolution step to compute possible resolving clauses. Two types of inverse resolution operator are in use in [[inductive logic programming]]: V-operators and W-operators. A V-operator takes clauses <math display="inline">R</math> and <math display="inline">C_1</math>as input and returns a clause <math display="inline">C_2</math> such that <math display="inline">R</math> is the resolvent of <math display="inline">C_1</math> and <math display="inline">C_2</math>. A W-operator takes two clauses <math display="inline">R_1</math> and <math display="inline">R_2</math> and returns thre clauses <math display="inline">C_1</math>, <math display="inline">C_2</math> and <math display="inline">C_3</math> such that <math display="inline">R_1</math> is the resolvent of <math display="inline">C_1</math> and <math display="inline">C_2</math> and <math display="inline">R_2</math> is the resolvent of <math display="inline">C_2</math> and <math display="inline">C_3</math>.<ref name="invres">{{Cite book |last1=Nienhuys-Cheng |first1=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 |page=197}}</ref>

Inverse resolution was first introduced by [[Stephen Muggleton]] and Wray Buntine in 1988 for use in the inductive logic programming system Cigol.<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> By 1993, this spawned a surge of research into inverse resolution operators and their properties.<ref name="invres" />

Line 66:

The ILP systems Progol,<ref name=":2" /> Hail <ref>{{cite book |last1=Ray |first1=O. |url= |title=Proceedings of the 13th international conference on inductive logic programming |last2=Broda |first2=K. |last3=Russo |first3=A.M. |date=2003 |publisher=Springer |isbn=978-3-540-39917-9 |series=LNCS |volume=2835 |pages=311–328 |chapter=Hybrid abductive inductive learning |citeseerx=10.1.1.212.6602 |doi=10.1007/978-3-540-39917-9_21 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-39917-9_21}}</ref> and Imparo <ref>{{cite book |last1=Kimber |first1=T. |title=Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning |last2=Broda |first2=K. |last3=Russo |first3=A. |date=2009 |publisher=Springer |isbn=978-3-642-04238-6 |series=LNCS |volume=575 |pages=169–181 |chapter=Induction on failure: learning connected Horn theories |doi=10.1007/978-3-642-04238-6_16 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-04238-6_16}}</ref> find a hypothesis {{mvar|H}} using the principle of the '''inverse entailment'''<ref name=":2" /> for theories {{mvar|B}}, {{mvar|E}}, {{mvar|H}}: <math>B \land H \models E \iff B \land \neg E \models \neg H</math>. First they construct an intermediate theory {{mvar|F}} called a bridge theory satisfying the conditions <math>B \land \neg E \models F</math> and <math>F \models \neg H</math>. Then as <math>H \models \neg F</math>, they generalize the negation of the bridge theory {{mvar|F}} with anti-entailment.<ref>{{cite journal |last1=Yamamoto |first1=Yoshitaka |last2=Inoue |first2=Katsumi |last3=Iwanuma |first3=Koji |year=2012 |title=Inverse subsumption for complete explanatory induction |url=https://link.springer.com/content/pdf/10.1007/s10994-011-5250-y.pdf |journal=Machine Learning |volume=86 |pages=115–139 |doi=10.1007/s10994-011-5250-y |s2cid=11347607}}</ref> 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'''.<ref>{{cite book |last=Yamamoto |first=Akihiro |url= |title=International Conference on Inductive Logic Programming |date=1997 |publisher=Springer |isbn=978-3-540-69587-5 |series=Lecture Notes in Computer Science |volume=1297 |___location= |pages=296–308 |chapter=Which hypotheses can be found with inverse entailment? |citeseerx=10.1.1.54.2975 |doi=10.1007/3540635149_58 |chapter-url=https://link.springer.com/chapter/10.1007/3540635149_58}}</ref> On the other hand, Imparo is complete by both anti-entailment procedure <ref name="kimber2009induction">{{cite thesis |first=Timothy |last=Kimber |title=Learning definite and normal logic programs by induction on failure |date=2012 |type=PhD |publisher=Imperial College London |url=https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.560694 |id=ethos 560694 |access-date=2022-10-21 |archive-date=2022-10-21 |archive-url=https://web.archive.org/web/20221021035457/https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.560694 |url-status=dead}}</ref> and its extended inverse subsumption <ref>{{cite arXiv |eprint=1407.3836 |class=cs.AI |first=David |last=Toth |title=Imparo is complete by inverse subsumption |date=2014}}</ref> procedure.

== List of implementations ==