Abduktiv logikprogrammering

Abduktiv logikprogrammering ( ALP ) är ett ramverk för kunskapsrepresentation på hög nivå som kan användas för att lösa problem deklarativt baserat på abduktivt resonemang . Den utökar normal logikprogrammering genom att tillåta vissa predikat att vara ofullständigt definierade, deklarerade som abducerbara predikat. Problemlösning åstadkoms genom att härleda hypoteser på dessa abducerbara predikat (abduktiva hypoteser) som lösningar på problem som ska lösas. Dessa problem kan antingen vara observationer som behöver förklaras (som i klassisk abduktion) eller mål som ska uppnås (som i normal logisk programmering ). Det kan användas för att lösa problem inom diagnos, planering , naturligt språk och maskininlärning . Det har också använts för att tolka negation som misslyckande som en form av abduktivt resonemang.

Syntax

Abduktiva logikprogram har tre komponenter, $\langle P,A,IC\rangle ,$ där:

P är ett logikprogram av exakt samma form som i logikprogrammering
A är en uppsättning predikatnamn, kallade abducerbara predikat
IC är en uppsättning av första ordningens klassiska formler.

Normalt innehåller inte logikprogrammet P några satser vars huvud (eller slutsats) refererar till ett abducerbart predikat. (Denna begränsning kan göras utan förlust av allmänhet.) Också i praktiken, många gånger, integritetsbegränsningarna i IC ofta begränsade till formen av förnekelser, dvs. klausuler av formen:

falskt:- A1,...,An, inte B1, ..., inte Bm.

En sådan begränsning innebär att det inte är möjligt för alla A1,...,An att vara sanna och samtidigt alla B1,...,Bm att vara falska.

Informell mening och problemlösning

Klausulerna i P definierar en uppsättning icke-abducerbara predikat och genom detta ger de en beskrivning (eller modell) av problemdomänen. Integritetsbegränsningarna i IC anger allmänna egenskaper för problemdomänen som måste respekteras vid varje lösning av ett problem.

Ett problem, G , som uttrycker antingen en observation som behöver förklaras eller ett mål som önskas, representeras av en konjunktion av positiva och negativa (NAF) bokstaver. Sådana problem löses genom att beräkna "abduktiva förklaringar" av G .

En abduktiv förklaring av ett problem G är en uppsättning positiva (och ibland även negativa) markinstanser av de abducerbara predikaten, så att, när dessa läggs till det logiska programmet P, gäller både problemet G och integritetsbegränsningarna IC. Abduktiva förklaringar utökar således logikprogrammet P genom tillägg av fullständiga eller partiella definitioner av de abducerbara predikaten. På så sätt bildar abduktiva förklaringar lösningar på problemet enligt beskrivningen av problemdomänen i P och IC. Utvidgningen eller kompletteringen av problembeskrivningen som ges av de abduktiva förklaringarna ger ny information, som hittills inte ingår i lösningen på problemet. Kvalitetskriterier för att föredra en lösning framför en annan, ofta uttryckta via integritetsbegränsningar, kan tillämpas för att välja specifika abduktiva förklaringar av problemet G .

Beräkning i ALP kombinerar bakåtresonemang av normal logikprogrammering (för att reducera problem till delproblem) med en sorts integritetskontroll för att visa att de abduktiva förklaringarna uppfyller integritetsbegränsningarna.

Följande två exempel, skrivna på enkel strukturerad engelska snarare än i den strikta syntaxen för ALP, illustrerar begreppet abduktiv förklaring i ALP och dess relation till problemlösning.

Exempel 1

Det abduktiva logiska programmet, $\langle P,A,{\mathit {IC}}\rangle$ , har i $P$ följande meningar:



 Gräset är blött  om  det regnar.  Gräset är blött  om  sprinklern var på.  Solen sken.

De abducerbara predikaten i $A$ är "det regnade" och "sprinklern var på" och den enda integritetsbegränsningen i ${\mathit {IC}}$ är:

 falskt  om  det regnade och solen sken.

Observationen att gräset är blött har två potentiella förklaringar, "det regnade" och "sprinklern var på", som medför observationen. Men bara den andra potentiella förklaringen, "sprinklern var på", uppfyller integritetsbegränsningen.

Exempel 2

Betrakta det abduktiva logikprogrammet som består av följande (förenklade) satser:





 X är medborgare  om  X är född i USA.  X är medborgare  om  X är född utanför USA  och  X är bosatt i USA  och  X är naturaliserad.  X är medborgare  om  X är född utanför USA  och  Y är mamma till X  och  Y är medborgare  och  X är registrerad.  Mary är mor till John.  Mary är medborgare.

tillsammans med de fem abducerbara predikaten, "är född i USA", "är född utanför USA", "är bosatt i USA", "är naturaliserad" och "är registrerad" och integritetsbegränsningen:

 falskt  om  John är bosatt i USA.

Målet "John är medborgare" har två abduktiva lösningar, varav en är "John är född i USA", den andra är "John är född utanför USA" och "John är registrerad". Den potentiella lösningen att bli medborgare genom bosättning och naturalisering misslyckas eftersom det bryter mot integritetsbegränsningen.

Ett mer komplext exempel som också skrivs i den mer formella syntaxen för ALP är följande.

Exempel 3

Det abduktiva logikprogrammet nedan beskriver en enkel modell av laktosmetabolismen hos bakterien E. coli. Programmet, P , beskriver (i sin första regel) att E. coli kan livnära sig på sockret laktos om det gör två enzymer permeas och galaktosidas. Liksom alla enzymer tillverkas dessa om de kodas av en gen (gen) som uttrycks (beskrivs av den andra regeln). De två enzymerna permeas och galaktosidas kodas av två gener, lac(y) respektive lac(z) (anges i programmets femte och sjätte regel), i ett kluster av gener (lac(X)) – som kallas en operon – det uttrycks när mängderna (amt) glukos är låga och laktos är höga eller när de båda är på medelhög nivå (se den fjärde och femte regeln). Abducibles, A , förklarar alla markinstanser av predikaten "belopp" som antagliga. Detta speglar att i modellen är mängderna vid varje tidpunkt av de olika ämnena okända. Detta är ofullständig information som ska fastställas i varje problemfall. Integritetsbegränsningarna, IC , anger att mängden av något ämne (S) bara kan ta ett värde.

Domänkunskap (P)

      
       
        
        
    
    
       foder  (  laktos  )  :-  göra  (  permeas  ),  göra  (  galaktosidas  ).  göra  (  Enzym  )  :-  kod  (  Gen  ,  Enzym  ),  uttryck  (  Gen  ).  express  (  lac  (  X  ))  :-  mängd  (  glukos  ,  låg  ),  mängd  (  laktos  ,  hi  ).  express  (  lac  (  X  ))  :-  mängd  (  glukos  ,  medium  ),  mängd  (  laktos  ,  medium  ).  kod  (  lac  (  y  ),  permease  ).  kod  (  lac  (  z  ),  galaktosidas  ).  temperatur  (  låg  )  :-  mängd  (  glukos  ,  låg  ).

Integritetsbegränsningar (IC)

            falskt  :-  mängd  (  S  ,  V1  ),  mängd  (  S  ,  V2  ),  V1  ≠  V2  .

Abducibles (A)

    abducible_predicate  (  mängd  ).

Problemmålet är $G={\text{foder(laktos)}}$ . Detta kan uppstå antingen som en observation som ska förklaras eller som ett tillstånd som ska uppnås genom att hitta en plan. Detta mål har två abduktiva förklaringar:

{\begin{cases}\Delta _{ 1}=\{{\text{mängd(laktos, hej), mängd(glukos, låg)}}\}\\\Delta _{2}=\{{\text{mängd(laktos, medium), mängd( glukos, medium)}}\}\end{case}}

Beslutet vilken av de två som ska antas kan bero på ytterligare information som finns tillgänglig, t.ex. kan det vara känt att när glukosnivån är låg så uppvisar organismen ett visst beteende – i modellen är sådan ytterligare information att temperaturen på organismen är låg – och genom att observera sanningen eller falskheten i detta är det möjligt att välja den första respektive andra förklaringen.

När en förklaring väl har valts blir denna en del av teorin, som kan användas för att dra nya slutsatser. Förklaringen och mer generellt dessa nya slutsatser utgör lösningen på problemet.

Formell semantik

Den formella semantiken för den centrala föreställningen om en abduktiv förklaring i ALP kan definieras på följande sätt.

Givet ett abduktivt logikprogram, ${\displaystyle \langle P,A,{\mathit {IC}}\rangle } , är$ en abduktiv förklaring till ett problem $G$ en mängd $\Delta$ av markatomer på abducerbara predikat så att:

$P\cup \Delta \models G$
$P\cup \Delta \models IC$
$P\cup \Delta$ är konsekvent

Denna definition lämnar öppet valet av den underliggande semantiken för logisk programmering genom vilken vi ger den exakta innebörden av entailment-relationen $\models$ och begreppet konsistens hos de (utökade) logikprogrammen. Vilken som helst av de olika semantikerna inom logisk programmering såsom kompletterings-, stabil eller välgrundad semantik kan (och har använts i praktiken) för att ge olika föreställningar om abduktiva förklaringar och därmed olika former av ALP-ramverk.

Ovanstående definition har en speciell syn på formaliseringen av rollen för integritetsbegränsningarna ${\mathit {IC}}$ som restriktioner för möjliga abduktiva lösningar. Det kräver att dessa omfattas av logikprogrammet utökat med en abduktiv lösning, vilket betyder att i vilken modell som helst av det utökade logikprogrammet (som man kan tänka sig som en påföljande värld givet Δ {\displaystyle \Delta } $kraven$ i integritetsbegränsningar är uppfyllda. I vissa fall kan detta vara onödigt starkt och det svagare kravet på konsistens, nämligen att $P\cup {\mathit {IC}}\cup \Delta$ är konsekvent, kan vara tillräckligt, vilket innebär att det finns minst en modell (möjlig efterföljande värld) av det utökade programmet där integritetsbegränsningarna gäller. I praktiken sammanfaller i många fall dessa två sätt att formalisera integritetsbegränsningarnas roll eftersom logikprogrammet och dess tillägg alltid har en unik modell. Många av ALP-systemen använder medföljande syn på integritetsbegränsningarna eftersom detta enkelt kan implementeras utan behov av några extra specialiserade procedurer för att tillfredsställa integritetsbegränsningarna eftersom denna syn behandlar begränsningarna på samma sätt som problemmålet. I många praktiska fall är det tredje villkoret i denna formella definition av en abduktiv förklaring i ALP antingen trivialt uppfyllt eller så finns det i det andra villkoret genom användning av specifika integritetsbegränsningar som fångar överensstämmelse.

Implementering och system

De flesta av implementeringarna av ALP utökar den SLD-upplösningsbaserade beräkningsmodellen för logisk programmering. ALP kan också implementeras genom sin koppling till Answer Set Programming (ASP), där ASP-systemen kan användas. Exempel på system av det tidigare tillvägagångssättet är ACLP, A-system, CIFF, SCIFF, ABDUAL och ProLogICA.

Se även

Induktiv logikprogrammering

Anteckningar

Poole, D.; Goebel, R.; Aleliunas, R. (1987). "Teoretiker: ett logiskt resonemangssystem för standarder och diagnoser" . I Cercone, Nick; McCalla, Gordon (red.). The Knowledge Frontier: Essays in the representation of Knowledge . Springer. s. 331–352. ISBN 978-0-387-96557-4 .
Kakas, AC; Mancarella, P. (1990). "Generaliserade stabila modeller: En semantik för bortförande". I Aiello, LC (red.). ECAI 90: förfaranden för den nionde europeiska konferensen om artificiell intelligens . Pitman. s. 385–391. ISBN 978-0273088226 .
Console, L.; Dupre, DT; Torasso, P. (1991). "Om förhållandet mellan bortförande och avdrag". Journal of Logic and Computation . 1 (5): 661-690. CiteSeerX 10.1.1.31.9982 . doi : 10.1093/logcom/1.5.661 .
Kakas, AC; Kowalski, RA; Toni, F. (1993). "Abduktiv logikprogrammering". Journal of Logic and Computation . 2 (6): 719–770. CiteSeerX 10.1.1.37.3655 . doi : 10.1093/logcom/2.6.719 .
Denecker, Marc; De Schreye, Danny (februari 1998). "SLDNFA: En abduktiv procedur för abduktiva logikprogram". Journal of Logic Programming . 34 (2): 111–167. CiteSeerX 10.1.1.21.6503 . doi : 10.1016/S0743-1066(97)00074-5 .
Denecker, M.; Kakas, AC (juli 2000). "Specialfråga: abduktiv logikprogrammering" . Journal of Logic Programming . 44 (1–3): 1–4. doi : 10.1016/S0743-1066(99)00078-3 .
Denecker, M.; Kakas, AC (2002). "Abduktion i logisk programmering" . I Kakas, AC; Sadri, F. (red.). Computational Logic: Logic Programming and Beyond: Essays in Honor of Robert A. Kowalski . Föreläsningsanteckningar i datavetenskap. Vol. 2407. Springer. s. 402–437. ISBN 978-3-540-43959-2 .
Poole, D. (1993). "Probabilistisk hornbortförande och Bayesianska nätverk" (PDF) . Artificiell intelligens . 64 (1): 81–129. doi : 10.1016/0004-3702(93)90061-F .
Esposito, F.; Ferilli, S.; Basile, TMA; Di Mauro, N. (februari 2007). "Inferens av abduktionsteorier för hantering av ofullständighet i första ordningens lärande" ( PDF) . Knowl. Inf. Syst . 11 (2): 217–242. doi : 10.1007/s10115-006-0019-5 . S2CID 10699982 . Arkiverad från originalet (PDF) 2011-07-17.

externa länkar