Programowanie logiki indukcyjnej - Inductive logic programming

Paradygmaty programowania
Akcja Zorientowany na agenta Zorientowany na tablicę Oparte na automatach Obliczenia współbieżne Programowanie relatywistyczne Oparty na danych Deklaratywny (kontrast: Tryb rozkazujący ) Funkcjonalny Logika funkcjonalna Czysto funkcjonalny Logika Logika abdukcyjna Zestaw odpowiedzi Logika współbieżna Logika funkcjonalna Logika indukcyjna Ograniczenie Logika ograniczeń Współbieżna logika ograniczeń Przepływ danych Oparte na przepływie Reaktywny Funkcjonalny reaktywny Ontologia Różnicowalny Dynamiczne/skryptowe Oparte na wydarzeniach Poziom funkcji (kontrast: Poziom wartości ) Bezpunktowy styl Konkatenatywny Ogólny Tryb rozkazujący (kontrast: deklaratywny ) Proceduralny Zorientowany obiektowo Polimorficzny Zamierzony Zorientowany na język Specyficzne dla domeny Piśmienny Programowanie w języku naturalnym Metaprogramowanie Automatyczny Programowanie indukcyjne Odblaskowy Zorientowany na atrybut Makro Szablon Bez struktury (kontrast: Strukturalny ) Szyk Niedeterministyczny Równoległe obliczenia Zorientowany na proces probabilistyczny Kwant Teoria mnogości Oparte na stosie Strukturalny (kontrast: niestrukturalny ) Struktura blokowa Strukturalna współbieżność Zorientowany obiektowo Aktorski Oparte na klasach Równoległy Oparte na prototypie Poprzez oddzielenie obaw : Zorientowany na aspekt Zorientowany na role Zorientowany na przedmiot Rekursywny Symboliczny Poziom wartości (kontrast: Poziom funkcji )
v T mi

Programowanie logiki indukcyjnej ( ILP ) to poddziedzina sztucznej inteligencji symbolicznej, która wykorzystuje programowanie logiczne jako jednolitą reprezentację przykładów, wiedzy podstawowej i hipotez. Biorąc pod uwagę kodowanie znanej wiedzy podstawowej i zestaw przykładów reprezentowanych jako logiczna baza danych faktów, system ILP wyprowadzi hipotetyczny program logiczny, który zawiera wszystkie pozytywne i żadne negatywne przykłady.

• Schemat: pozytywne przykłady + negatywne przykłady + podstawowa wiedza ⇒ hipoteza .

Programowanie w logice indukcyjnej jest szczególnie przydatne w bioinformatyce i przetwarzaniu języka naturalnego . Gordon Plotkin i Ehud Shapiro położyli wstępne teoretyczne podstawy dla indukcyjnego uczenia maszynowego w logicznym otoczeniu. Shapiro zbudował swoją pierwszą implementację (Model Inference System) w 1981 roku: program Prolog , który indukcyjnie wywnioskował programy logiczne z pozytywnych i negatywnych przykładów. Termin „ Programowanie w logice indukcyjnej” został po raz pierwszy wprowadzony w artykule Stephena Muggletona w 1991 roku. Muggleton zorganizował także doroczną międzynarodową konferencję na temat programowania w logice indukcyjnej, na której przedstawił teoretyczne idee inwencji predykatów, rozdzielczości odwrotnej i implikacji odwrotnej. Muggleton najpierw zaimplementował odwrotne pociąganie w systemie PROGOL . Termin „ indukcyjny ” odnosi się tutaj do indukcji filozoficznej (tj. sugerowania teorii wyjaśniającej obserwowane fakty), a nie matematycznej (tj. dowodzącej właściwości wszystkich członków dobrze uporządkowanego zbioru).

Formalna definicja

Wiedza tło jest podana jako teoria logiki B , zwykle w postaci Klauzula Horna stosowanych w programowaniu logicznym . Te pozytywne i negatywne przykłady podano w połączeniu i z unnegated i negującymi naziemnych literałach , odpowiednio. Prawidłowe hipoteza H jest propozycja logiczny, który spełnia następujące wymagania. ${\ Displaystyle E ^ {+}}$${\ Displaystyle E ^ {-}}$

${\ Displaystyle {\ zacząć {tablica} {llll} {\ tekst {konieczność:}} i B \ nie \ modele i E ^ {+} \ \ {\ tekst {wystarczalność:}} i B \ ziemia i \ kolor {niebieski} \models }&E^{+}\\{\text{Słaba spójność:}}&B\land h&\not \models &{\textit {false}}\\{\text{Silna spójność:}}&B\land h \land E^{-}&\not \models &{\textit {false}}\end{array}}}$

„ Konieczność ” nie nakłada ograniczeń na h , ale zabrania tworzenia hipotezy, o ile pozytywne fakty można bez niej wyjaśnić. „ Wystarczalności ” wymaga żadnego generowane hipotezy h wyjaśnić wszystkie pozytywne przykłady . „ Słaby Konsystencja ” zabrania generacja dowolnej hipotezy h , które jest sprzeczne z wiedzą tło B . „ Silna zgodność ” zabrania również stawiania jakiejkolwiek hipotezy h, która jest niespójna z negatywnymi przykładami , biorąc pod uwagę podstawową wiedzę B ; implikuje „ słabą konsystencję ”; jeśli nie podano negatywnych przykładów, oba wymagania są zbieżne. Džeroski wymaga jedynie „ Dostateczności ” (zwanej tam „Kompletnością”) i „ Silnej konsekwencji ”. ${\ Displaystyle E ^ {+}}$${\ Displaystyle E ^ {-}}$

Przykład

Poniższy znany przykład dotyczący poznawania definicji relacji rodzinnych wykorzystuje skróty:

par : rodzic , fem : kobieta , dau : córka , g : George , h : Helen , m : Mary , t : Tom , n : Nancy , e : Eve .

Zaczyna się od podstawowej wiedzy (por. zdjęcie)

${\displaystyle {\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)}$,

pozytywne przykłady

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

i trywialne twierdzenie prawdziwe, oznaczające brak negatywnych przykładów.

Podejście Plotkina „ stosunkowo najmniej uogólnione (rlgg) ” do programowania w logice indukcyjnej powinno zostać wykorzystane do uzyskania sugestii, jak formalnie zdefiniować relację potomną dau .

To podejście wykorzystuje następujące kroki.

• Zrelatywizuj każdy pozytywny przykładowy literał z pełną podstawową wiedzą:

  ${\ Displaystyle {\ zacząć {wyrównany} {\ textit {dau}} (m, h) \ leftarrow {\ textit {par}} (h, m) \ land {\ textit {par}} (h, t) \ grunt {\textit {par}}(g,m)\grunt {\textit {par}}(t,e)\grunt {\textit {par}}(n,e)\grunt {\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)\end{wyrównany}}}$,

• Konwertuj na klauzulę w postaci normalnej :

  ${\ Displaystyle {\ zacząć {wyrównany}} {\ textit {dau}} (m, h) \ lub \ l nie {\ textit {par}} (h, m) \ l nie {\ textit {par}} (h ,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnie {\textit {par}}(n,e )\lor \lnie {\textit {fem}}(h)\lor \lnie {\textit {fem}}(m)\lor \lnie {\textit {fem}}(n)\lor \lnie {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnie {\textit {par}}(h,m)\lor \lnie {\textit {par}}(h ,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnie {\textit {par}}(n,e )\lor \lnie {\textit {fem}}(h)\lor \lnie {\textit {fem}}(m)\lor \lnie {\textit {fem}}(n)\lor \lnie {\textit {fem}}(e)\end{wyrównany}}}$,

• Anti-unifikuj każdą zgodną parę literałów:
  • ${\ Displaystyle {\ textit {dau}} (x_ {mnie}, x_ {ht})}$z i ,${\displaystyle {\textit {dau}}(m,h)}$${\displaystyle {\textit {dau}}(e,t)}$
  • ${\ Displaystyle \ lnot {\ textit {par}} (x_ {ht}, x_ {mnie})}$z i ,${\displaystyle \lnot {\textit {par}}(h,m)}$${\displaystyle \lnot {\textit {par}}(t,e)}$
  • ${\ Displaystyle \ nie {\ textit {fem}} (x_ {mnie})}$z i ,${\displaystyle \lnot {\textit {fem}}(m)}$${\displaystyle \lnot {\textit {fem}}(e)}$
  • ${\displaystyle \lnot {\textit {par}}(g,m)}$z i , podobnie dla wszystkich innych literałów wiedzy w tle${\displaystyle \lnot {\textit {par}}(g,m)}$${\displaystyle \lnot {\textit {par}}(g,m)}$
  • ${\ Displaystyle \ nie {\ textit {par}} (x_ {gt}, x_ {mnie})}$z i i wiele innych zanegowanych literałów${\displaystyle \lnot {\textit {par}}(g,m)}$${\displaystyle \lnot {\textit {par}}(t,e)}$
• Usuń wszystkie zanegowane literały zawierające zmienne, które nie występują w literale dodatnim:
  • po usunięciu wszystkich zanegowanych literałów zawierających inne zmienne niż , pozostaje tylko wraz ze wszystkimi podstawowymi literałami z wiedzy podstawowej${\displaystyle x_{mnie},x_{ht}}$${\ Displaystyle {\ textit {dau}} (x_ {ja}, x_ {ht}) \ lub \ nie {\ textit {par}} (x_ {ht}, x_ {ja}) \ lub \ nie {\ textit {fem}}(x_{me})}$
• Konwertuj klauzule z powrotem do postaci Horn:
  • ${\displaystyle {\textit {dau}}(x_{mnie},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{mnie})\land {\textit {fem}} (x_{me})\land ({\text{wszystkie podstawowe fakty wiedzy}})}$

Wynikowa klauzula Horn jest hipotezą h uzyskaną przez podejście rlgg. Ignorując podstawowe fakty, klauzula nieformalnie brzmi „ jest nazywana córką jeśli jest rodzicem i jest kobietą ”, co jest powszechnie akceptowaną definicją. ${\displaystyle x_{mnie}}$${\displaystyle x_{ht}}$${\displaystyle x_{ht}}$${\displaystyle x_{mnie}}$${\displaystyle x_{mnie}}$

W odniesieniu do powyższych wymagań, „ konieczność ” została spełniona, ponieważ predykat dau nie pojawia się w wiedzy podstawowej, co w związku z tym nie może implikować żadnej własności zawierającej ten predykat, jak w przykładach pozytywnych. „ Wystarczalność ” spełnia obliczona hipoteza h , ponieważ wraz z wiedzą podstawową implikuje pierwszy przykład pozytywny , i podobnie h iz wiedzy podstawowej implikuje drugi przykład pozytywny . „ Słaba spójność ” spełnia h , ponieważ h utrzymuje się w (skończonej) strukturze Herbranda opisanej przez podstawową wiedzę; podobnie dla " Silna konsystencja ". ${\displaystyle {\textit {par}}(h,m)\land {\textit {fem}}(m)}$${\displaystyle {\textit {dau}}(m,h)}$${\displaystyle {\textit {par}}(t,e)\land {\textit {fem}}(e)}$${\displaystyle {\textit {dau}}(e,t)}$

Wspólna definicja relacji babci, mianowicie. , nie można się nauczyć przy użyciu powyższego podejścia, ponieważ zmienna y występuje tylko w treści klauzuli; odpowiednie literały zostałyby usunięte w czwartym kroku podejścia. Aby przezwyciężyć tę wadę, ten krok musi zostać zmodyfikowany w taki sposób, aby można go było sparametryzować za pomocą różnych dosłownych heurystyk po selekcji . Historycznie implementacja GOLEM opiera się na podejściu rlgg. ${\displaystyle {\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}} (ty, z)}$

Indukcyjny system programowania logicznego

Indukcyjny system programowania logicznego to program, który przyjmuje jako dane wejściowe teorie logiczne i generuje poprawną hipotezę. Teorie H wrt Algorytm systemu ILP składa się z dwóch części: poszukiwania hipotezy i wyboru hipotezy. Najpierw hipoteza jest wyszukiwana za pomocą procedury programowania logicznego indukcyjnego, następnie podzbiór znalezionych hipotez (w większości systemów jedna hipoteza) jest wybierany przez algorytm selekcji. Algorytm selekcji ocenia każdą ze znalezionych hipotez i zwraca te z najwyższym wynikiem. Przykładem funkcji punktacji jest minimalna długość kompresji, gdzie hipoteza o najniższej złożoności Kołmogorowa ma najwyższy wynik i jest zwracana. System ILP jest kompletny, jeśli dla dowolnej teorii logiki wejściowej można znaleźć poprawną hipotezę H wrt do tych teorii wejściowych za pomocą procedury wyszukiwania hipotez. ${\ Displaystyle B, E ^ {+}, E ^ {-}}$${\ Displaystyle B, E ^ {+}, E ^ {-}}$${\ Displaystyle B, E ^ {+}, E ^ {-}}$

Wyszukiwanie hipotez

Współczesne systemy ILP takie jak Progol, Hail i Imparo znajdują hipotezę H wykorzystując zasadę odwrotnego wnioskowania dla teorii B , E , H : . Najpierw konstruują pośrednią teorię F zwaną teorią mostową spełniającą warunki i . Następnie jako , uogólniają negację teorii mostów F z anty-uwikłaniem. Jednak działanie anty-uwikłania, ponieważ jest wysoce niedeterministyczne, jest obliczeniowo droższe. Dlatego też alternatywne poszukiwanie hipotez może być przeprowadzone przy użyciu operacji odwrotnego subsumpcji (anty-subsumpcji), która jest mniej niedeterministyczna niż anty-uwikłanie. ${\ Displaystyle B \ ziemia H \ modele e \ jeśli B \ ziemia \ neg e \ modele \ neg H}$${\ Displaystyle B \ ziemia \ neg E \ modele F}$${\ Displaystyle F \ modele \ neg H}$${\ Displaystyle H \ modele \ neg F}$

Pojawiają się pytania o kompletność procedury wyszukiwania hipotez konkretnego systemu ILP. Na przykład procedura poszukiwania hipotez Progola oparta na regule wnioskowania odwrotnego nie jest kompletna w przykładzie Yamamoto . Z drugiej strony Imparo jest kompletne zarówno pod względem postępowania anty-entailmentowego, jak i rozszerzonej procedury odwrotnej subsumpcji.

Realizacje

• 1BC i 1BC2: naiwne klasyfikatory bayesowskie pierwszego rzędu:
• ACE (połączony silnik)
• Aleph
• Atom
• Claudien
• DL-Uczeń
• DMaks
• FastLAS (szybkie uczenie się z zestawów odpowiedzi)
• FOIL (Uczeń indukcyjny pierwszego rzędu)
• Golem
• ILASP (indukcyjne uczenie programów zestawów odpowiedzi)
• Imparo
• Inthelex (przyrostowy uczeń TEORII z PRZYKŁADÓW)
• Limonka
• Metagol
• Mio
• MIS (Model Inference System) autorstwa Ehuda Shapiro
• PROGOL
• RSD
• Cieplejsze (teraz zawarte w ACE)
• ProGolem

Zobacz też

• Zdroworozsądkowe rozumowanie
• Analiza koncepcji formalnej
• Rozumowanie indukcyjne
• Programowanie indukcyjne
• Prawdopodobieństwo indukcyjne
• Statystyczne uczenie relacyjne
• Nauka przestrzeni wersji

Bibliografia

Dalsza lektura