Induktivní logické programování

Induktivní logické programování (také pod zkratkou ILP – Inductive 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.

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.

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

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 $ex$ ∈ $EX$⁺, $H$ $\wedge$ $B$ ⊢ $ex$ (ze znalostní báze a hypotézy lze dokázat všechny pozitivní příklady)
2. pro všechny $ex$ ∈ $EX$⁻, $H$ $\wedge$ $B$ ⊬ $ex$ (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$)

Cílové koncepty v ILP jsou reprezentovány vo formě prvořádových predikátů $p$_i($X$₁,..,$X$_n) jisté arity $n$. Hypotézy generované učícím algoritmem jsou definicemi pro každý z cílových predikátů $p$_i, ve formě množiny logických klauzulí (pravidel) $p$_i($X$₁,..,$X$_n)←$L$₁,...,$L$_n, kde $L$₁,..,$L$ sú 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:

Nechť je dána množina tréninkový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éninkový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éninkové množině ($B$ ∪$H$ ⊢ $e$, pro všechna $e$∈$EX$⁺)

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$ ∪$H$ ⊬ $e$, pro všechna $e$∈$EX$⁻).

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éninkový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í.: 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

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éninkové příklady $EX$ (kde znamínkem + jsou označeny pozitivní příklady a znaménkem minus negativní příklady)a znalostní báze $B$.

Tabulka 1 :

Tréninkové 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ů

Existují různé pohledy na klasifikaci ILP systémů :  : 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éninkové 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

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$, když $B$ ∪ $H$ ⊨ $e$.

Rozšířením funkce na množiny příkladů dostaneme $covers$($B$,$H$,$EX$) = { $e$ ∈ $EX$ | $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 $c$ ∈ $H$, $c$ = $T$ ← $Q$, a substituce θ taková, že $T$θ=$e$ a $Q$θ = {$L$₁,...,$L$_m}θ ⊆ $M$. Tohle pokrytí pak značíme $covers$_ext($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éninkový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éninkový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 $q$_i (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$. :

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

Interaktivní ILP systémy

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éninkový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 $H$^mod, získanou odvoláváním a potvrzováním jednotlivých klauzulí z $H$ tak, aby $H$^mod byla úplná a konzistentní vzhledem ku příkladům $EX$ ∪ {$e$} a znalostní bázi $B$. :

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

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 θ = {$X$₁/$t$₁,...,$X$_k/$t$_k} 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é $X$_j ve $W$ nahrazeny stejným termem $t$_j.

Definice: Klauzule $c$ = $T$←$Q$ (kde $T$ je atom $p$($X$₁,...,$X$_n) a $Q$ je konjunkce literálů $L$₁,...,$L$_m) θ-zahrnuje klauzuli $c$', když existuje substituce θ={$X$₁/$t$₁,...,$X$_k/$t$_k} z proměnných $X$_i v $c$ do termů $t$_i 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

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

Tyto techniky jsou využívány empirickými ILP systémy, protože hledání shora-dolů se lépe 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'\}$

Tento 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$+.