Induktív logikai programozás

Az induktív logikai programozás (ILP) a gépi tanulás  egyik ága , amely a logikai programozást példák, háttérismeretek és hipotézisek bemutatására használja. Miután megkapta a már ismert háttérismeretek leírását és a logikai tények alapjául szolgáló példasort, az ILP rendszer hipotézisek formájában tud olyan logikai programot generálni, amely minden pozitív példát megmagyaráz, a negatív példákat pedig nem.

Séma: pozitív példák + negatív példák + háttérismeretek => hipotézisek

Az induktív logikai programozás kifejezést Stephen Muggleton egy cikkében használták először 1991-ben. Az "induktív" kifejezést itt filozófiai (egy elmélet javaslata a megfigyelt tények magyarázatára) és nem matematikai (egy halmaz tagjainak tulajdonságait bizonyítva) értelemben használjuk.

ILP probléma

A feladat a célpredikátum teljes és konzisztens definíciójának megtalálása a háttérismeretek szempontjából.

A „hipotézis megmagyarázza a példákat” azt jelenti:

Szabályok a Prologban

Az ILP-megvalósítások általában a Prologban készülnek . A további példa megértéséhez emlékezzünk vissza, hogyan vannak elrendezve a szabályok ebben a programozási nyelvben.

Ebben a szabály egy implikáció, például: has_son(X):-parent(X,Y), !woman(Y). (X-nek fia van, ha X a szülője Y és Y nem nő) A szabály feje az implikáció következtetése. A szabály törzse az implikáció elküldése (a "," literálok kötőszava). A literál egy atomi képlet a Prolog -ban, vagy annak tagadása. Ha több szabály van ugyanazzal a fejjel, akkor ezek egyesíthetők úgy, hogy a testüket összekapcsolják a ";" diszjunkcióval.

Hipotézisek finomítása

A hipotézis finomítása iteratív folyamat: egy általánosabb H1 hipotézist veszünk fel, amely megmagyaráz minden "+" példát és néhány "-" példát. Kifinomult, hogy kevesebb "-"-példát magyarázzon. Eredmény: H2 hipotézis, amely a H1 által magyarázott példáknak csak egy részét magyarázza meg

A hipotézisek finomításának módjai:

Változók azonosítása

Ez volt:

van_lánya ( X ) :- szülő ( Y , Z ).

Lett belőle:

van_lánya ( X ) : - szülő ( X , Z )

Háttér állítmány hozzáadása a törzshöz

Ez volt:

van_lánya ( X ) :-.

Lett belőle:

van_lánya ( X ) :- szülő ( Y , Z ).

Példa

Tegyük fel, hogy tényalapunk van a családról:

férfi ( János ). férfi ( bill ). férfi ( paul ). szülő ( John , Kate ). szülő ( mária , kate ). szülő ( Bill , Paul ). szülő ( kate , paul ). nő ( mária ). nőstény ( kate ).

Ehhez a feladathoz a háttértudás a „szülő”, „férfi” és „nő” predikátumok lesznek:

szülő ( X , Y ) férfi ( X ) nő ( X )

Meg akarjuk tanítani az ILP rendszernek a "van a lánya" predikátumot. Definiáljuk célpredikátumként:

van_lánya ( X )

Erre a predikátumra a pozitív példák a következők lennének:

van_lánya ( mária ) van_lánya ( John )

Negatív példák:

lánya ( számla ) lánya ( kate ) lánya ( paul )

A képzés első lépésében csak egy maximálisan általános hipotézisünk van:

van_lánya ( X ).

Triviálisan van elrendezve – minden példát lefed (bármely X esetén teljesít). De nyilvánvaló, hogy néhány példában rossz eredményt ad - például vannak az adatbázisban, akiknek nincs lányuk (ezek Bill, Kate és Paul). Így a hipotézis teljes (lefedi az összes "+"-példát), de inkonzisztens (néhány "-"-példát lefed).

Kezdjük el a hipotézis finomításának folyamatát. Mivel a változókat nem tudjuk azonosítani - csak egy van -, a második módszert fogjuk használni, ami egy háttér predikátum hozzáadása a törzshöz. 3 hipotézist kapunk:

van_lánya ( X ):- férfi ( Y ). van_lánya ( X ):- nő ( Y ). van_lánya ( X ):- szülő ( Y , Z ).

Most már 1 módot használhat a hipotézisek finomítására és a változók azonosítására (azaz Y-t X-re cserélheti).

van_lánya ( X ):- férfi ( X ). van_lánya ( X ):- nő ( X ). van_lánya ( X ):- szülő ( X , Z ).

A kapott hipotézisek közül az első: "X-nek van egy lánya, ha X férfi." Ellenpéldája van Máriában, akinek van egy lánya, de nem férfi. Tehát itt a fa ága csonka: a hipotézis már hiányos (nem vonatkozik Máriára, akinek lánya van) és következetlen (a "Bill" és a "Paul" példákra vonatkozik, akiknek nincs lánya). Hasonlóképpen lesz ez az "X-nek lánya van, ha X nő" hipotézis esetében.

Az egyetlen ág, amely a helyes hipotézishez vezet, a jobb oldalon található finomító lánc, beleértve a szülő predikátumot is. Ennek eredményeként a következő hipotézist kapjuk:

van_lánya ( X ):- szülő ( X , Z ), nő ( Z ).

Ő az, aki teljes és közös.


Jellemzők

  • Olyan rekurzív fogalmak tanítása , mint a „leszármazottak”.
  • Több predikátum tanulása (több predikátum egyidejű tanulása, ahol az egyik predikátum egy másikkal van definiálva)

Hátrányok

  • Manuálisan kell megadnia a változók számát és típusát a cél predikátumban
  • Magas számítási komplexitás ( NP-teljes probléma ). A literálok hozzáadása növeli a változók számát az állítmányban. A változók bármely részhalmaza azonosítható egymással, ami azonnal exponenciális komplexitásnövekedést ad.

Heurisztika

Lehetséges korlátozások az időköltségek csökkentésére:

  • A maximális keresési mélység korlátozása
  • Korlátozás a predikátum törzsben lévő literálok maximális számára
  • A "hipotézisköltség" paraméter bevezetése: Költség(H) = változók_száma(H) + 10*literálok_száma(H) + 10*NegCover(H)

Az ILP hatálya

Irodalom

  • Iván Bratko. Mesterséges intelligencia algoritmusok PROLOG = Prolog Programming For Artificial Intelligence nyelven. - M . : "Williams" , 2004. - S. 640. - ISBN 0-201-40375-7 .