Inductive logic programming: Difference between revisions

Revision as of 12:01, 29 February 2024

Revision as of 12:14, 29 February 2024

Line 62:

=== Top-down search ===

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) operation instead, which is less non-deterministic than anti-entailment.

Questions of completeness of a hypothesis search procedure of specific inductive logic programming system arise. For example, the 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.

=== Metainterpretive learning ===