Programmazione logica induttiva

La programmazione logica induttiva si basa sul metodo induttivo e sulla logica del primo ordine. E' anche conosciuta come ILP (Inductive Logic Programming). Si tratta di una disciplina dell'apprendimento automatico.

Come funziona?

Data una conoscenza di base (background) e un insieme di esempi, il sistema ILP produce delle ipotesi e un criterio di classificazione dei dati.

Gli esempi consistono in due insiemi

• Descrizioni. Questo insieme contiene alcune caratteristiche degli elementi.
• Classificazione. In questo insieme sono inclusi alcuni esempi di classificazione positivi e negativi. E' il concetto oggettivo (conoscenza) che il sistema deve approfondire.

Pertanto il vincolo di consequenzialità è

Background ∧ Ipotesi ∧ Descrizioni |= Classificazioni

Dove le Ipotesi sono un'incognita da scoprire.

La macchina formula un'ipotesi di classificazione in base al proprio background e verifica se classifica correttamente gli esempi positivi e negativi.

Un esempio pratico

La macchina deve individuare un'ipotesi in grado di capire se una persona è il nonno di un'altra persona.

Prendo in considerazione queste relazioni di parentela.

Nell'insieme delle Classificazioni fornisco alla macchina solo alcuni esempi positivi

Nonno(A,D)
Nonno(A,E)

e alcuni esempi negativi

¬Nonno(A,B)
¬Nonno(A,C)

Nell'insieme delle Descrizioni descrivo alcune caratteristiche degli elementi.

Genitore(A,B)
Genitore(A,C)
Genitore(B,D)
Genitore(B,E)
Genitore(C,F)
Genitore(C,G)

Da questi vincoli di consequenzialità il programma di apprendimento formula delle ipotesi e verifica se soddisfano gli esempi positivi e negativi.

Ipotesi 1

La macchina formula un'ipotesi

Genitore(x,y) ⇒ Nonno(x,y)

Poi verifica il risultato rispetto alla conoscenza in suo possesso

Genitore(A,B) ⇒ Nonno(A,B)
Genitore(A,C) ⇒ Nonno(A,C)
Genitore(B,D) ⇒ Nonno(B,D)
Genitore(B,E) ⇒ Nonno(B,E)
Genitore(C,F) ⇒ Nonno(C,F)
Genitore(C,G) ⇒ Nonno(C,G)

Questa ipotesi viola due esempi negativi, quindi è poco efficace.

Ipotesi 2

La macchina formula un'ipotesi

Genitore(x,y) ∧ Genitore(y,z) ⇒ Nonno(x,z)

In pratica se x è il genitore di y e y è il genitore di z, allora x è il nonno di z.

Poi verifica il risultato rispetto alla conoscenza in suo possesso

Genitore(A,B) ∧ Genitore(B,D) ⇒ Nonno(A,D)
Genitore(A,B) ∧ Genitore(B,E) ⇒ Nonno(A,E)
Genitore(A,C) ∧ Genitore(C,F) ⇒ Nonno(A,F)
Genitore(A,C) ∧ Genitore(C,G) ⇒ Nonno(A,G)

Questa ipotesi soddisfa i due esempi positivi e non viola nessun esempio negativo.

Pertanto, l'ipotesi ha una buona probabilità d'essere vera.

Nota. La macchina non sa nulla sulle relazioni Nonno(A,G) e Nonno(A,G) ma, visti i buoni risultati dell'ipotesi, può considerarle vere.

E così via