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):
 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ů).
 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í  (znalostní báze, teorie), množina pozitivních příkladů + a množina negativních příkladů −. Potom najdi hypotézu  takovou, že
 pro všechny  ∈ +,    ⊢  (ze znalostní báze a hypotézy lze dokázat všechny pozitivní příklady)
 pro všechny  ∈ −,    ⊬  (ze znalostní báze a hypotézy nelze dokázat žádný negativní příklad)
    ⊬ ⟡ (hypotéza  je konzistentní se znalostní bází )

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

Tabulka 1 :

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ů 
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  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é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ů  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 . :

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ů  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 . :

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

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  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 

Matematická logika
Strojové učení