Abduktivna logika programiranja

Abduktivna logika programiranja (ALP) je na visokom nivou znanja zastupljenosti okvira koji se mogu koristiti za rešavanje problema deklarativno na osnovu abduktivnog rezonovanja. Prostire se normalno logika programiranja dozvoljavajući nekim predikatima da budu nepotpuno definisani, proglašava ih abducible predikatima. Rešavanje problema se vrši od strane izvoda hipoteze o tim abducible predikatima (abductive hipoteza), kao rešenja problema koje treba rešiti. Ovi problemi mogu biti ili zapažanja koje treba objasniti (kao u klasičnoj otmici) ili ciljevi koje treba postići (kao u normalnom logičko programiranje). Može se koristiti za rešavanje problema u dijagnostici, planiranju, prirodnog jezika i mašinskog učenja. Takođe se koriste za tumačenje negacija kao neuspeh kao oblik abduaktiv razmišljanja.

Sintaksa uredi

Abduktivni logički programi imaju tri komponente, $\langle P,A,IC\rangle ,$ gde:

P je logika programa u potpuno istom obliku kao u logičkom programiranju
A je skup predikatskih imena, zvani abdukible predikata
IC je skup prvog reda klasičnih formula.

Normalno, logika programa P, ne sadrži nikakve odredbe čije glave (ili zaključak) se odnosi na abducible predikate. (. Ovo ograničenje može se napraviti bez gubitka opštosti) Takođe u praksi, mnogo puta ograničenja integriteta u ISu su često ograničena na formu demantija, odnosno klauzule u obliku:

   false:- A1,...,An, not B1, ..., not Bm.

Takva ograničenje znače da nije moguće za sve A1, ..., An da budu istinita i istovremeno sve B1, ..., Bm da je lažna.

Neformalne značenje i rešavanje problema uredi

Klauzule u P definišu set ne-abducible predikata i kroz to daju opis (ili modela) domena problema. Integritet ograničenja u ISu će odrediti opšte osobine domena problema koje treba da se poštuju za bilo koje rješenje problema.

Problem G, koji izražava ili primedbu koja treba da se objasni ili cilj koji se želi, predstavljen je zajedno pozitivne i negativne (NAF) literale. Ovakvi problemi su rešeni računanjem "abductive objašnjenja" G.

Abduktivno objašnjenje problema G je skup pozitivnih (a ponekad i negativne) kopnenih instanca abdukible predikata, tako da, kada se oni dodaju u logički program P, problem G i ograničenja integriteta IC oba ga drže. Tako abduktivna objašnjenja produžuju logiku programa P dodavanjem potpunim ili delimičnim definicijama abducible predikata. Na ovaj način, abduktivna objašnjenja formiraju rešenja problema prema opisu domena problema u P i IC. Produženje ili završetak opisa problema koja su abduktivna objašnjenja daje nove informacije, do sada nisu sadržani u rešenju problema. Kriterijumi kvaliteta da preferiraju jedno rešenje u odnosu na drugo, često izražavao preko integriteta ograničenja, mogu se primeniti da izaberete specifične abduktive objašnjenja problema G.

Obračun u ALPu kombinuje unazad obrazloženje normalne logike programiranja (da se smanji probleme Sub-probleme) sa nekom vrstom integriteta proveravanja da pokaže da se abduktivna objašnjenja zadovoljavaju ograničenjima integriteta.

Sledeća dva primera, napisana jednostavnim strukturiranim engleskim nego strogim sintaksičkim ALP, ilustruju pojam abduktivnog objašnjenja u ALPu i njen odnos prema rešavanju problema.

Primer 1 uredi

Abduktivna logika programa, $\langle P,A,{\mathit {IC}}\rangle$ , ima u $P$ sledeće rečenice:

Trava je mokra ako je padala kiša.

Trava je mokra ako je prskalica bila uključena.

Sunce je sijalo.

U abducible predikatima u $A$ su "je padala kiša" i "prskalica bila uključena" i jedino ograničenje u integritet ${\mathit {IC}}$ je:

  лаж ако је падала киша и сунце је сијало.

Posmatranje da je trava mokra ima dva potencijalna objašnjenja, "je padala kiša" i "prskalica bila uključena", koji podrazumeva posmatranje. Međutim, tek drugo potencijalno objašnjenje ", rekao je prskalica bila uknjučena" zadovoljava integritet ograničenja.

Primer 2 uredi

Razmotrimo abduktivnu logiku programa koji se sastoji od sledećih (Simplified) klauzula:

X je građanin ako X je rođen u SADu.

X je državljanin, ako je X rođen izvan SAD i X je stanovnik SAD i X je naturalizovani.

X je građanin ako X je rođen izvan SAD i Y je majka od X i Y je državljanin i X je registrovan.

Meri je Džonova majka.

Meri je građanin.

zajedno sa pet abducible predikata "je rođen u SAD", "je rođen izvan SAD", "je stanovnik SAD", "je naturalizovani" i "registrovani i integritet ograničenje:

laž ako je Džon stanovnik SAD.

Cilj "Džon je građanin" ima dva abduktivna rešenja, od kojih je jedan "Džon je rođen u SADu", drugi je "Džon je rođen izvan SADa" i "Džon je registrovan". On potencijalno rešenje da postane građanin od boravka i da dobije državljanstvo.

Složeniji primer koji je takođe zapisan u formalnoj sintaksi ALP je sledeći.

Primer 3 uredi

Abduktivna logika programa ispod opisuje jednostavan model laktoze metabolizma bakterija E. coli. Program P, opisuje (u svom prvom pravilu) da se E. coli može hraniti šećerom laktoze, ako to čine dva enzima permease i galaktozidazu. Kao i svi enzimi, one su napravljene ako su kodirane od strane gena (Gene) koji se izražava (opisan od strane drugog pravilu). Dva enzime permeasa i galaktozidaze su kodirani od dva gena, Lac (i) i Lac (z), respektivno (navedenih u petoj i šestoj vladavini programa), u klasteru gena (Lac (x)) - zove Operon - koji se izražava kada su količine (AMT) glukoze niske i laktoze visoke ili kada su obe na srednjem nivou (videti četvrto i peto pravilo). Abducibles A, proglasi sve kopnene instance predikatima "količina" kao assumable. To pokazuje da u modelu iznosi u bilo koje doba raznih supstanci su nepoznati. To je nepotpuna informacija koja treba da se utvrdi u svakom problemu slučaju. Ograničenja integriteta, IC, navode da iznos bilo koje supstance (S) može uzeti samo jednu vrednost.

Domen znanje (P)

hrana(laktoza):-napraviti(premise), napraviti(galaktosidase).

napraviti(enzime):-kod(gen, enzim), izraziti(gen).

izraziti(lak(X)):-iznos(glukoza, nizak), iznos(laktoza, visok).

izraziti(lak(X)):-iznos(glukoza, srednje), iznos(laktoza, srednje).

kod(lak(y), premise).

kod(lak(z), galaktosidase).

temperatura(niska):-izraziti(glukozu, niksa).

Ograničenja integriteta (IC)

netačno :- izrazi(S,V1), izrazi(S,V2), V1 ≠ V2.

Abducibles (A)

abducibles_predikat(izrazi).

Problem cilja je G = hrana(laktoza). Ovo može nastati bilo kao posmatranja koja treba objasniti ili kao stanje stvari koje treba postići pronalaženjem plana. Ovaj cilj ima dva abduktivna objašnjenja:

\Delta _{1}=\{{\text{amount(lactose, hi), amount(glucose, low)}}\}

\Delta _{2}=\{{\text{amount(lactose, medium), amount(glucose, medium)}}\}

Odluka koje je od njih dvoje da usvoji mogu zavisiti dodatne informacije koje su dostupne, npr može da se zna da kada je nivo glukoze nizak onda organizam pokazuje određeno ponašanje - u modelu što je dodatna informacija da je temperatura organizma niska - i posmatrajući istinu ili laž o tome da je moguće izabrati prvi ili drugi objašnjenje respektivno.

Kada je objašnjenje izabrano, onda to postaje deo teorije, koja se može koristiti za crtanje novih zaključaka. Objašnjenje i uopšte ovi novi zaključci čine rešenje problema.

Formalna semantika uredi

Formalna semantika centralni pojam abductive objašnjenja u ALPu može se definisati na sledeći nači

S obzirom da abductive logika programa, $\langle P,A,{\mathit {IC}}\rangle$ , abductive objašnjenje za problem $G$ je set $\Delta$ podzemnih atoma na abducible predikata tako da je:

$P\cup \Delta \models G$
$P\cup \Delta \models IC$
$P\cup \Delta$ je konzistentna

Ova definicija ostavlja izbor osnovnih semantičkih logika programa kroz koje dajemo tačno značenje \ modela entailment odnosa i pojam doslednosti (Ektended) logičkih programa. Bilo različitih semantika logike programiranja kao što su završetak, stabilna ili dobro osnovana semantika može (i koji su korišćeni u praksi) da daju različite pojmove abductive objašnjenja i na taj način različite oblike ALP okvira.

Navedena definicija uzima poseban pogled na formalizaciju uloge ograničenja integriteta ${\mathit {IC}}$ kao ograničenja o mogućim rešenjima abduktiva. To zahteva da se oni podrazumevanom logikom produženog programa sa abductive rešenjima, tako što znači da u svakom modelu sa produženim logičkim programom (kojih može pasti na pamet kao svet što je dao $\Delta$ ) zahtevi ograničenja integriteta su ispunjeni. U nekim slučajevima to može biti nepotrebno jak i slabiji uslov doslednosti, naime $P\cup {\mathit {IC}}\cup \Delta$ je u skladu, može biti dovoljna, što znači da postoji barem jedan model (moguće usledio svetu) od proširenog programa gde su ograničenja integriteta zadržana. U praksi, u mnogim slučajevima ova dva načina formalizovanja uloga ograničenja integriteta se poklapaju, kao logike programa i njegovi nastavci uvek imaju jedinstven model. Mnogi od ALP sistema koriste entailment pogled na ograničenja integriteta, jer to može lako implementirati bez potrebe za ikakvim dodatnim specijalizovanim procedurama za zadovoljstvo ograničenja integriteta, jer ovo gledište tretira ograničenja na isti način kao i problem cilja. Imajte na umu da u mnogim praktičnim slučajevima treći uslov u ovom formalnom definicijom abductive objašnjenja u ALP je bilo trivijalno zadovoljen ili je sadržano u drugom stanju preko korišćenja posebnih ograničenja integriteta za snimanje doslednosti.

Implementacija i sistemi uredi

Većina implementacija ALP produži SLD rezolucije zasnovane na računarskom modelu logike programiranja. ALP takođe može biti implementiran putem svog linka na Odgovor Set programiranje (ASP), gde se mogu koristiti ASP sistemi. Primeri sistema bivšeg pristupa su ACLP, A-sistem, CIFF, SCIFF, ABDUAL i ProLogICA.

Vidi još uredi

Literatura uredi

Poole, D.; Goebel, R.; Aleliunas, R. (1987). „Theorist: a logical reasoning system for defaults and diagnosis”. Ur.: Cercone, Nick; McCalla, Gordon. The Knowledge Frontier: Essays in the Representation of Knowledge. Springer. str. 331—352. ISBN 978-0-387-96557-4.
Kakas, A.C.; Mancarella, P. (1990). „Generalised Stable Models: A Semantics for Abduction”. Ur.: Aiello, L.C. ECAI 90: proceedings of the 9th European Conference on Artificial Intelligence. Pitman. str. 385—391. ISBN 9780273088226.
Console, L.; Dupre, D.T.; Torasso, P. (1991). „On the Relationship between Abduction and Deduction”. J Logic Computation. 1 (5): 661—690. doi:10.1093/logcom/1.5.661.
Kakas, A.C.; Kowalski, R.A.; Toni, F. (1993). „Abductive Logic Programming”. J Logic Computation. 2 (6): 719—770. doi:10.1093/logcom/2.6.719.
Denecker, Marc; De Schreye, Danny (1998). „SLDNFA: An Abductive Procedure for Abductive Logic Programs”. J. Logic Programming. 34 (2): 111—167. CiteSeerX 10.1.1.21.6503  . doi:10.1016/S0743-1066(97)00074-5.
Denecker, M.; Kakas, A.C. (2000). „Special issue: abductive logic programming”. J. Logic Programming. 44 (1-3): 1—4. doi:10.1016/S0743-1066(99)00078-3.
Denecker, M.; Kakas, A.C. (2002). „Abduction in Logic Programming”. Ur.: Kakas, A.C.; Sadri, F. Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski. Lecture notes in computer science. 2407. Springer. str. 402—437. ISBN 978-3-540-43959-2.
Poole, D. (1993). „Probabilistic Horn abduction and Bayesian networks” (PDF). Artificial Intelligence. 64 (1): 81—129. doi:10.1016/0004-3702(93)90061-F.
Esposito, F.; Ferilli, S.; Basile, T.M.A.; Di Mauro, N. (2007). „Inference of abduction theories for handling incompleteness in first-order learning” (PDF). Knowl. Inf. Syst. 11 (2): 217—242. doi:10.1007/s10115-006-0019-5. Arhivirano iz originala (PDF) 17. 07. 2011. g. Pristupljeno 22. 12. 2016.

Spoljašnje veze uredi

ACLP Arhivirano na sajtu Wayback Machine (3. mart 2016)
ACL
SCIFF
Asystem