Абдуктивна логика програмирања

Абдуктивна логика програмирања (АЛП) је на високом нивоу знања заступљености оквира који се могу користити за решавање проблема декларативно на основу абдуктивног резоновања. Простире се нормално логика програмирања дозвољавајући неким предикатима да буду непотпуно дефинисани, проглашава их абдуцибле предикатима. Решавање проблема се врши од стране извода хипотезе о тим абдуцибле предикатима (абдуцтиве хипотеза), као решења проблема које треба решити. Ови проблеми могу бити или запажања које треба објаснити (као у класичној отмици) или циљеви које треба постићи (као у нормалном логичко програмирање). Може се користити за решавање проблема у дијагностици, планирању, природног језика и машинског учења. Такође се користе за тумачење негација као неуспех као облик абдуактив размишљања.

Синтакса

Абдуктивни логички програми имају три компоненте, $\langle P,A,IC\rangle ,$ где:

P је логика програма у потпуно истом облику као у логичком програмирању
А је скуп предикатских имена, звани абдукибле предиката
IC је скуп првог реда класичних формула.

Нормално, логика програма P, не садржи никакве одредбе чије главе (или закључак) се односи на абдуцибле предикате. (. Ово ограничење може се направити без губитка општости) Такође у пракси, много пута ограничења интегритета у IСу су често ограничена на форму демантија, односно клаузуле у облику:

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

Таква ограничење значе да није могуће за све А1, ..., Аn да буду истинита и истовремено све B1, ..., Bm да је лажна.

Неформалне значење и решавање проблема

Клаузуле у P дефинишу сет не-абдуцибле предиката и кроз то дају опис (или модела) домена проблема. Интегритет ограничења у IСу ће одредити опште особине домена проблема које треба да се поштују за било које рјешење проблема.

Проблем G, који изражава или примедбу која треба да се објасни или циљ који се жели, представљен је заједно позитивне и негативне (НАФ) литерале. Овакви проблеми су решени рачунањем "абдуцтиве објашњења" G.

Абдуктивно објашњење проблема G је скуп позитивних (а понекад и негативне) копнених инстанца абдукибле предиката, тако да, када се они додају у логички програм P, проблем G и ограничења интегритета IC оба га држе. Тако абдуктивна објашњења продужују логику програма P додавањем потпуним или делимичним дефиницијама абдуцибле предиката. На овај начин, абдуктивна објашњења формирају решења проблема према опису домена проблема у P и IC. Продужење или завршетак описа проблема која су абдуктивна објашњења даје нове информације, до сада нису садржани у решењу проблема. Критеријуми квалитета да преферирају једно решење у односу на друго, често изражавао преко интегритета ограничења, могу се применити да изаберете специфичне абдуктиве објашњења проблема G.

Обрачун у АЛПу комбинује уназад образложење нормалне логике програмирања (да се смањи проблеме Суб-проблеме) са неком врстом интегритета проверавања да покаже да се абдуктивна објашњења задовољавају ограничењима интегритета.

Следећа два примера, написана једноставним структурираним енглеским него строгим синтаксичким АЛП, илуструју појам абдуктивног објашњења у АЛПу и њен однос према решавању проблема.

Пример 1

Абдуктивна логика програма, $\langle P,A,{\mathit {IC}}\rangle$ , има у $P$ следеће реченице:

Трава је мокра ако је падала киша.

Трава је мокра ако је прскалица била укључена.

Сунце је сијало.

У абдуцибле предикатима у $A$ су "је падала киша" и "прскалица била укључена" и једино ограничење у интегритет ${\mathit {IC}}$ је:

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

Посматрање да је трава мокра има два потенцијална објашњења, "је падала киша" и "прскалица била укључена", који подразумева посматрање. Међутим, тек друго потенцијално објашњење ", рекао је прскалица била укњучена" задовољава интегритет ограничења.

Пример 2

Размотримо абдуктивну логику програма који се састоји од следећих (Симплифиед) клаузула:

X је грађанин ако X је рођен у САДу.

X је држављанин, ако је X рођен изван САД и X је становник САД и X је натурализовани.

X је грађанин ако X је рођен изван САД и Y је мајка од X и Y је држављанин и X је регистрован.

Мери је Џонова мајка.

Мери је грађанин.

заједно са пет абдуцибле предиката "је рођен у САД", "је рођен изван САД", "је становник САД", "је натурализовани" и "регистровани и интегритет ограничење:

лаж ако је Џон становник САД.

Циљ "Џон је грађанин" има два абдуктивна решења, од којих је један "Џон је рођен у САДу", други је "Џон је рођен изван САДа" и "Џон је регистрован". Он потенцијално решење да постане грађанин од боравка и да добије држављанство.

Сложенији пример који је такође записан у формалној синтакси АЛП је следећи.

Пример 3

Абдуктивна логика програма испод описује једноставан модел лактозе метаболизма бактерија Е. цоли. Програм P, описује (у свом првом правилу) да се Е. цоли може хранити шећером лактозе, ако то чине два ензима пермеасе и галактозидазу. Као и сви ензими, оне су направљене ако су кодиране од стране гена (Гене) који се изражава (описан од стране другог правилу). Два ензиме пермеаса и галактозидазе су кодирани од два гена, Лац (и) и Лац (z) (наведених у петој и шестој владавини програма), у кластеру гена (Лац (x)) - зове Оперон - који се изражава када су количине (АМТ) глукозе ниске и лактозе високе или када су обе на средњем нивоу (видети четврто и пето правило). Абдуциблес А, прогласи све копнене инстанце предикатима "количина" као ассумабле. То показује да у моделу износи у било које доба разних супстанци су непознати. То је непотпуна информација која треба да се утврди у сваком проблему случају. Ограничења интегритета, IC, наводе да износ било које супстанце (S) може узети само једну вредност.

Домен знање (P)

храна(лактоза):-направити(премисе), направити(галактосидасе).

направити(ензиме):-код(ген, ензим), изразити(ген).

изразити(лак(X)):-износ(глукоза, низак), износ(лактоза, висок).

изразити(лак(X)):-износ(глукоза, средње), износ(лактоза, средње).

код(лак(y), премисе).

код(лак(z), галактосидасе).

температура(ниска):-изразити(глукозу, никса).

Ограничења интегритета (IC)

нетачно :- изрази(S,V1), изрази(S,V2), V1 ≠ V2.

Абдуциблес (A)

абдуциблес_предикат(изрази).

Проблем циља је G = храна(лактоза). Ово може настати било као посматрања која треба објаснити или као стање ствари које треба постићи проналажењем плана. Овај циљ има два абдуктивна објашњења:

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

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

Одлука које је од њих двоје да усвоји могу зависити додатне информације које су доступне, нпр може да се зна да када је ниво глукозе низак онда организам показује одређено понашање - у моделу што је додатна информација да је температура организма ниска - и посматрајући истину или лаж о томе да је могуће изабрати први или други објашњење респективно.

Када је објашњење изабрано, онда то постаје део теорије, која се може користити за цртање нових закључака. Објашњење и уопште ови нови закључци чине решење проблема.

Формална семантика

Формална семантика централни појам абдуцтиве објашњења у АЛПу може се дефинисати на следећи начи

С обзиром да абдуцтиве логика програма, $\langle P,A,{\mathit {IC}}\rangle$ , абдуцтиве објашњење за проблем $G$ је сет $\Delta$ подземних атома на абдуцибле предиката тако да је:

$P\cup \Delta \models G$
$P\cup \Delta \models IC$
$P\cup \Delta$ је конзистентна

Ова дефиниција оставља избор основних семантичких логика програма кроз које дајемо тачно значење \ модела ентаилмент односа и појам доследности (Ектендед) логичких програма. Било различитих семантика логике програмирања као што су завршетак, стабилна или добро основана семантика може (и који су коришћени у пракси) да дају различите појмове абдуцтиве објашњења и на тај начин различите облике АЛП оквира.

Наведена дефиниција узима посебан поглед на формализацију улоге ограничења интегритета ${\mathit {IC}}$ као ограничења о могућим решењима абдуктива. То захтева да се они подразумеваном логиком продуженог програма са абдуцтиве решењима, тако што значи да у сваком моделу са продуженим логичким програмом (којих може пасти на памет као свет што је дао $\Delta$ ) захтеви ограничења интегритета су испуњени. У неким случајевима то може бити непотребно јак и слабији услов доследности, наиме $P\cup {\mathit {IC}}\cup \Delta$ је у складу, може бити довољна, што значи да постоји барем један модел (могуће уследио свету) од проширеног програма где су ограничења интегритета задржана. У пракси, у многим случајевима ова два начина формализовања улога ограничења интегритета се поклапају, као логике програма и његови наставци увек имају јединствен модел. Многи од АЛП система користе ентаилмент поглед на ограничења интегритета, јер то може лако имплементирати без потребе за икаквим додатним специјализованим процедурама за задовољство ограничења интегритета, јер ово гледиште третира ограничења на исти начин као и проблем циља. Имајте на уму да у многим практичним случајевима трећи услов у овом формалном дефиницијом абдуцтиве објашњења у АЛП је било тривијално задовољен или је садржано у другом стању преко коришћења посебних ограничења интегритета за снимање доследности.

Имплементација и системи

Већина имплементација АЛП продужи СЛД резолуције засноване на рачунарском моделу логике програмирања. АЛП такође може бити имплементиран путем свог линка на Одговор Сет програмирање (АСП), где се могу користити АСП системи. Примери система бившег приступа су АЦЛП, А-систем, ЦИФФ, СЦИФФ, АБДУАЛ и ПроЛогИЦА.

Види још

Литература

Poole, D.; Goebel, R.; Aleliunas, R. (1987). „Theorist: a logical reasoning system for defaults and diagnosis”. Ур.: Cercone, Nick; McCalla, Gordon. The Knowledge Frontier: Essays in the Representation of Knowledge. Springer. стр. 331—352. ISBN 978-0-387-96557-4.
Kakas, A.C.; Mancarella, P. (1990). „Generalised Stable Models: A Semantics for Abduction”. Ур.: Aiello, L.C. ECAI 90: proceedings of the 9th European Conference on Artificial Intelligence. Pitman. стр. 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”. Ур.: 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. стр. 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. Архивирано из оригинала (PDF) 17. 07. 2011. г. Приступљено 22. 12. 2016.

Спољашње везе

ACLP Архивирано на сајту Wayback Machine (3. март 2016)
ACL
SCIFF
Asystem