First Order Inductive Learner (FOIL)

Descrizione

Nell'ambito dei metodi di apprendimento induttivo applicabili al linguaggio della logica dei predicati, un contributo significativo e' stato portato da FOIL, introdotto da Quinlan nel 1990.
Ispirato al precedente ID3 , sempre di Quinlan, riprende da questo l'idea di applicare misure di teoria dell'informazione alla definizione di funzioni euristiche in grado di guidare la ricerca nello spazio delle ipotesi.

FOIL appartiene alla categoria dei medodi ILP di tipo "top-down", basati su specializzazione. Funziona in modo batch, richiedendo misure euristiche che considerano l'intero insieme di esempio.

L'algoritmo riceve come parametro il nome e l'arita' di un predicato da apprendere e produce un insieme di regole la cui disgiunzione ne descrive la migliore approssimazione, espressa in relazione ad un determinato gruppo di predicati fissato .

Le ipotesi che possono essere apprese da FOIL sono rappresentabili in forma simile alle clausole di Horn, ma, a differenza di queste, non consentono l'uso di simboli di funzione, mentre ammettono letterali negati nel corpo della clausola.

La struttura dell'algoritmo comprende un ciclo esterno che, come per CN2, ha per obiettivo l'apprendimento una singola regola alla volta. In ogni iterazione vengono eliminati dall'insieme di esempio le istanze positive che soddisfano la nuova regola. Questo ciclo termina quando tutti gli esempi positivi risultano coperti da una delle definizioni ottenute.

Un ciclo piu' interno effettua la ricerca nello spazio delle ipotesi , partendo dall'ipotesi piu' generale relativa al predicato da apprendere ( p(X₁, ... ,X₁) :- true. ), considera, di volta in volta, l'insieme ottenuto applicando all'ipotesi corrente l'Operatore di Specializzazione. Tra le ipotesi candidate viene scelta quella che presenta il migliore guadagno di informazione, rispetto agli esempi dati. La nuova ipotesi cosi' ottenuta costituisce la base per la prossima specializzazione, e la ricerca termina quando tutti gli esempi negativi risultano correttamente discriminati.

Algoritmo FOIL:

FOIL( TargetPredicate, DefPredicates, Examples)

Pos <- { <e,x> in Examples | TargetPredicate( e ) = true }
Neg <- { <e,x> in Examples | TargetPredicate( e ) = false }
Learned_Rules <- {}

while ( |Pos| > 0 ) do // --- outer loop -----------------

// Learn a new rule

NewRule <- TargetPredicate(X) :- true. // most general
NewRuleNeg <- Neg

while ( |NewRuleNeg| > 0 ) do // --- inner loop ---------

CandidateRules <- spec-op( NewRule, DefPredicates )

BestRule <- argmax InfoGain( R, NewRule )

^{R in CandidateRules}

NewRuleNeg <- { <e,x> in NewRuleNeg | BestRule(e) = true }

LearnedRules <- LearnedRules + NewRule
Pos <- Pos - { <e,x> in Pos | NewRule(e) = true }

return LearnedRules

Generazione Ipotesi Candidate

Durante la fase di ricerca, l'ipotesi corrente viene espansa nell' insieme di clausole piu' specializzate, ottenute aggiungendo un letterale alle precondizioni della clausola originale.

spec-op( p(X₁,...,X_n) :- L₁,...,L_n, DefPreds ) = { p(X₁,...,X_n) :- L₁,...,L_n, L_n+1}

Dove il letterale di espansione considerato L_n+1puo' essere uno dei tipi seguenti:

q(Y₁,...,Y_k), dove q e' un predicato di DefPreds, mentre Y₁,...,Y_ksono variabili gia' presenti nella regola, oppure nuove variabili, introdotte dal letterale. In ogni caso, almeno una variabile deve essere gia' compresa nella regola.
Equal( X_i,...,X_j), dove X_i,...,X_jsono variabili gia' presente nella regola
Un letterale ottenuto per negazione da uno dei due casi precedenti

Consistendo di un solo letterale, la specializzazione prodotta risulta minimale, nel senso che vengono considerate in modo sistematico tutte le clausole che specializzano in modo piu' generale possibile, la clausola originale.

Euristica del Guadagno di Informazione

La ricerca nello spazio delle ipotesi effettuata da FOIL e' di tipo "hill-climbing", selezionando ad ogni passo solo la migliore ipotesi candidata.
In maniera analoga ad ID3 , la bonta' di una specializzazione s, rispetto all'ipotesi originale h, viene calcolata rispetto alla misura di "guadagno di informazione" , cosi' definita:

                                                  p_sp_h
InfoGain(s,h)    =    t ( log₂ _______ - log₂ _______ )
                                               p_s + n_s p_h + n_h

dove p_s , n_se p_h, n_hcorrispondono, rispettivamente, al numero di esempi positivi e negativi che soddisfano o meno le regole s e h, mentre t indica il numero di esempi coperti dalla regola h, che soddisfano anche s.

Assunzione di Mondo Chiuso

Gli esempi del predicato da apprenedere vengono forniti a FOIL in due insiemi E⁺e E^- , contenenti le tuple p(a₁,...,a_n), ..., p(b₁,...,b_n) relative alle istanze positive e negative. Nel caso in cui fossero disponibili solo gli esempi positivi, e possibile ricorrere all'assunzione di mondo chiuso per generare gli esempi negativi in modo automatico, in una fase di pre-elaborazione. Questa operazione e' possibile solo in domini completamente specificati, dove e' possibile conoscere in anticipo tutte le possibili istanze positive di un certo concetto.
I predicati utilizzabili per la definizione induttiva, devono essere espressi in forma estensionale, vale a dire mediante enumerazione di tutti i possibili fatti ground. Anche in questo caso, e' possibile ricorrere ad una fase di elaborazione per tradurre in forma estensionale, eventuali clausole contenenti variabili.

Apprendimento di Clausole Ricorsive

La definizione del predicato da apprendere attraverso esempi positivi, permette la sua assimilazione agli altri predicati di definizione, espressi anchessi in forma estensionale.
Questo permette l'apprendimento di predicati ricorsivi come dimostrato negli esempi di utilizzo.
A questo riguardo, e' possibile segnalare che FOIL e' stato applicato con successo a problema dell'apprendimento del predicato quicksort, notoriamente ricorsivo.

Trattamento di Dati Imperfetti

In applicazioni reali, spesso i dati di esempio sono imprecisi o incompleti. Questo determina la produzione di regole estremamente complesse, necessarie per considerare i casi particolari introdotti dal rumore. Per ovviare a questo problema FOIL utilizza un criterio di arresto della fase di ricerca, basato sulla restrizione della complessita' di descrizione. Questo criterio termina la ricerca quando la lunghezza della clausola corrente, valutata rispetto a una forma di codifica ottimale, supera la lunghezza necerraria a fornire una descrizione esplicita degli esempi positivi.
Qualora questo si verifichi, la clausola ottenuta viene scartata, utilizzando al suo posto l'insieme degli esempi positivi considerati durante la ricerca.

succ prec indice