Programarea logică inductive (ILP) este o ramură a învățării automate care utilizează programarea logică ca formă de prezentare a exemplelor, cunoștințelor de bază și ipotezelor. După ce a primit descrieri ale cunoștințelor deja cunoscute și un set de exemple prezentate ca bază logică a faptelor, sistemul ILP poate genera un program logic sub formă de ipoteze care explică toate exemplele pozitive și niciunul dintre cele negative.
Schema: exemple pozitive + exemple negative + cunoștințe de bază => ipoteze
Termenul de programare logică inductive a fost folosit pentru prima dată într-un articol al lui Stephen Muggleton în 1991. Termenul „inductiv” este folosit aici într-un sens filozofic (propunerea unei teorii pentru a explica faptele observate), și nu în sens matematic (demonstrarea proprietății membrilor unei mulțimi).
Sarcina este de a găsi o definiție completă și consecventă a predicatului țintă în ceea ce privește cunoștințele de bază.
„Ipoteza explică exemple” înseamnă:
De obicei, implementările ILP sunt realizate în Prolog . Pentru a înțelege exemplul suplimentar, să ne amintim cum sunt aranjate regulile în acest limbaj de programare.
În ea, regula este o implicație, de exemplu: are_fiu(X):-parent(X,Y), !femeie(Y). (X are un fiu dacă X este părintele lui Y și Y nu este femeie) Capul regulii este concluzia implicației. Corpul regulii este trimiterea implicației (conjuncția lui "," literali). Un literal este o formulă atomică în Prolog sau negația acesteia. Dacă există mai multe reguli cu același cap, atunci ele pot fi combinate într-una singură, conectându-și corpurile cu disjuncția ";"
Rafinarea ipotezei este un proces iterativ: este luată o ipoteză mai generală H1, care explică toate exemplele „+” și unele exemple „-”. Este rafinat pentru a explica mai puține „-”-exemple. Rezultat: Ipoteza H2 care explică doar un subset din exemplele explicate de H1
Modalități de rafinare a ipotezelor:
Identificarea variabilelor
A fost:
are_fiica ( X ) :- părinte ( Y , Z ).A devenit:
are_fiica ( X ) :- părinte ( X , Z )Adăugarea unui predicat de fundal în corp
A fost:
are_fiica ( X ) :-.A devenit:
are_fiica ( X ) :- părinte ( Y , Z ).Să presupunem că avem o bază de fapte despre familie:
bărbat ( John ). bărbat ( factura ). bărbat ( paul ). părinte ( John , Kate ). părinte ( mary , kate ). părinte ( Bill , Paul ). părinte ( kate , paul ). femeie ( mary ). femeie ( kate ).Cunoștințele de bază pentru această sarcină vor fi predicatele „părinte”, „mascul” și „femeie”:
părinte ( X , Y ) bărbat ( X ) femeie ( X )Vrem să învățăm sistemul ILP predicatul „are o fiică”. Să-l definim ca predicat țintă:
are_fiica ( X )Pentru acest predicat, exemple pozitive ar fi:
are_fiica ( Maria ) are_fiica ( Ioan )Exemple negative:
are_daughter ( factura ) are_daughter ( Kate ) are_daughter ( paul )La primul pas de antrenament, avem o singură ipoteză maxim generală:
are_fiica ( X ).Este aranjat trivial - acoperă toate exemplele (performează pentru orice X). Dar este evident că în unele exemple dă un rezultat greșit – de exemplu, sunt cei din baza de date care nu au o fiică (aceștia sunt Bill, Kate și Paul). Astfel, ipoteza este completă (acoperă toate "+"-exemple), dar inconsecventă (acoperă unele "-"-exemple).
Să începem procesul de rafinare a ipotezei. Deoarece nu putem identifica variabile - există doar una - vom folosi a doua metodă - adăugând un predicat de fundal în corp. Obținem 3 ipoteze:
are_fiica ( X ):- bărbat ( Y ). are_fiica ( X ):- femeie ( Y ). are_fiica ( X ):- părinte ( Y , Z ).Acum puteți folosi 1 mod de a rafina ipotezele și de a identifica variabilele (adică înlocuiți Y cu X) Obținem:
are_fiică ( X ):- bărbat ( X ). are_fiica ( X ):- femeie ( X ). are_fiica ( X ):- părinte ( X , Z ).Prima dintre ipotezele rezultate este: „X are o fiică dacă X este bărbat”. Ea are un contraexemplu în Mary, care are o fiică, dar nu este bărbat. Deci aici ramura copacului este trunchiată: ipoteza este deja incompletă (nu o acoperă pe Mary, care are o fiică) și inconsecventă (acoperă exemplele „Bill” și „Paul”, care nu au fiice). În mod similar, va fi și în cazul ipotezei „X are o fiică, dacă X este femeie”.
Singura ramură care duce la ipoteza corectă este lanțul de rafinare din partea dreaptă, inclusiv predicatul părinte. Ca urmare, obținem ipoteza:
are_fiica ( X ):- părinte ( X , Z ), femeie ( Z ).Ea este cea completă și unită.
Posibile restricții pentru reducerea costurilor de timp: