Induktivní logické programování (ILP) je odvětví strojového učení , které využívá logické programování jako formu prezentace příkladů, základních znalostí a hypotéz. Po obdržení popisů již známých základních znalostí a sady příkladů prezentovaných jako logický základ faktů může systém ILP generovat logický program ve formě hypotéz, který vysvětluje všechny pozitivní příklady a žádný z negativních.
Schéma: pozitivní příklady + negativní příklady + znalost pozadí => hypotézy
Termín indukční logické programování byl poprvé použit v článku Stephena Muggletona v roce 1991. Termín "indukční" je zde použit ve filozofickém (návrh teorie k vysvětlení pozorovaných skutečností), nikoli v matematickém (prokazování vlastnosti členů množiny) smyslu.
Úkolem je nalézt úplnou a konzistentní definici cílového predikátu z hlediska základních znalostí.
„Hypotéza vysvětluje příklady“ znamená:
Implementace ILP se obvykle provádějí v Prologu . Pro pochopení dalšího příkladu si připomeňme, jak jsou pravidla uspořádána v tomto programovacím jazyce.
V něm je pravidlo implikací, například: has_son(X):-parent(X,Y), !woman(Y). (X má syna, pokud X je rodič Y a Y není žena) Hlavou pravidla je závěr implikace. Tělem pravidla je odeslání implikace (spojení "," literálů). Literál je atomický vzorec v Prologu nebo jeho negace. Pokud existuje několik pravidel se stejnou hlavou, pak je lze spojit do jednoho spojením jejich těl s disjunkcí ";"
Upřesňování hypotézy je iterativní proces: Je vzata obecnější hypotéza H1, která vysvětluje všechny příklady „+“ a některé příklady „-“. Je upraven tak, aby vysvětlil méně "-"-příkladů. Výsledek: Hypotéza H2, která vysvětluje pouze podmnožinu příkladů vysvětlených H1
Způsoby, jak upřesnit hypotézy:
Identifikace proměnných
To bylo:
has_daughter ( X ) :- parent ( Y , Z ).To se stalo:
has_daughter ( X ) :- parent ( X , Z )Přidání predikátu pozadí do těla
To bylo:
has_daughter ( X ) :-.To se stalo:
has_daughter ( X ) :- parent ( Y , Z ).Předpokládejme, že máme základ faktů o rodině:
muž ( john ). muž ( Bill ). muž ( Pavel ). rodič ( john , kate ). rodič ( Mary , Kate ). rodič ( Bill , Paul ). rodič ( kate , paul ). žena ( Mary ). žena ( kate ).Základními znalostmi pro tento úkol budou predikáty „rodič“, „muž“ a „žena“:
rodič ( X , Y ) muž ( X ) žena ( X )Chceme systém ILP naučit predikát „má dceru“. Definujme to jako cílový predikát:
has_daughter ( X )Pro tento predikát by pozitivní příklady byly:
has_daughter ( mary ) has_daughter ( john )Negativní příklady:
has_daughter ( bill ) has_daughter ( kate ) has_daughter ( paul )V prvním kroku tréninku máme pouze jednu maximálně obecnou hypotézu:
má_dceru ( X ).Je triviálně uspořádán - pokrývá všechny příklady (vystupuje pro libovolné X). Je ale zřejmé, že v některých příkladech dává špatný výsledek – například v databázi jsou tací, kteří dceru nemají (to jsou Bill, Kate a Paul). Hypotéza je tedy úplná (pokrývá všechny "+"-příklady), ale nekonzistentní (pokrývá některé "-"-příklady).
Začněme proces upřesňování hypotézy. Protože nemůžeme identifikovat proměnné - existuje pouze jedna - použijeme druhou metodu - přidání predikátu pozadí do těla. Dostáváme 3 hypotézy:
has_daughter ( X ):- muž ( Y ). has_daughter ( X ):- žena ( Y ). has_daughter ( X ):- parent ( Y , Z ).Nyní můžete použít 1 způsob, jak upřesnit hypotézy a identifikovat proměnné (tj. nahradit Y X) Dostaneme:
has_daughter ( X ):- muž ( X ). has_daughter ( X ):- žena ( X ). has_daughter ( X ):- parent ( X , Z ).První z výsledných hypotéz je: "X má dceru, pokud je X muž." Má protipříklad v Mary, která má dceru, ale není muž. Zde je tedy větev stromu zkrácena: hypotéza je již neúplná (nezahrnuje Marii, která má dceru) a nekonzistentní (pokrývá příklady „Bill“ a „Paul“, kteří nemají žádné dcery). Podobně tomu bude v případě hypotézy „X má dceru, pokud je X žena“.
Jediná větev, která vede ke správné hypotéze, je zpřesňující řetězec na pravé straně, včetně nadřazeného predikátu. V důsledku toho dostáváme hypotézu:
has_daughter ( X ):- rodič ( X , Z ), žena ( Z ).Je to ona, kdo je úplný a společný.
Možná omezení pro snížení časových nákladů: