Machine Machine LearningLearning

Come migliorarsi attraverso l’esperienza

Rossi Fabio2004-05-12

Indice

Apprendimento Automatico Definizioni Applicazioni

Alberi di decisione Definizione, obbiettivi Esempi

Inductive logic Programming Definizioni, tassonomie Alcune regole e tecniche

Definizioni di Apprendimento Automatico Definizione1:

Learning is constructing or modifying representations of what is being experienced[Michalski 1986]

Definizione2: Learning denotes changes in the system that are

adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more efficiently and more effectively the next time [Simon 1984]

Definizioni di Apprendimento Automatico Apprendere = migliorare la capacità di esecuzione di

un certo compito, attraverso l’esperienza Migliorare nel task T Rispetto ad una misura di prestazione P Basandosi sull’esperienza E

E = esempi di comportamenti “positivi” o “negativi” forniti da un istruttore, oppure un sistema di “ricompense”.

In A.I. : Tecniche che consentono ad agenti (o sistemi automatici ) di migliorare il proprio comportamento attraverso l’analisi delle proprie esperienze.

Impieghi dell’Apprendimento Automatico1. Data Mining (estrazione di conoscenza):

scoprire regolarità e patterns in dati multi-dimensionali e complessi (es. cartelle cliniche).

2. Miglioramento delle performance: macchine che migliorano le loro capacità (es. movimenti di un robot).

3. Software adattabili: programmi che si adattano alle esigenze dell’utente (es. Letizia).

Scelte nella definizione di un sistema di apprendimento1. Componenti Migliorabili: decidere quali

sono le componenti sulle quali “lavorare”

2. Scelta e Rappresentazione di una “funzione obiettivo” che rappresenti il compito

3. Scelta di un algoritmo di apprendimento

4. Modalità di training: supervisionato, guidato da obiettivi

2. funzione obiettivo

Funzione obiettivo: espressione formale della conoscenza appresa. Viene usata per determinare le prestazioni del programma di apprendimento.

Esempi di funzioni obiettivo: polinomi, alberi di decisione, reti neurali, insiemi di regole….

peso

alte

zza

++

++

---

A=bP

2. funzione obiettivo e funzione appresa

Nota: Difficilmente un sistema riesce ad apprendere perfettamente una funzione obbiettivo f (l’esempio della funzione altezza-peso è un caso).

In genere viene appresa un funzione, avente la forma prescelta (polinomio, regole,..), che rappresenta una stima , o IPOTESI (indicata con h), per la funzione obiettivo.

L’obiettivo è di apprendere una h che approssimi f “il meglio possibile”.

3. algoritmo di apprendimento Scelta dell’algoritmo e della funzione obiettivo

ovviamente correlate Metodi statistici

Bayesian learning Markov models

Metodi algebrici Gradient descent Support Vector Machines

Metodi knowledge-based Alberi di decisione Regole di associazione

4. Modalità di training

Basato sull’informazione a disposizione: Supervisionato (esempi disponibili) Con rinforzo (premi a fronte di comportamenti

corretti) Non supervisionato (senza esempi)

Basato sul ruolo dell’apprendista (learner) Apprendimento passivo (apprende da esempi a-

priori) Apprendimento attivo (apprende anche durante il

funzionamento)

4. Modalità di training

Definiamo:KB Conoscenza baseKA Conoscenza aggiuntivaE Input EsternoMi Motore Inferenziale

Apprendimento Dichiarativo

KB + E KB*Apprendimento

4.3.a Apprendimento DeduttivoNel caso DICHIARATIVO si può avere: Apprendimento Deduttivo:

KB* = KB + KA con KB KAse KB Mi E KA = E

KA Mi E

In genere aumento l’efficienza del sistema

4.3.b Apprendimento Induttivo

Apprendimento Induttivo:KB* = KB + KA con KBKA E

Con KB* non inconsistente e relazione debole di conseguenza logica

In genere aumento la conoscenza del sistema

Apprendimento Induttivo

Il sistema parte dai fatti e dalle osservazioni derivanti da un insegnante o dall’ambiente circostante e le generalizza, ottenendo conoscenza che, auspicabilmente, sia valida anche per casi non ancora osservati (induzione). Due tipi di apprendimento induttivo:

Apprendimento da esempi: la conoscenza è acquisita a partire da un insieme di esempi positivi che sono istanze del concetto da imparare e di esempi negativi che sono non-istanze del concetto.

Apprendimento di regolarità: non c’e’ un concetto da imparare, l’obiettivo e’ quello di trovare regolarità (ovvero caratteristiche comuni) nelle istanze date.

Apprendimento Induttivo

Problema:In generale possono esserci molte ipotesi per la funzione obiettivo, alle quali è possibile assegnare, al di là del semplice criterio di consistenza con gli esempi, un grado di preferenza detto inclinazione

Approccio Incrementale: Si cerca di modificare l’ipotesi corrente ad ogni nuovo esempio fornito

Apprendimento Induttivo Definizione formale del problemaDato:

Un insieme di osservazioni (esempi, istanze) xX(es: x feature vector): x: (a1,a2..an), ai assume valori su 0,1)

Una funzione obiettivo o concetto da apprendere (indicata con f) (es. valutazione dell’interesse di una pagina web per un utente): Interessante: X0,1 dove X è l’insieme delle rappresentazioni feature-vector di pagine web

Uno spazio di ipotesi H (che dipende dalla modalità di rappresentazione di f)

Un insieme di apprendimento D:D: <(x1,f(x1))…(x, f(xm))>Dove f(xi)=1 se xi è un esempio positivo di f, 0 altrimenti

Determinare: un’ipotesi h in H tale che h(x) = f(x) x in D

Apprendimento InduttivoCompletezza e Consistenza

Alberi diAlberi diDecisioneDecisione

Metodo di apprendimentodi conoscenza simbolica

Alberi di Decisione

Un albero di decisione prende in ingresso un elemento xX descritto mediante un insieme di proprietà (coppie attributo-valore) ed emette in uscita una "decisione” binaria ( si o no)

Nodi ed Archi: corrispondono al test della proprietà che può avere come risultato uno dei Vi PROPRIETA’

V1 V2 Vk…

Alberi di Decisione

Clienti?

No Si

No

No Si

Si No Si

Si

Si

No Si

Si

0 Alcuni

Pieno

Attesa stimata?

Alternative? fame?

Prenotazione? E' Venerdì osabato?

Alternative?

Bar?Pioggia?

>6030-60 10-30 0-10

No Si NoSi

No Si No Si NoSi

No SiNo Si

Aspettare o meno?

Alberi di Decisione Obiettivo Lo scopo è, come in tutti i modelli di apprendimento

induttivo da esempi, imparare la definizione di una funzione obiettivo espressa in termini di albero di decisioni.

Un albero di decisione può essere espressa come una disgiunzione (OR) di implicazioni, aventi il valore della decisione come conclusione. Nell'esempio, la funzione obiettivo (decisione) è "Attendo" ed è implicata, fra l'altro, dalla implicazione:r Clienti(r,Pieno) AttesaStimata(r,10-30) Fame(r,N) Attendo(r)Dove r rappresenta l’istanza (di ristorante) da valutare

Alberi di Decisione

La decisione deve basarsi sull'esame di esempi D: xX, così descritti: ogni esempio è rappresentato da un vettore che rappresenta

i valori degli attributi prescelti per descrivere le istanze del dominio x: <v1=vali,v2=valj,..vn=valm>

(utilizzando attributi booleani : <a1,a2,………..aN> ai={0,1} ) gli attributi sono proprietà che descrivono gli esempi del

dominio (es: fame=si,no Prezzo = $,$$,$$$ Attesa = 0-10,10-30..,>60

Gli alberi di decisione hanno il potere espressivo dei linguaggi proposizionali, ovvero - qualsiasi funzione booleana può essere scritta

come un albero di decisione (e viceversa).

Alberi di Decisione Quando è appropriato usarli? Quando è appropriato usare alberi di decisione?

Gli esempi (istanze) sono rappresentabili in termini di coppie attributo-valore.

La funzione obiettivo assume valori nel discreto. Un albero di decisioni assegna classificazioni booleane ma può essere esteso al caso di funzioni a più valori. Non è comune, ma possibile, l'utilizzo di questa tecnica per apprendere funzioni nel continuo (discretizzando i valori di f(x)).

E’ appropriato rappresentare il concetto da apprendere mediante una forma normale disgiuntiva.

I dati di apprendimento possono contenere errori, oppure attributi di cui il valore è mancante.

Alberi di Decisione Come utilizzare gli esempi D?Es. Alt. Ba r V/S Fa. Clien. Pz. Pio . Pr e. Tip. Att. Att?X1X2X3X4X5X6X7X8X9X10X11X12

SISINOSISINONONONOSINOSI

NONOSINONOSISINOSISINOSI

NONONOSISINONONOSISINOSI

SISINOSINOSINOSINOSINOSI

AlcPienAlcPiePieAlcAlcNesPiePieNesPie

$$$$$..

FrTailF.FTail..

0-1030 -60

SiNoSiSi…

Alberi di Decisione Come utilizzare gli esempi D?

L'insieme di addestramento D è l'insieme completo degli esempi sottoposti al sistema di apprendimento

Una soluzione semplice sarebbe creare una espressione congiuntiva per ogni esempio e costruire una disgiunzione: ma il sistema non avrebbe alcun potere predittivo su esempi non visti! Il problema è estrarre uno schema dagli esempi, che sia in grado di estrapolare esempi non visti

Alberi di DecisioneAlgoritmo L'obiettivo è di estrarre uno schema coinciso. Rasoio di Ockham: l'ipotesi più probabile è la più semplice che

sia consistente con tutte le osservazioni. Il problema di identificare l'albero più piccolo è intrattabile.

Tuttavia esistono euristiche che consentono di trovare alberi "abbastanza" piccoli.

L'idea consiste nell’analizzare dapprima gli attributi più importanti, ovvero quelli che discriminano di più.

Supponendo per ora di poter fare questa scelta ad ogni passo i, l'algoritmo di creazione di un albero delle decisioni da un set di esempi D è il seguente:

Alberi di Decisione Algoritmo1. Scelgo l’attributo più importante come radice e

suddivido gli esempi2. Per ogni nodo successore:

Se ci sono sia es. positivi che negativi ricorsivamente applico l’algoritmo con un attributo in meno

Se sono tutti es. positivi metto la foglia SI Se sono tutti es. negativi metto la foglia NO Se non ci sono esempi restituisco un valore di default

calcolato in base alla maggioranza del nodo progenitore Se non ci sono più attributi ma ho ancora esempi misti ho

una situazione di errore (rumore) o di vero non determinismo

InductiveInductiveLogic Logic

ProgrammingProgrammingPer la rappresentazionedegli esempi e dei concetti

Conoscenza e ApprendimentoCome utilizzare la conoscenza a prioriL’approccio induttivo “puro” cerca ipotesi:

Ipotesi Descrizioni Classificazioni.

Ovviamente cerca Ipotesi “semplici” e consistenti con le descrizioni

Conoscenza e ApprendimentoCome utilizzare la conoscenza a prioriSchema KBIL:

knowledge Based Inductive LearningLa conoscenza di fondo e le nuove ipotesi vengono combinate per spiegare gli esempi.

Fondo Ipotesi Descrizioni Classificazioni

Approccio induttivobasato sullaConoscenza

osservazioni Ipotesi predizioni

Conoscenzaa priori

Inductive Logic ProgrammingInductive Logic ProgrammingDefinizioneDefinizione

E’ il settore dell’Apprendimento Automatico che impiega la programmazione logica come linguaggio di rappresentazione degli esempi e dei concetti

ML + LP = ILP

Inductive Logic ProgrammingInductive Logic ProgrammingDefinizione del problemaDefinizione del problema

Dati: un insieme P di possibili programmi un insieme E+ di esempi positivi un insieme E- di esempi negativi un programma logico consistente B, tale che

B e+, per almeno un e+ E+ Trovare:

un programma logico P P tale che e+ E+, B,P e+ (P è completo) e- E-, B,P e- (P è consistente)

Inductive Logic ProgrammingInductive Logic ProgrammingTerminologiaTerminologia B: background knowledge, conoscenza a

priori, predicati di cui conosciamo già la definizione.

E+ E- costituiscono il training set P programma target, B,P è il programma

ottenuto aggiungendo le clausole di P dopo quelle di B.

P viene detto hypothesis space. Definisce lo spazio di ricerca. La descrizione di tale spazio delle ipotesi prende il nome di language bias.

B,P e si dice "P copre e"

Inductive Logic ProgrammingInductive Logic ProgrammingEsempioEsempio Apprendimento del predicato father.

Dati P : programmi logici contenenti clausole

father(X,Y) :- αcon α congiunzione di letterali scelti fra

parent(X,Y),parent(Y,X),male(X),male(Y),female(X),female(Y)

B= { parent(john,mary),male(john),parent(david,steve),male(david),parent(kathy,ellen),female(kathy)}

Inductive Logic ProgrammingInductive Logic ProgrammingEsempioEsempio E+={father(john,mary),father(david,steve)} E-={father(kathy,ellen),father(john,steve)} Trovare:

un programma per calcolare il predicato father che sia consistente e completo rispetto ad E+, E-

Possibile soluzione: father(X,Y):-parent(X,Y),male(X).

Altro Esempio

Inductive Logic ProgrammingInductive Logic ProgrammingAree di ApplicazioneAree di Applicazione acquisizione di conoscenza per sistemi esperti knowledge discovery nei database: scoperta di

informazioni potenzialmente utili dai dati memorizzati in un database

scientific knowledge discovery: generazione di una teoria scientifica a partire da osservazioni + generazione di esperimenti discriminanti + test della teoria

software engineering: sintesi di programmi logici inductive engineering: costruzione di un modello

di un dispositivo partendo da esempi del suo comportamento.

Inductive Logic ProgrammingInductive Logic ProgrammingApplicazioni di successoApplicazioni di successo predizione della relazione struttura - attività

nella progettazione di medicine predizione della struttura secondaria delle

proteine, importante per determinare l'attività di una medicina.

classificazione dei documenti in base alla loro struttura

diagnosi di guasti in apparati elettromeccanici regole temporali per la diagnosi di guasti ai

componenti di satelliti

Inductive Logic ProgrammingInductive Logic ProgrammingClassificazione dei sistemiClassificazione dei sistemiEsistono diverse dimensioni di classificazione dei sistemi di ILP. Possono richiedere che tutti gli esempi siano dati all'inizio

(batch learners) oppure possono accettarli uno ad uno (incremental learners).

Possono apprendere un solo predicato alla volta (single predicate learners) oppure più di uno (multiple predicate learners).

Durante l'apprendimento possono fare domande all’utente per chiedere la validità delle generalizzazioni e/o per classificare esempi generati dal sistema (interactive learners) oppure non avere interazione con l'esterno (non-interactive learners).

Infine, un sistema può imparare una teoria da zero oppure partendo da una teoria preesistente incompleta e/o inconsistente (theory revisors).

Inductive Logic ProgrammingInductive Logic ProgrammingClassificazione dei sistemiClassificazione dei sistemi

Sebbene si tratti di dimensioni indipendenti, i sistemi esistenti appartengono a due gruppi opposti.

Da una parte ci sono i sistemi batch, non interattivi che apprendono da zero un concetto alla volta (empirical systems);

dall'altro ci sono i sistemi incrementali, interattivi che fanno theory revision e imparano più predicati alla volta (interactive or incremental systems)

Inductive Logic ProgrammingInductive Logic ProgrammingRelazione di generalità I sistemi apprendono una teoria compiendo una

ricerca nello spazio delle clausole ordinato secondo la relazione di generalità.

Nel caso della programmazione logica induttiva la relazione di generalità e’ basata su quella di θ-sussunzione:

La clausola C1 θ -sussume C2 se esiste una sostituzione θ tale che C1θ C2.

Si dice che una clausola C1 e’ almeno tanto generale quanto una clausola C2 (e si scrive C1 ≥ C2) se C1 θ-sussume C2

C1 e’ piu’ generale di C2 (C1>C2) se C1 ≥ C2 ma non C2 ≥ C1

Inductive Logic ProgrammingInductive Logic ProgrammingEsempio di Esempio di θ-sussunzione C1=grandfather(X,Y)←father(X,Z). C2=grandfather(X,Y)←father(X,Z),parent(Z,Y). C3=grandfather(john,steve)←father(john,mary),

parent(mary,steve).

C1 θ-sussume C2 con la sostituzione vuota θ= C1 θ-sussume C3 con la sostituzione

θ={X/john,Y/steve,Z/mary}. C2 θ-sussume C3 con la sostituzione

θ={X/john,Y/steve,Z/mary}.

Inductive Logic ProgrammingInductive Logic Programming proprietà della proprietà della θ-sussunzione La θ-sussunzione ha l’importante proprietà che se C1 θ-

sussume C2 allora C1 C2. Non e’ pero’ vero viceversa. Per questa ragione la θ-sussunzione viene utilizzata per

rappresentare la relazione di generalità: essa approssima la relazione di generalità intuitiva che è basata sulla relazione di conseguenza logica.

Inductive Logic ProgrammingInductive Logic ProgrammingAlgoritmiAlgoritmi Gli algoritmi per ILP si dividono in bottom-up e

top-down a seconda che utilizzino operatori di generalizzazione o specializzazione.

Gli algoritmi bottom-up partono dagli esempi (specifici o bottom) e li generalizzano ottenendo una teoria che li copre.

Vengono utilizzati degli operatori di generalizzazione ottenuti invertendo le regole deduttive di unificazione, risoluzione e implicazione

Inductive Logic ProgrammingInductive Logic ProgrammingAlgoritmi Top-DownAlgoritmi Top-Down Gli algoritmi top-down imparano programmi

generando le clausole in maniera sequenziale (una dopo l’altra). La generazione di una clausola avviene partendo da una clausola generale (con il body vuoto) e specializzandola (applicando un operatore di specializzazione o raffinamento) fino a che non copre più nessun esempio negativo.

Inductive Logic ProgrammingInductive Logic ProgrammingTop-Down: criteri di Top-Down: criteri di terminazioneterminazione Gli algoritmo top-down differiscono tra di loro a

seconda del criterio di necessita’ e di sufficienza. In genere, il criterio di Sufficienza richiede che tutti

gli esempi positivi siano coperti. In genere, il criterio di Necessità richiede che

nessun esempio negativo sia coperto dalla clausola. Nel caso di dati rumorosi, questo criterio può essere rilassato e si può ammettere la copertura di un certo numero di esempi negativi.

Inductive Logic ProgrammingInductive Logic Programming Top-Down: Esempio Top-Down: Esempio P : father(X,Y) :- α con α

{parent(X,Y),parent(Y,X), male(X),male(Y),female(X),female(Y)}

B= { parent(john,mary),male(john), parent(david,steve),male(david), parent(kathy,ellen),female(kathy)}

E+={father(john,mary),father(david,steve)} E-={father(kathy,ellen),father(john,steve)}

Inductive Logic ProgrammingInductive Logic Programming

1° passo di specializzazione father(X,Y) :- true.copre tutti gli e+ ma anche gli e-

2° passofather(X,Y) :- parent(X,Y).copre tutti gli e+ ma anche l'e- father(kathy,ellen).

3° passofather(X,Y) :- parent(X,Y), male(X).copre tutti gli e+ e nessun e-

Gli esempi positivi coperti vengono rimossi, E+ diventa vuoto e l'algoritmo termina generando la teoria:

father(X,Y) :- parent(X,Y), male(X).

BibliografiaBibliografia

Fonti delseminario

BibliografiaBibliografiaMachine LearningMachine Learning T. M. Mitchell, Machine Learning, McGraw-

Hill,1997 J. R. Quinlan, C4.5: Programs for machine

learning, Morgan Kaufmann Publishers, San Mateo, California, 1993

J. R. Quinlan, Improved Use of Continuous Attributes in C4.5, Journal of Artificial Intelligence Research, 4, pag. 77--90, 1996. ftp://ftp.cs.cmu.edu/project/jair/volume4/quinlan96a.ps

I.H. Witten, E. Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, 1999.

BibliografiaBibliografiaInductive Logic ProgrammingInductive Logic Programming S. Muggleton e C. Feng, Efficient induction of logic

programs, Proceedings of the 1st Conference on Algorithmic Learning Theory Ohmsma, Tokyo, pag. 368-381, 1990.

G.D. Plotkin. A note on inductive generalisation.In B. Meltzer and D. Michie, editors, Machine Intelligence 5, pages 153-163. Edinburgh University Press, Edinburgh, 1969.

J. R. Quinlan, Determinate literals in inductive logic programming, Proceedings of Twelfth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1991.