Induktivno logičko programiranje

Induktivno logičko programiranje (ILP) je podoblast mašinskog učenja koji koristi logiku programiranja kao jedinstvenu reprezentaciju za primere, znanje i hipoteze. Dalo je kodiranje poznatog predznanja i skupa primera predstavljenih kao logična baza činjenica, jedan ILP sistem će izvesti hipoteza logičkih programa koji obuhvata sve pozitivne i ništa od negativnih primera.

Šema: pozitivni primeri + negativni primeri + predznanje => hipoteza.

Induktivno logičko programiranje je posebno korisno u bioinformatici i obradi prirodnog jezika. Ehud Šapiro je položio teorijski temelj za induktivno logičko programiranje^[1]^[2] i izgradio svoju prvu primenu (model Inference Sistema) 1981:^[3] Prolog program koji induktivno zaključene logičke programe iz pozitivnih i negativnih primera. Termin Induktivno logičko programiranje je prvi put uvedeno^[4] u rad Stephena Muggletona 1991.^[5] Termin "induktivno" ovde se odnosi na filozofsku (tj sugeriše teoriju da objasni posmatrane činjenice) više nego na matematičku (tj dokazivanja imovine za sve članove dobro - organizovanog seta) indukciju.

Formalna definicija[uredi | uredi izvor]

Prethodno znanje je dato kao logička teorija $B$ , obično u obliku Horn klauzule koje se koriste u logičkom programiranju. Pozitivni i negativni primeri su dati kao celina $E^{+}$ i $E^{-}$ od unnegated i negiranih podzemnih literala, respektivno. Ispravno hipoteza $h$ je logička propozicija koja zadovoljava sledeće uslove.^[6] | Potreba: | $B$ | $\not \models$ | $E^{+}$ |- | Dovoljnost: | $B\land h$ | $\models$ | $E^{+}$ |- | Slaba konzistentnost: | $B\land h$ | $\not \models$ | ${\textit {false}}$ |- | Jaka konzistentnost: | $B\land h\land E^{-}$ | $\not \models$ | ${\textit {false}}$ |} "Potreba" ne nameće ograničavanje $h$ , ali zabranjuje svaku generaciju hipoteza sve dok se pozitivne činjenice ne objasne bez nje. "Dovoljnost" zahteva nikakvu generisanu hipotezu $h$ za objašnjenje svih pozitivnih primera $E^{+}$ . "Slaba doslednost" zabranjuje generaciju bilo koje hipoteze $h$ koja je u suprotnosti sa pozadinom znanja $B$ . "Jaka koinzistentnost" takođe zabranjuje stvaranje bilo koje hipoteze h koja nije u skladu sa negativnim primerima $E^{-}$ , s obzirom na prethodno znanje $B$ ; to podrazumeva "slabu konzistentnost"; ako su dati nikakvi negativni primeri, oba uslova se poklapaju. Džeroski^[7] zahteva samo "dovoljnost" (pod nazivom "potpunost" tamo) i "Jaku doslednost".

Primer[uredi | uredi izvor]

Preuzet porodični odnos u rubrici "primer

”

Sledeći poznati primer za učenje definicija porodičnih odnosa koriste skraćenice par : parent, fem : female, dau : daughter, g : George, h : Helen, m : Mary, t : Tom, n : Nancy, i e : Eve... To počinje od pozadine znanja (uporedi sliku)

{\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)

,

su pozitivni primeri

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

,

i trivijalni predlog ${\textit {true}}$ da označi odsustvo negativnih primera.

Plotkinsova^[8]^[9] "Relativna najmanja opšta generalizacija (Rnog)" je pristup induktivnom logičkom programiranju koja se koristi kako bi se dobio predlog o tome kako da se formalno definiše ćerka odnosno ${\textit {dau}}$ .

Ovaj pristup koristi sledeće korake.

Relativizuje svaki pozitivan primer bukvalno sa kompletnim predznanjem:
- ${\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)$ ,
Pretvori u klauzulu normalanog oblika:
- ${\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)$ ,
Borba protiv svakog kompatibilnog^[10] para ^[11] literala:
- ${\textit {dau}}(x_{me},x_{ht})$ od ${\textit {dau}}(m,h)$ i ${\textit {dau}}(e,t)$ ,
- $\lnot {\textit {par}}(x_{ht},x_{me})$ od $\lnot {\textit {par}}(h,m)$ i $\lnot {\textit {par}}(t,e)$ ,
- $\lnot {\textit {fem}}(x_{me})$ od $\lnot {\textit {fem}}(m)$ i $\lnot {\textit {fem}}(e)$ ,
- $\lnot {\textit {par}}(g,m)$ od $\lnot {\textit {par}}(g,m)$ i $\lnot {\textit {par}}(g,m)$ , sličan za sve ostale literale pozadinskog znanja
- $\lnot {\textit {par}}(x_{gt},x_{me})$ od $\lnot {\textit {par}}(g,m)$ i $\lnot {\textit {par}}(t,e)$ , i još mnogo negiranih literala
Obriši sve negirane literale koji sadrže varijable koje se ne javljaju u pozitivnim literalima:
- nakon brisanja svih negiranih literala koji sadrže druge promenljive od $x_{me},x_{ht}$ , samo ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ Ostaje, zajedno sa svim kopnenim literalima iz znanja pozadine
Pretvori klauzule nazad na Horn formu:
- ${\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}}(x_{me})\land ({\text{all background knowledge facts}})$

Dobijena Horn klauzula hipoteza $h$ dobijena pomoću Rig pristupa. Ignorisanje pozadine činjenica znanja, klauzula neformalno piše " $x_{me}$ zove ćerku $x_{ht}$ ako $x_{ht}$ je roditelj od $x_{me}$ i $x_{me}$ je žensko", što je uobičajeno prihvaćena definicija.

Što se tiče gorenavedenih uslova, "Potreba" je zadovoljana jer predikat ${\textit {dau}}$ se ne pojavljuje u pozadini znanja, koja stoga ne može označiti bilo koju imovinu koja sadrži ovaj predikat, kao što su pozitivni primeri. "Dovoljnost" je zadovoljena obračunatim hipotezama $h$ , pošto ona, zajedno sa ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ od pozadinskog znanja, podrazumeva prvi pozitivan primer ${\textit {dau}}(m,h)$ , i slično $h$ i ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ iz poznavanja pozadine podrazumeva drugi pozitivan primer ${\textit {dau}}(e,t)$ ."Slaba koinzistentnost" je zadovoljena sa $h$ , jer ona drži $h$ u (konačnoj) Herbrand strukturi opisa pozadinskog znanja; slično za "Jaka konzistentnost".

Zajednička definicija baka odnosa, naime. ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ , ne mogu naučiti korišćenjem gorenavedenog pristupa, pošto promenljiva $y$ se javlja samo u telima klauzula; odgovarajući literali bi bili izbrisana u 4. koraka. Da bi se prevazišao ovaj propust, taj korak mora biti modifikovan tako da se može parametrizovati sa različitim literalima nakon selekcije heuristike. Istorijski, implementacija GOLEM se zasniva na Rig pristupu.

Induktivni logički programski sistem[uredi | uredi izvor]

Induktivni logički programski sistem je program koji se uzima kao ulaz logičkih teorija $B,E^{+},E^{-}$ i daje ispravnu hipotezu $H$ VRT teorije $B,E^{+},E^{-}$ Algoritam jednog ILP sistema se sastoji iz dva dela: hipoteza traženja i selekcije hipoteza. Prvo hipoteza je pretres sa induktivnim postupkom logičkog programiranja, onda podskup nalazi hipotezu (u većini sistema jedna hipoteza) izabranu od strane izbor algoritma. Sortira bodove algoritma, svake od pronađeni hipoteza i vraća one sa najvećom ocenom. Primer skor funkcija uključuje minimalnu dužinu kompresije gde je hipoteza sa najnižom Kolmogorovom kompleksnoščću ima najvišu ocenu i vraća se. ILP sistem je kompletan akko za bilo kakve ulaze logičkih teorija $B,E^{+},E^{-}$ neka ispravna hipoteza $H$ VRT ove ulazne teorije može se naći sa svojom hipotezom u istraživačkoj proceduri.

Pretraga Hipoteza[uredi | uredi izvor]

Moderni ILP sistemi kao što su Progol,^[5] Hail^[12] i Imparo ^[13] pronalaze hipotezu H koristeći princip inverznih elemenata^[5] za teoriju B, E, H: $B\land H\models E\iff B\land \neg E\models \neg H$ . Prvo se konstruiše srednja teorija F i naziva se teorija mosta koja ispunjava uslove $B\land \neg E\models F$ and $F\models \neg H$ . Onda $H\models \neg F$ , oni generalizuju negaciju teorije mosta F sa anti-entailment. Međutim, rad na anti-entailment je visoko ne-deterministički računski skup. Dakle, alternativna hipoteza pretraga može se obaviti pomoću rada inverzne supsumacije (anti-supsumacije) umesto što je manje nedeterministički od anti-entailment.

Pitanja potpunost postupka hipoteza za pretragu specifičnog ILP sistema nastaju. Na primer, Progol hipoteza istraživanja postupka na osnovu obrnutog entailment zaključivanja pravila nije završen u Jamamoto primeru.^[14] S druge strane, Imparo je završena u anti-entailment postupku^[15] i njegovoj izuzetno inverznoj supsumaciji^[16] postupka.

Implementacije[uredi | uredi izvor]

1BC i 1BC2: prvog reda naivni Baiesova klasifikatori: (http://www.cs.bris.ac.uk/Research/MachineLearning/1BC/)
ACE (Kombinovani Motor) (http://dtai.cs.kuleuven.be/ACE/ Arhivirano na sajtu Wayback Machine (9. decembar 2014))
Aleph (http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/)
Atom (http://www.ahlgren.info/research/atom/ Arhivirano na sajtu Wayback Machine (26. mart 2014))
Claudien (http://dtai.cs.kuleuven.be/claudien/^{[mrtva veza]})
DL-Learner (https://web.archive.org/web/20190815184411/http://dl-learner.org/)
DMax (http://dtai.cs.kuleuven.be/dmax/ Arhivirano na sajtu Wayback Machine (6. mart 2014))
FOIL(ftp://ftp.cs.su.oz.au/pub/foil6.sh^{[mrtva veza]})
Golem (ILP) (http://www.doc.ic.ac.uk/~shm/Software/golem)
Imparo^[15]
Inthelex (INcremental THEory Learner from EXamples) (http://lacam.di.uniba.it:8000/systems/inthelex/ Arhivirano na sajtu Wayback Machine (28. novembar 2011))
Lime (https://web.archive.org/web/20020516195248/http://cs.anu.edu.au/people/Eric.McCreath/lime.html)
Mio (http://libra.msra.cn/Publication/3392493/mio-user-s-manual Arhivirano 2013-02-19 na sajtu Archive.today)
MIS (Model Inference System) by Ehud Shapiro
PROGOL (http://www.doc.ic.ac.uk/~shm/Software/progol5.0)
RSD (https://web.archive.org/web/20070301162526/http://labe.felk.cvut.cz/~zelezny/rsd/)
Tertius (http://www.cs.bris.ac.uk/publications/Papers/1000545.pdf)
Warmr (sada uključeni u ACE)
ProGolem (http://ilp.doc.ic.ac.uk/ProGolem/) ^[17]^[18]

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press. Cambridge, MA. (1991). str. 199–254.
^ Shapiro, Ehud Y. . Algorithmic program debugging. Cambridge, Mass. . MIT Press. 1983. ISBN 978-0-262-19218-7.
^ Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.
^ Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. CiteSeerX: 10.1.1.56.1790
^ ^а ^б ^в Muggleton, S. (1991). „Inductive logic programming”. New Generation Computing. 8 (4): 295—318. doi:10.1007/BF03037089.
^ Muggleton, Stephen (1999). „Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic”. Artificial Intelligence. 114: 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”, Ур.: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, стр. 117—152 ; here: Sect.5.2.4
^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., ур. „A Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 5: 153—163.
^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., ур. „A Further Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 6: 101—124.
^ 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. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.
^ Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.
^ Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.
^ ^а ^б Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.
^ David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836
^ Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). „ProGolem: a system based on relative minimal generalization” (PDF). ILP.
^ 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” (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. Архивирано из оригинала (PDF) 03. 03. 2016. г. Приступљено 08. 01. 2016.

Литература[uredi | uredi izvor]

Muggleton, S.; De Raedt, L. (1994). „Inductive Logic Programming: Theory and methods”. The Journal of Logic Programming. 19-20: 629—679. doi:10.1016/0743-1066(94)90035-3.
Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 978-0-13-457870-5. Архивирано из оригинала 6. 9. 2004. г. Приступљено 8. 1. 2016.
Visual example of inducing the grandparenthood relation by the Atom system. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html Arhivirano na sajtu Wayback Machine (26. mart 2014)

[1] Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press. Cambridge, MA. (1991). str. 199–254.

[2] Shapiro, Ehud Y. . Algorithmic program debugging. Cambridge, Mass. . MIT Press. 1983. ISBN 978-0-262-19218-7.

[3] Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.

[4] Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. CiteSeerX: 10.1.1.56.1790

[muggleton1995inverse-5] а ^б ^в Muggleton, S. (1991). „Inductive logic programming”. New Generation Computing. 8 (4): 295—318. doi:10.1007/BF03037089.

[6] Muggleton, Stephen (1999). „Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic”. Artificial Intelligence. 114: 283—296. doi:10.1016/s0004-3702(99)00067-3. ; here: Sect.2.1

[7] Džeroski, Sašo (1996), „Inductive Logic Programming and Knowledge Discovery in Databases”, Ур.: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, стр. 117—152 ; here: Sect.5.2.4

[8] Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., ур. „A Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 5: 153—163.

[9] Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., ур. „A Further Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 6: 101—124.

[10] .e. sharing the same predicate symbol and negated/unnegated status

[11] ral: $n$ -tuple when $n$ positive example literals are given

[12] Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.

[13] Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.

[14] Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.

[kimber2009induction-15] а ^б Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.

[16] David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836

[17] Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). „ProGolem: a system based on relative minimal generalization” (PDF). ILP.

[18] 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” (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. Архивирано из оригинала (PDF) 03. 03. 2016. г. Приступљено 08. 01. 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]