Induktivní logické programování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Induktivní logické programování (také pod zkratkou ILPInductive logic programming) je podoborem oboru strojového učení, v rámci kterého zahrnuje techniky strojového učení spadající pod širší kategorii konceptního učení (concept learning). Cílem konceptního učení je naučení nějakého konceptu, jenž definuje třídu objektů, příkladů, nebo individuí tak, že na základě jistých tréninkových příkladů a znalostní báze (background knowledge) bude vygenerována hypotéza, která by mohla být dobrou aproximací originálního konceptu. Ukazuje se, že jazyk pozůstávající z logických programů poskytuje dostatečnou expresivnost pro řešení mnohých učících problémů s relacemi. Systémy, které dokáží indukovat hypotézu ve formě logického programu proto nazýváme systémy induktivního logického programovaní (ILP systémy – Inductive Logic Programming systems).

ILP rozšiřuje možnosti tradičnějších metod, kde jsou příklady i hypotézy popsány hodnotami atributů (attribute-value, neboli AV), o expresivnost prvořádové logiky. ILP metody mohou tedy využívat vztahy mezi vlastnostmi charakterizujícími příklady a mezi samotnýma příklady, a vyjádřit jich ve formě prvořádových predikátů s proměnnými.[1]

Kombinace strojového učení a logického programování rozvíjí běžné induktivní strojové učení o nástroje a techniky k indukci hypotézy z pozorování (příkladů) a syntetizaci znalostí ze zkušenosti. Užívání výpočtové logiky jako reprezentačního mechanizmu pro hypotézy a pozorování napomáhá ILP překonat dvě hlavní omezení klasických technik strojového učení (jakým je např. Top-Down-Induction-of-Decision-Tree, TDIDT):

  1. používání omezeného formalizmu znalostní reprezentace (výrokové logiky) – mnohé sféry expertizy mohou být vyjádřeny jenom v prvořádové logice nebo jej odrodě, výroková logika je pro ně nedostateční (což je zjevné např. v syntéze logického programu z příkladů).
  2. potíže v používání podstatné znalostní báze v učícím procesu.[2]

Navíc ILP rozšiřuje teorii a praxi výpočtové logiky větším využíváním indukce jako způsobu inference. Zatímco současná výpočtová logika popisuje deduktivní inferenci z logických formulí poskytnutých uživatelem, ILP popisuje induktivní inferenci logického programu na základě příkladů a znalostní báze.

Formální definice[editovat | editovat zdroj]

Specifikace problému: Nech je daná množina Hornových klauzulí B (znalostní báze, teorie), množina pozitivních příkladů EX+ a množina negativních příkladů EX-. Potom najdi hypotézu H takovou, že

  1. pro všechny exEX+, H \wedge Bex (ze znalostní báze a hypotézy lze dokázat všechny pozitivní příklady)
  2. pro všechny exEX-, H \wedge Bex (ze znalostní báze a hypotézy nelze dokázat žádný negativní příklad)
  3. H \wedge B ⊬ ⟡ (hypotéza H je konzistentní se znalostní bází B)[3]

Cílové koncepty v ILP jsou reprezentovány vo formě prvořádových predikátů pi(X1,..,Xn) jistý arity n. Hypotézy generované učícím algoritmem jsou definicemi pro každý z cílových predikátů pi, ve formě množiny logických klauzulí (pravidel) pi(X1,..,Xn)←L1,...,Ln, kde L1,..,Lliterály.

Existence znalostní báze jako jistého souboru předešlých znalostí není nutná, avšak pro závažnější problémy žádoucí, jelikož eventuálně slouží k lepší a přirozenější vyjadřovací schopnosti při generalizaci příkladů. Nebo jinak, znalostní báze determinuje vyhledávací prostor popisů konceptů, jenž nazýváme prostor hypotéz (hypothesis space). Na základě tohoto můžeme přeformulovat naši definici slovně takhle[4]:

Nechť je dána množina tréningových příkladů EX a znalostní báze B, najdi hypotézu H, vyjádřenu v nějakém jazyce pro popis konceptů L tak, že H je úplná a konzistentní vzhledem ke znalostní báze B a příkladům EX.

Definice: Hypotézu H nazýváme úplnou vzhledem k množině tréningových příkladů EX a znalostní bázi B, jestli z hypotézy a znalostní báze může být odvozen každý pozitivní příklad v tréningové množině (B He, pro všechna eEX+)

Definice: Hypotézu H nazýváme konzistentní, jestli žádný negativní příklad nemůže být z hypotézy a znalostní bázi odvozen (B He, pro všechna eEX-).

V principu se tedy jedná o žádoucí podmínky, které jsou již zahrnuty v definice výše, nicméně tyhle podmínky se ukáží jako svazující v praktických situacích s nedokonalými informacemi (např. chybějící hodnoty, chyby v tréningových příkladech a znalostní bázi – tzv. hluk nebo noise, nedostateční množství příkladů ...). Navíc mohou tyhle podmínky pomoci k produkci přílišně složitých hypotéz, které způsobují tzv. přeučení tréninkových příkladů (v anglické literatuře označováno jako overfitting).

Zvolený jazyk je také jedním z mechanizmů, které mohou omezit vyhledávaní hypotéz, tedy určují prostor hypotéz samotný. Když zvolíme silnější jazyk (teda méně expresivní jazyk kandidátních hypotéz), vyhledávací prostor se zmenší a učení se stane efektivnější; avšak tahle metoda stejně zamezí, aby systém nalezl komplexnější řešení, které není obsaženo v méně expresivním jazyce. Tato dilema mezi expresivností a komplexitou tvoří velkou část současného výzkumu v oboru induktivního učení.[5]: Příkladem jazykových omezení na typ klauzulí v predikátových definicích jsou Hornovy klauzule, klauzule bez funkčních symbolů (teda v predikátech v klauzulových literálech se nenacházejí žádné složitější termy, jenom proměnné a konstanty), nerekurzivní predikáty (cílový predikát se nesmí objevit v tele klauzule).

Příklad[editovat | editovat zdroj]

Hore popsané koncepty lze ilustrovat na jednoduchém příkladu, v němž se snažíme definovat cílový koncept dcera vyjádřen pomocí predikátu dcera(X,Y) (X je dcera Y). V tabulce 1 jsou tréningové příklady EX (kde znamínkem + jsou označeny pozitivní příklady a znaménkem mínus negativní příklady)a znalostní báze B.

Tabulka 1[6] :

Tréningové příklady Znalostní báze
dcera(marie,anna) + rodič(anna, marie) žena(anna)
dcera(eva,tomáš) + rodič(anna, tomáš) žena(marie)
dcera(tomáš,anna) - rodič(tomáš,eva) žena(eva)
dcera(eva,anna) - rodič(tomáš, jan)

ILP algoritmus je schopný vygenerovat následující hypotézu predikátu dcera(X,Y) (předpokládáme jazyk L Hornových klauzulí:

       dcera(X,Y)  žena(X), rodič(Y,X).

Tohle možno vyslovit v programovacím jazyku Prolog ve formě pravidla dcera(X,Y):- žena(X), rodič(Y,X)., v přirozeným jazyce: "Když X je žena a Y je rodič X, pak X je dcera Y.".

Typologie ILP systémů[editovat | editovat zdroj]

Existují různé pohledy na klasifikaci ILP systémů[7] : [8] : na základě několika kritérií:

  • podle toho, zdali akceptují jediný cílový koncept nebo několik.
  • podle toho, zdali berou všechny tréningové příklady najednou a následně tvoří hypotézu (tzv. batch learners) nebo berou příklady postupně (tzv. incremental learners)
  • podle toho, zdali se dotazují uživatele na správnost dosud naučené hypotézy v různých momentech procesu, a žádají od uživatele, aby klasifikoval nové příklady vygenerované systémem jako pozitivní nebo negativní (interaktivní), nebo tohle nedělají (neinteraktivní)
  • podle toho, zdali se učí koncept od základu, nebo na začátku přijmou částečnou definici cílového predikátu, kterou postupně vylepšují učením

Na základě tyhle rozdělení je možné udělat nejdůležitější rozlišení, a to mezi empirickými ILP systémy a interaktivními ILP systémy.

Empirické ILP systémy[editovat | editovat zdroj]

Abychom výše zmíněnou definici učení spravili funkčnější, je vhodné využít sémantického pojmu pokrytí. Říkáme, že e je pokryto hypotézou H při dané znalostní bázi B, když e je logickým důsledkem B H, teda B H e.

Definice: Mějme B znalostní bázi, H hypotézy a množinu příkladů EX, funkce covers je definována následovně: covers (B ,H, e) = true, ak B H e.

Rozšířením funkce na množiny příkladů dostaneme covers(B,H,EX) = { eEX | B H e }.

Tahle definice pokrytí je ovšem intenzionální, jelikož znalostní báze B je intenzionální obsahující i základní fakty (pozitivní a negativní příklady) i "nezákladní" klauzule (v znalostní bázi). Na druhé straně, extenzionální pojem pokrytí v sobě zahrnuje extenzionální znalostní bázi, která sestává jenom ze základních faktů. Většina empirických ILP systémů využívá právě tohohle pojmu. V tomhle případe, jestli B obsahuje intenzionální predikátové definice, extenzionální ILP systém musí transformovat B do základního modelu M bázové teorie B (teda do modelu, jenž obsahuje všechny pravdivé základní fakty odvozené z B).

Následně můžeme definovat pojem extenzionální pokrytí.

Definice: Hypotéza H extenzionálně pokrývá příklad e vzhledem ku základnímu modelu M, když existuje klauzule cH, c = TQ, a substituce θ taková, že Tθ=e a Qθ = {L1,...,Lm}θM. Tohle pokrytí pak značíme coversext(M, H, e).

Úloha empirického ILP systému v sobě zahrnuje některé odlišnosti, hlavně typickou orientaci na jediný cílový koncept v prostředí velkého souboru převážně zašuměných (noisy) příkladů, využívaní tréningových příkladů najednou (batch learner), neinteraktivní charakter, a učení od základů. Mohli bychom ji popsat následovně:

Dána je množina tréningových příkladů EX pozůstávající z pravdivých EX+ a nepravdivých EX- základních faktů o neznámém predikátu p. Jazyk L specifikuje syntaktické restrikce definice predikátu p. Dána je znalostní báze B, definující predikáty qi (odlišné od p), které mohou být použity v definici p a poskytující dodateční informace o argumentech příkladů predikátu p. Nájdi definici H pre p, vyjádřitelní v L takovou, že H je úplní a konzistentní vzhledem ku EX a B.[9] :

Systémy, které bychom mohli zařadit mezi empirické ILP, jsou např. FOIL, GOLEM, PROLOG.

Interaktivní ILP systémy[editovat | editovat zdroj]

Interaktivní ILP jsou naproti empirickým převážně orientovány na učení mnohých cílových predikátů z menšího množství příkladů, typicky inkrementálně. Jejich úkol bychom mohli popsat takhle:

Daná je množina tréningových příkladů EX o vícerých predikátech, znalostní báze B s predikátovými definicemi, které považujeme za platné a současná hypotéza H pokud možno neplatná. Navíc zde existuje nějaké orákulum, které je schopné rozhodnout o náležitosti dotazů o příkladech e do pozitivní a negativní třídy příkladů.

Najdi novou hypotézu Hmod, získanou odvoláváním a potvrzováním jednotlivých klauzulí z H tak, aby Hmod byla úplná a konzistentní vzhledem ku příkladům EX {e} a znalostní bázi B.[10] :

V tomhle procese sehrává důležitou úloha možná změna hypotézy jazyka L v procese učení. Tahle změna může vést ku tvorbě nových predikátů, stejně tak i silnějších hypotéz jazyka.

Mezi tyhle systémy bychom mohli zařadit MIS sestavený Ehudem Shapirem, MARVIN, CLINT, nebo CIGOL.

Techniky ILP[editovat | editovat zdroj]

Na konceptní učení je možno nahlížet jako na vyhledávací problém, kde cílem je najít stavy v prostoru hypotéz, které uspokojují nějaké kvalitativní kritéria. Pro umožnění hledání je nutné strukturovat prostor hypotéz, což je možné prostřednictvím speciálního svazu θ-zahrnutí. Díky tomu zavedeme do struktury částečné uspořádaní. Nejprve je nutné definovat funkci substituce.

Definice: Substituce θ = {X1/t1,...,Xk/tk} je funkce z proměnných do termů. Aplikací substituce θ na dobře vytvořenou formuli W se získá Wθ, kde jsou všechny výskyty každé proměnné Xj ve W nahrazeny stejným termem tj.

Definice: Klauzule c = TQ (kde T je atom p(X1,...,Xn) a Q je konjunkce literálů L1,...,Lm) θ-zahrnuje klauzuli c', když existuje substituce θ={X1/t1,...,Xk/tk} z proměnných Xi v c do termů ti tak, že klauzule c se substitucí θ je podmnožina klauzule c' (cθc')

Příklad

Nechť máme klauzuli  c = D(X,Y) \implies R(Y,X), kde D(X,Y) představuje vztah "X je dcera Y" a R(Y,X) zase vztah "Y je rodič X".

Nechť termy m = Marie, a = Anna, t = Tomáš. Substitucí \theta = \{ X/m, Y/a \}  získáme klauzuli c\theta= D(m,a) \implies R(a,m). Notace D(X,Y)\implies R(Y,X) může být vyjádřena i ve formě

\{ D(X,Y);\neg R(Y,X) \}, kde středník mezi atomy znamená disjunkci. ¨

Klauzule c pak θ-zahrnuje klauzuli c' =  D(X,X) \implies Z(X),R(X,X), kde atom Z(X) možno interpretovat jako "X je žena", pod substitucí \theta = \{ Y/X \}  .

Klauzule c také θ-zahrnuje klauzuli  D(m,a) \implies Z(m),R(a,m),R(a,t) pod substitucí \theta = \{X/m,Y/a \}  , protože (D(m,a); \neg R(a,m))\subseteq(D(m,a); \neg R(a,m); \neg R(a,t))

θ-zahrnutí zavádí syntaktický pojem obecnosti. Klauzule c je alespoň tak obecná jak klauzule c' (c \leq c'), když c θ-zahrnuje c'. Klauzule c je obecnější jako klauzule c' (c < c'), když platí c \leq c' a neplatí c' \leq c. V tomto případě říkáme, že c' je specializací (zjemněním) c a c je generalizací c'.

Takhle definováno θ-zahrnutí, které zavádí svaz ( \leq ) na množině redukovaných klauzulí (což znamená, že každé dvě klauzule mají nejmenší horní mez (nhm) a největší dolní mez (ndm)), zároveň poskytuje dostateční základnu pro dvě ILP techniky:

  • zdola-nahoru (bottom-up) budování nejmenších obecných generalizací z tréninkových příkladů
  • shora-dolu (top-down) hledání zjemňujících grafů

Bottom-up generalizační techniky[editovat | editovat zdroj]

Používají se hlavně u interaktivních (inkrementálních) ILP systémů. Začínají od nejvíce specifikované klauzule, která pokrývá daný příklad, a poté zobecňují tuhle klauzuli, až kým nemůže být více zobecněná bez pokrytí negativních příkladů. Využívají dvě základní generalizační (syntaktické) operace:

  • užívání inverzní substituce na klauzule (teda substituce, která mapuje termy do proměnných)
  • odstraňování literálu z těla klauzule

Při tyhle technikách se využívá ještě pojmu nejmenší obecní zobecnění (z ang. least general generalization, lgg), která pomáhá minimalizovat riziko z přijetí negativních příkladů. Pojem lgg vychází ze svazového uspořádání, které bylo zavedené prostřednictvím θ-zahrnutí.

Definice: Nejmenší obecní zobecnění (lgg) dvou redukovaných klauzulí c a c' je nejmenší horní mez c a c' v θ-zahrnujícím svaze, a označuje se lgg( c , c' ).

Tohle je ovšem jenom základní definice, lgg je jinak definováno rekurzivně pro termy, predikáty, literály a klauzule.

Top-down specializační techniky[editovat | editovat zdroj]

Tyhle techniky jsou využívány empirickými ILP systémy, protože hledání shora-dole se líp přizpůsobuje heuristice omezování velkého vyhledávacího prostoru. Využívají specializační operátor, jinak nazýván i zjemňující operátor, jenž je založený na θ-zahrnutí.

Definice: Pro daný jazyk L, zjemňující operátor ρ mapuje klauzuli c do množiny klauzulí  \rho (c) , které jsou specializací (zjemněním) klauzule c :

\rho (c)= \{ c' | c'\in L, c < c'\}

Tenhle operátor využívá dvě základní specializační (syntaktické) techniky:

  • užívání substituce na klauzule (tedy změna nějakých proměnných na termy)
  • přidávání literálů do těla klauzule.

Algoritmus využíván při této technice iterativně přidává nové klauzule c_i k finální hypotéze H, aby pokrývala stále větší množinu příkladů, a eliminuje předtím přidány klauzule, které nakonec pokrývají i negativní příklady, až kým je hypotéze úplní a konzistentní. Přitom využívá orientovaný acyklický graf (v tomhle případe nazýván zjemňující/specializační graf), v kterém uzly představují programové klauzule a hrany korespondují se základními zjemňujícími operacemi (substituce a přidávání literálů). Tenhle graf pak funguje ku vyhledávání od nejobecnější klauzule (prázdný klauzule ( c_i = T \leftarrow ) ku více specifické klauzuli (c'_i =T\leftarrow L_1,...,L_m) pokrývající podmnožinu pozitivních příkladů EX+.

Reference[editovat | editovat zdroj]

  1. POVEDA POVEDA, Jordi; TURMO BORRÀS, Jordi. Inductive Logic Programming and Its Application to the Temporal Expression Chunking Problem. [s.l.] : LSI Department Technical Report, 2007.  
  2. MUGGLETON, Stephen; DE RAEDT, Luc. Inductive Logic Programming: Theory and Methods. Journal of Logic Programming. , roč. 1994, čís. 19, s. 629-679.  
  3. BERKA, Petr. Dobývání znalostí z databází. Praha : Academia, 2003. 366 s. ISBN 80-200-1062-9.  
  4. LAVRAČ, Nada; DŽEROSKI, Sašo. Inductive Logic Programming: Techniques and Applications. New York : Ellis Horwood, 1994. ISBN 0-13-457870-8. S. 10.  
  5. LAVRAČ, Nada; DŽEROSKI, Sašo. [s.l.] : [s.n.]. S. 11.  
  6. LAVRAČ, Nada; DŽEROSKI, Sašo. [s.l.] : [s.n.]. S. 14.  
  7. LAVRAČ, Nada; DŽEROSKI, Sašo. [s.l.] : [s.n.]. 311 s.  
  8. POVEDA POVEDA, Jordi; TURMO BORRÀS, Jordi. [s.l.] : [s.n.]. S. 3-4.  
  9. LAVRAČ, Nada; DŽEROSKI, Sašo. [s.l.] : [s.n.]. S. 30.  
  10. LAVRAČ, Nada; DŽEROSKI, Sašo. [s.l.] : [s.n.]. S. 32.