Programowanie logiki abdukcyjnej - Abductive logic programming

Programowanie w logice abdukcyjnej ( ALP ) to struktura reprezentacji wiedzy wysokiego poziomu, której można używać do rozwiązywania problemów deklaratywnie opartych na rozumowaniu abdukcyjnym . Rozszerza normalne programowanie logiczne , pozwalając na niekompletne zdefiniowanie niektórych predykatów, zadeklarowanych jako predykaty podlegające. Rozwiązywanie problemów jest dokonywane przez wyprowadzenie hipotez na podstawie tych predykatów abdukcyjnych (hipotez abdukcyjnych) jako rozwiązań problemów do rozwiązania. Problemy te mogą być albo obserwacjami, które trzeba wyjaśnić (jak w klasycznym uprowadzeniu) lub celami do osiągnięcia (jak w normalnym programowaniu logicznym ). Może służyć do rozwiązywania problemów w diagnostyce, planowaniu , języku naturalnym i uczeniu maszynowym . Jest również używany do interpretowania negacji jako niepowodzenia jako formy rozumowania abdukcyjnego.

Składnia

Programy logiki abdukcyjnej składają się z trzech komponentów, gdzie: ${\ Displaystyle \ langle P, A, IC \ rangle ,}$

• P to program logiczny o dokładnie takiej samej formie jak w programowaniu logicznym
• A jest zbiorem nazw predykatów, zwanych predykatami przyswajalnymi
• IC to zbiór klasycznych formuł pierwszego rzędu.

Normalnie program logiczny P nie zawiera żadnych klauzul, których nagłówek (lub konkluzja) odnosi się do predykatu dającego się przyswoić. (To ograniczenie można wprowadzić bez utraty ogólności.) Również w praktyce, w wielu przypadkach, ograniczenia integralności w IC są często ograniczone do postaci zaprzeczeń, tj. klauzul o postaci:

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

Takie ograniczenie oznacza, że ​​nie jest możliwe, aby wszystkie A1,...,An były prawdziwe i jednocześnie wszystkie B1,...,Bm były fałszywe.

Nieformalne znaczenie i rozwiązywanie problemów

Klauzule w P definiują zbiór predykatów niepodlegających abdukcji i przez to dostarczają opisu (lub modelu) dziedziny problemu. Ograniczenia integralności w IC określają ogólne właściwości domeny problemu, które muszą być przestrzegane przy każdym rozwiązaniu problemu.

Problem G , który wyraża albo obserwację wymagającą wyjaśnienia, albo pożądany cel, jest reprezentowany przez połączenie literałów pozytywnych i negatywnych (NAF). Takie problemy są rozwiązywane przez obliczanie "abdukcyjnych wyjaśnień" G .

Abdukcyjne wyjaśnienie problemu G jest zbiorem pozytywnych (a czasem także negatywnych) podstawowych wystąpień predykatów uprowadzalnych, takich, że gdy są one dodawane do programu logicznego P, zarówno problem G, jak i ograniczenia integralności IC są utrzymywane. Zatem wyjaśnienia abdukcyjne rozszerzają program logiczny P przez dodanie pełnych lub częściowych definicji predykatów uprowadzalnych. W ten sposób wyjaśnienia abdukcyjne tworzą rozwiązania problemu zgodnie z opisem dziedziny problemu w P i IC. Rozszerzenie lub uzupełnienie opisu problemu podanego przez wyjaśnienia abdukcyjne dostarcza nowych informacji, dotychczas nie zawartych w rozwiązaniu problemu. Kryteria jakości preferujące jedno rozwiązanie nad drugim, często wyrażane przez ograniczenia integralności, mogą być zastosowane do wybrania konkretnych abdukcyjnych wyjaśnień problemu G .

Obliczenia w ALP łączą wsteczne rozumowanie normalnego programowania logicznego (w celu zredukowania problemów do podproblemów) z rodzajem sprawdzania integralności, aby pokazać, że wyjaśnienia abdukcyjne spełniają ograniczenia integralności.

Poniższe dwa przykłady, napisane prostym ustrukturyzowanym językiem angielskim, a nie ścisłą składnią ALP, ilustrują pojęcie abdukcyjnego wyjaśniania w ALP i jego związek z rozwiązywaniem problemów.

Przykład 1

Program logiki abdukcyjnej, , ma następujące zdania: ${\ Displaystyle \ langle P A {\ mathit {IC}} \ rangle}$${\displaystyle P}$

  Grass is wet if it rained.

  Grass is wet if the sprinkler was on.

  The sun was shining.

Predykaty abducible to „padał deszcz” i „zraszacz był włączony”, a jedynym ograniczeniem integralności jest: ${\ Displaystyle A}$${\displaystyle {\mathit {IC}}}$

  false if it rained and the sun was shining.

Obserwacja, że ​​trawa jest mokra ma dwa potencjalne wytłumaczenia: „padało” i „zraszacz był włączony”, co pociąga za sobą obserwację. Jednak tylko drugie potencjalne wyjaśnienie, „zraszacz był włączony”, spełnia ograniczenie integralności.

Przykład 2

Rozważmy program logiki abdukcyjnej składający się z następujących (uproszczonych) klauzul:

  X is a citizen if X is born in the USA.

  X is a citizen if X is born outside the USA and X is a resident of the USA and X is naturalized.

  X is a citizen if X is born outside the USA and Y is the mother of X and Y is a citizen and X is registered.

  Mary is the mother of John.

  Mary is a citizen.

wraz z pięcioma predykatami przyswajalnymi, „urodził się w USA”, „urodził się poza USA”, „jest mieszkańcem USA”, „jest naturalizowany” i „jest zarejestrowany” oraz ograniczeniem integralności:

  false if John is a resident of the USA.

Cel „Jan jest obywatelem” ma dwa rozwiązania abdukcyjne, z których jedno to „Jan urodził się w USA”, drugie to „Jan urodził się poza USA” i „Jan jest zarejestrowany”. Potencjalne rozwiązanie polegające na uzyskaniu obywatelstwa przez miejsce zamieszkania i naturalizację zawodzi, ponieważ narusza ograniczenie integralności.

Bardziej złożony przykład, który jest również napisany w bardziej formalnej składni ALP, jest następujący.

Przykład 3

Poniższy program logiki abdukcyjnej opisuje prosty model metabolizmu laktozy bakterii E. coli. Program P opisuje (w swojej pierwszej zasadzie), że E. coli może żywić się laktozą cukrową, jeśli wytwarza dwa enzymy permeazę i galaktozydazę. Jak wszystkie enzymy, są one wytwarzane, jeśli są kodowane przez gen (Gene), który ulega ekspresji (opisany w drugiej regule). Dwa enzymy permeazy i galaktozydazy są kodowane przez dwa geny, odpowiednio lac(y) i lac(z) (wymienione w piątej i szóstej regule programu), w klastrze genów (lac(X)) – zwanym operon – wyrażany, gdy ilość (amt) glukozy jest niska, a laktoza wysoka lub gdy obie są na średnim poziomie (patrz zasada czwarta i piąta). Abducibles, A , deklarują wszystkie podstawowe instancje predykatów „ilość” jako możliwe do przyjęcia. Odzwierciedla to, że w modelu ilości w dowolnym momencie różnych substancji są nieznane. Jest to niepełna informacja, którą należy ustalić w każdym przypadku problemowym. Ograniczenia integralności IC , stwierdzają, że ilość dowolnej substancji (S) może przyjąć tylko jedną wartość.

Wiedza dziedzinowa (P)

   feed(lactose) :- make(permease), make(galactosidase).
   make(Enzyme) :- code(Gene, Enzyme), express(Gene).
   express(lac(X)) :- amount(glucose, low), amount(lactose, hi).
   express(lac(X)) :- amount(glucose, medium), amount(lactose, medium).
   code(lac(y), permease).
   code(lac(z), galactosidase).
   temperature(low) :- amount(glucose, low).

Ograniczenia integralności (IC)

   false :- amount(S, V1), amount(S, V2), V1 ≠ V2.

Odwodzenia (A)

   abducible_predicate(amount).

Celem problemu jest . Może to wynikać albo z obserwacji do wyjaśnienia, albo jako stanu rzeczy do osiągnięcia poprzez znalezienie planu. Ten cel ma dwa abdukcyjne wyjaśnienia: ${\ Displaystyle G = {\ tekst {pasza (laktoza)}}}$

${\ Displaystyle {\ zacząć {przypadki} \ Delta _ {1} = \ {{\ tekst {ilość (laktoza, cześć), ilość (glukoza, niski)}} \} \ \ \ Delta _ {2} = \ { {\text{ilość(laktoza, medium), ilość(glukoza, medium)}}\}\end{przypadki}}}$

Decyzja, który z nich przyjąć może zależeć od dodatkowych informacji, które są dostępne, np. może być wiadome, że gdy poziom glukozy jest niski, organizm zachowuje się w określony sposób – w modelu taką dodatkową informacją jest to, że temperatura ciała organizm jest niski – i obserwując prawdziwość lub fałsz tego można wybrać odpowiednio pierwsze lub drugie wyjaśnienie.

Po wybraniu wyjaśnienia staje się ono częścią teorii, którą można wykorzystać do wyciągnięcia nowych wniosków. Wyjaśnienie i bardziej ogólnie te nowe wnioski stanowią rozwiązanie problemu.

Semantyka formalna

Formalną semantykę centralnego pojęcia wyjaśnienia abdukcyjnego w ALP można zdefiniować w następujący sposób.

Biorąc pod uwagę program logiki abdukcyjnej , abdukcyjnym wyjaśnieniem problemu jest zbiór atomów podstawowych na predykatach abdukcyjnych, taki, że: ${\ Displaystyle \ langle P A {\ mathit {IC}} \ rangle}$${\ Displaystyle G}$${\ Displaystyle \ Delta}$

• ${\ Displaystyle P \ puchar \ Delta \ modele G}$
• ${\ Displaystyle P \ puchar \ Delta \ modele IC}$
• ${\ Displaystyle P \ filiżanka \ Delta}$jest spójny

Ta definicja pozostawia otwarty wybór podstawowej semantyki programowania logicznego, poprzez którą nadajemy dokładne znaczenie relacji implikacji i pojęcie spójności (rozszerzonych) programów logicznych. Każda z różnych semantyk programowania logicznego, takich jak uzupełnianie, stabilna lub dobrze ugruntowana semantyka, może (i była używana w praktyce) dawać różne pojęcia wyjaśnień abdukcyjnych, a tym samym różne formy ram ALP. ${\displaystyle \modele}$

Powyższa definicja przyjmuje szczególny pogląd na sformalizowanie roli ograniczeń integralności jako ograniczeń możliwych rozwiązań abdukcyjnych. Wymaga to, aby były one zawarte w programie logicznym rozszerzonym o rozwiązanie abdukcyjne, co oznacza, że ​​w każdym modelu rozszerzonego programu logicznego (który można traktować jako dany świat wynikowy ) wymagania więzów integralności są spełnione. W niektórych przypadkach może to być niepotrzebnie silne, a słabsze wymaganie spójności, a mianowicie spójność, może wystarczyć, co oznacza, że ​​istnieje co najmniej jeden model (możliwy następujący świat) rozszerzonego programu, w którym występują ograniczenia integralności. W praktyce w wielu przypadkach te dwa sposoby sformalizowania roli ograniczeń integralności są zbieżne, ponieważ program logiczny i jego rozszerzenia zawsze mają unikalny model. Wiele systemów ALP wykorzystuje widok pociągania ograniczeń integralności, ponieważ można go łatwo wdrożyć bez potrzeby stosowania dodatkowych specjalistycznych procedur w celu spełnienia ograniczeń integralności, ponieważ widok ten traktuje ograniczenia w taki sam sposób, jak cel problemu. W wielu praktycznych przypadkach trzeci warunek w tej formalnej definicji abdukcyjnego wyjaśnienia w ALP jest albo trywialnie spełniony, albo jest zawarty w drugim warunku poprzez użycie specyficznych ograniczeń integralności, które wychwytują spójność. ${\displaystyle {\mathit {IC}}}$${\ Displaystyle \ Delta}$${\ Displaystyle P \ filiżanka {\ mathit {IC}} \ filiżanka \ delta}$

Wdrożenia i systemy

Większość implementacji ALP rozszerza model obliczeniowy programowania logicznego oparty na rozdzielczości SLD. ALP może być również zaimplementowana poprzez jego połączenie z Programowaniem Zestawów Odpowiedzi (ASP), gdzie można zastosować systemy ASP. Przykładami systemów pierwszego podejścia są ACLP, A-system, CIFF, SCIFF, ABDUAL i ProLogICA.

Zobacz też

• Rozumowanie abdukcyjne
• Programowanie zestawu odpowiedzi
• Programowanie logiki indukcyjnej
• Negacja jako porażka
• Argumentacja

Uwagi

Bibliografia

Zewnętrzne linki

• ACLP
• ACL
• SCIFF
• System