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í (znalostní báze, teorie), množina pozitivních příkladů + a množina negativních příkladů -. Potom najdi hypotézu takovou, že

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

Cílové koncepty v ILP jsou reprezentovány vo formě prvořádových predikátů i(1,..,n) jisté arity . Hypotézy generované učícím algoritmem jsou definicemi pro každý z cílových predikátů i, ve formě množiny logických klauzulí (pravidel) i(1,..,n)←1,...,n, kde 1,..,literá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ů a znalostní báze , najdi hypotézu , vyjádřenu v nějakém jazyce pro popis konceptů tak, že je úplná a konzistentní vzhledem ke znalostní báze a příkladům .

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

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

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 (tedy 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]

Výše 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 (kde znamínkem + jsou označeny pozitivní příklady a znaménkem mínus negativní příklady)a znalostní báze .

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 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 je pokryto hypotézou při dané znalostní bázi , když je logickým důsledkem , teda .

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

Rozšířením funkce na množiny příkladů dostaneme (,,) = { | }.

Tahle definice pokrytí je ovšem intenzionální, jelikož znalostní báze 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 obsahuje intenzionální predikátové definice, extenzionální ILP systém musí transformovat do základního modelu bázové teorie (teda do modelu, jenž obsahuje všechny pravdivé základní fakty odvozené z ).

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

Definice: Hypotéza extenzionálně pokrývá příklad vzhledem ku základnímu modelu , když existuje klauzule , = , a substituce θ taková, že θ= a θ = {1,...,m}θ. Tohle pokrytí pak značíme ext(, , ).

Ú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ů pozůstávající z pravdivých + a nepravdivých - základních faktů o neznámém predikátu . Jazyk specifikuje syntaktické restrikce definice predikátu . Dána je znalostní báze , definující predikáty i (odlišné od ), které mohou být použity v definici a poskytující dodateční informace o argumentech příkladů predikátu . Nájdi definici pre , vyjádřitelní v takovou, že je úplní a konzistentní vzhledem ku a .[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ů o vícerých predikátech, znalostní báze s predikátovými definicemi, které považujeme za platné a současná hypotéza pokud možno neplatná. Navíc zde existuje nějaké orákulum, které je schopné rozhodnout o náležitosti dotazů o příkladech do pozitivní a negativní třídy příkladů.

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

V tomhle procese sehrává důležitou úloha možná změna hypotézy jazyka 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 θ = {1/1,...,k/k} je funkce z proměnných do termů. Aplikací substituce θ na dobře vytvořenou formuli se získá θ, kde jsou všechny výskyty každé proměnné j ve nahrazeny stejným termem j.

Definice: Klauzule = (kde je atom (1,...,n) a je konjunkce literálů 1,...,m) θ-zahrnuje klauzuli ', když existuje substituce θ={1/1,...,k/k} z proměnných i v do termů i tak, že klauzule se substitucí θ je podmnožina klauzule ' (θ')

Příklad

Nechť máme klauzuli , kde představuje vztah "X je dcera Y" a zase vztah "Y je rodič X".

Nechť termy m = Marie, a = Anna, t = Tomáš. Substitucí získáme klauzuli . Notace může být vyjádřena i ve formě

, kde středník mezi atomy znamená disjunkci. ¨

Klauzule pak θ-zahrnuje klauzuli , kde atom možno interpretovat jako "X je žena", pod substitucí .

Klauzule také θ-zahrnuje klauzuli pod substitucí , protože

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

Takhle definováno θ-zahrnutí, které zavádí svaz () 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í a je nejmenší horní mez a v θ-zahrnujícím svaze, a označuje se .

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 , zjemňující operátor ρ mapuje klauzuli do množiny klauzulí , které jsou specializací (zjemněním) klauzule  :

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 k finální hypotéze , 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 () ku více specifické klauzuli () pokrývající podmnožinu pozitivních příkladů +.

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.