Modalità di Apprendimento e apprendimento di concetti

Example-based learning

Tipi di apprendimento

• 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)

Apprendimento supervisionato da esempi

• Si ha a disposizione un insieme di esempi classificati x: <v1,v2,..vn,o> dove vi sono valori delle variabili di ingresso (ad es. i valori delle fi che caratterizzano lo stato di una scacchiera), ed o è l’uscita (es. il valore di V(b)). Prendono anche il nome di attributi o features.

• Implica l’esistenza di un istruttore che conosce la risposta corretta

• Si apprende una funzione obiettivo

• La misura della prestazione consiste nel minimizzare l’errore di approssimazione della funzione obiettivo sugli esempi a disposizione

f : V1 V2 V3 .. O

min(e) min ˆ f f

Basato sull’informazione a disposizione

Apprendimento per rinforzo

• L’apprendista interagisce con l’ambiente e riceve una ricompensa (numerica) positiva o negativa (es: se un robot che fa goal il “peso” della sequenza di azioni che lo ha portato a fare goal viene aumentato)

• Cosa si apprende: una strategia di comportamento (un “piano” o sequenza di azioni)

• Misura della prestazione: si cerca di massimizzare “a lungo termine” la ricompensa complessivamente ottenuta

Basato sull’informazione a disposizione

Apprendimento non supervisionato

• L’esperienza di apprendimento è rappresentata da dati non classificati (ad esempio, scontrini fiscali, cartelle cliniche, pagine web )

• Cosa si apprende: regole associative fra i dati (es: if cocacola then patatine)

• E’ difficile trovare misure di prestazione a priori per questo tipo di associazioni. Spesso, valutazioni da parte di esperti umani.

Basato sull’informazione a disposizione

Apprendimento attivo e passivo

• Ruolo passivo dell’apprendista:– L’apprendista può apprendere solo dai dati che

vengono messi a disposizione (E)

• Ruolo attivo dell’apprendista:– L’apprendista può fare domande ed esperimenti (es. un

web advisor può chiedere esplicitamente all’utente di valutare il suo gradimento sull’operato dell’advisor)

– Problema: come limitare l’intrusività dell’apprendista in modo ottimale?

Basato sul ruolo dell’apprendista

Apprendimento da Esempi (example-based learning)

Apprendimento induttivo, o da esempi

• Supervisionato• L' apprendimento da

osservazioni, o induttivo, consiste nella descrizione di una funzione f a partire da un insieme di coppie ingresso/uscita dette esempi.x

y

y O, x V

f : V O

Definizione formale del problemaDato:

• Un insieme di osservazioni (esempi, istanze) xX (es: x è un vettore di caratteristiche o feature vector:

x: (a1,a2..an), ai assume valori su elementi di un alfabeto i, ad esempio 0,1, oppure nel continuo aV, V)

• Una funzione obiettivo o concetto da apprendere (indicata con c o 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 c) (es: se c è una funzione lineare in n variabili, H è un iperpiano n-dimensionale )• Un insieme di apprendimento D:

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

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

Istanze e spazio delle istanze

• Come rappresentare gli “oggetti” del mondo sui quali si vuole apprendere qualcosa?

• Comunemente si usa una rappresentazione vettoriale x:(a1,a2..an). Ogni x è un vettore in uno spazio n-dimensionale

• Alcuni algoritmi usano rappresentazioni strutturate (esempio, grafi) per evidenziare relazioni esistenti fra le caratteristiche, o features, che descrivono un oggetto

Esempio: imparare a classificare mobili

• X: mobilia• Attributi o features: gambe ripiani cassetti ante • Valori degli attributi: N+ (es gambe=0,1,2,3,4)• Rappresentazione vettoriale:

x(gambe,ripiani,cassetti, ante)

xi (4,1,0,0)

• Rappresentazione strutturata

ripiani :#1 sopra gambe :# 4

Rappresentazione delle istanze

• Ovviamente una rappresentazione strutturata è più adeguata in alcune applicazioni (ad esempio immagini, robotica) ma gli algoritmi di apprendimento risultano molto più complessi

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

Scelta della funzione obiettivo

Scelta di una funzione obiettivo• L’apprendista solitamente considera

una classe H di ipotesi, es. alberi di decisione, reti neurali, polinomi, monomi booleani

• Il metodo di apprendimento consiste in una strategia di ricerca nello spazio delle ipotesi

Esempio

Es: decidere se portare l’ombrello o meno, a seconda del tempo. Come rappresentare l’input dell’apprendista?Tre attributi : a,b,c

(0,1,?) col significato a=nuvoloso, b=freddo, c=marzoRappresentazione vettoriale delle istanze, es: x:<1,0,0>Funzione obiettivo: 3-monomial (congiunzione di n3 letterali)c=abc con H: ( ) Esempi: D= (<0,0,0>,0) (<1,0,0>,1) (<1,0,1>,1)

• Se esistono varie ipotesi che si adattano ai dati, ci deve essere un criterio di preferenza

a bc,abc,abc, abc,abc,abc,abc,abc, ab, ab,...

h ab

Algoritmi di apprendimento da esempi

• Due semplici algoritmi (Find_S e Version Space)

• Si applicano a:– Funzioni booleane c: X{0‚1}– Monomial , cioè congiunzioni di k letterali dove k

è compreso fra 1 ed n, n é il numero di attributi (features) utilizzati per rappresentare ogni istanza x di X

– Es: esprimibile anche come un vettore (1,0,?,?,1)c a1 a2 a5

Un esempio: apprendere un profilo di utente per web browsing

D=

• Assunzione: gli esempi non contengono errori (NON SEMPRE VERO!!!)

• “Click” è il nostro concetto c ed assume valori in (0,1)

Dominio Piattaforma

Browser Giorno Schermo Continente

Click?

edu

com

com

org

Mac

Mac

PC

Unix

Net3

NetCom

IExpl

Net2

Lu

Lu

Sab

Gio

XVGA

XVGA

VGA

XVGA

America

America

Asia

Europa

Si

Si

No

Si

attributo

valori

c

Ese

mp

i D

Rappresentare le ipotesi

• Supponiamo che le ipotesi h in H abbiano la forma di congiunzione di k letterali (k6 nell’esempio):

• h: dove rappresenta il valore j-esimo dell’attributo i-esimo (es Schermo=XVGA)

• Ogni letterale può essere– Un valore specifico (es: Giorno= lu,mar,merc..)– Un “don’t care” (?)– Non può assumere valori (es. Screen=)Es:h: <com,?,?,sab,?,america>– Quante ipotesi posso formulare?

va1 ,vb

2,vc3, vd

4,ve5,v f

6 v ji

v ji

H (3 2) (32) (4 2) (7 2) (2 2) (3 2)

Ipotesi dell’apprendimento induttivo

• Ogni ipotesi che approssima il comportamento della funzione obiettivo su un numero “sufficentemente grande” di esempi lo approssimerà sufficentemente anche su campioni non osservati

• Perché ciò è vero? Dalla teoria statistica del campionamento, (per estrarre parametri di popolazioni da campioni), e dalla computational learning theory (vedremo tutto questo più avanti nel corso)

Apprendimento di concetti=ricerca nello spazio delle ipotesi

• La ricerca può essere aiutata ordinando parzialmente le ipotesi

• Un ordinamento può essere fatto sulla base della generalità delle h– Def.– h2 è vera solo se lo è h1– Es: h1=<edu,Mac,?,Lun,?,?> h2=<edu,Mac,IE,Lun,?,Europa>

h1 gen h2 iff x X,h2(x) 1 h1(x) 1

Ordinamenti per generalità sullo spazio delle ipotesi

h1

h2h3

X H

generalitàX: istanze H:ipotesi

Ogni ipotesi “copre” cioè soddisfa, zero o più istanze classificate dell’insieme D in X

FIND-S: cerca l’ipotesi massimamente specifica

(per apprendere funzioni booleane)

1. Inizializza h come l’ipotesi più specifica in H

2. Per ogni esempio positivo (xi,1) esegui:– Per ogni condizione su un attributo in h, esegui:

• Se xi non è “coperto” da h, sostituisci con la condizione immediatamente più generale che sia soddisfatta da x

3. Emetti l’ipotesi h

a ji

aji

esempio

h2,3

h1

X H

generalità

h4

h0

X1= (<edu,mac,Net3,Lun,XVGA,America>,1) h0 = <0,0,0,0,0,0>X2= (<com,mac,Net3,Mar,XVGA,America>,1) h1=<edu,mac,Net3,Lun,XVGA,America>X3= (<com,PC,IE,Sab,VGA,Eur>,0) h2=<?,mac,Net3,?,XVGA,America>X4= (<org,Unix,Net2,Mer,XVGA,America>,1) h3=<?,mac,Net3,?,XVGA,America>

h4=<?,?,?,?,XVGA,America>

D H

Problemi dell’algoritmo Find_S

• Convergenza: non è chiaro quando (e se) ha appreso un modello del concetto c (condizione arresto?)

• Consistenza: poiché gli esempi negativi vengono ignorati, non è possibile rilevare inconsistenze

• Trova un’ipotesi massimamente specifica (poca capacità di generalizzare)

• In funzione di H, possono esistere parecchie ipotesi massimamente specifiche.

Algoritmo dello spazio delle versioni

• Def. Un’ipotesi h è consistente con un set di esempi di training D del concetto obiettivo c iff h(x)=c(x) <x,c(x)>D

• Uno spazio delle versioni VSH,Ddove H è lo spazio delle ipotesi e D il training set, è il subset di di H consistente con D

• Come ottenere VSH,D? – Elencare ed eliminare ad ogni nuovo esempio in D: non pratico!

– Algoritmo VS

Rappresentazione dello spazio delle versioni

• Idea chiave: memorizzare solo le ipotesi “di confine”, utilizzando l’ordinamento parziale delle ipotesi in H

• Insieme G in VSH,D : è l’insieme di ipotesi massimamente generali

• Insieme S in VSH,D : è l’insieme di ipotesi massimamente specifiche

• Ogni ulteriore ipotesi h in VSH,D giace nello spazio compreso fra G e S

VSH,D=hH sS,gG t.c. ggenhgens

Algoritmo VS (1)

Gle ipotesi più generali in H

Sle ipotesi più specifiche in H

Es.<0,0,0,0,0,0>

<?,?,?,?,?,?>

S0

G0

Algoritmo VS (2)

• Per ogni d: <x,c(x)> in D, esegui:

• Se d è positivo (c(x)=1), esegui:

– Rimuovi da G le ipotesi inconsistenti con d

– Per ogni ipotesi s in S che non sia consistente con d esegui:

• Rimuovi s da S

• Aggiungi ad S tutte le ipotesi h che siano generalizzazioni minime di s, e consistenti con d , e gG, gh

• Rimuovi da S ogni ipotesi s che sia più generale di altre ipotesi in S

Esempio (a)

<0,0,0,0,0,0>

<?,?,?,?,?,?>

S0

G0

d1= (<edu,mac,Net3,Lun,XVGA,America>,1)

<edu,Mac,Net3,Lun,XVGA,America>

Esempio (b)

<edu,Mac,Net3,Lun,XVGA,America>

<?,?,?,?,?,?>

S1

G1

d2=(<com,mac,NetCom,Mar,XVGA,America>,1)

<?,Mac,?,?,XVGA,America>

Esempio (c)

<?,Mac,?,?,XVGA,America>

<?,?,?,?,?,?>

S2

G2

Algoritmo VS (2)

• Se d è un esempio negativo:– Elimina in S ogni ipotesi h inconsistente con d– Per ogni ipotesi g in G inconsistente con d:

• Elimina g da G• Aggiungi a G tutte le specializzazioni minime h di g

tali che h sia consistente con d, ed esistano in S ipotesi più specifiche di h (cioè, h non “sconfini” in S)

• Elimina da G ogni ipotesi g’ che sia meno generale di un’altra ipotesi g” in G

– not (g’,g”) g’G, g”G t.c. g”geng’)

Esempio (d)

<?,Mac,?,?,XVGA,America>

<?,?,?,?,?,?>

S2

G2

d3=(<com,PC,IE,Sa,VGA,Eur> 0)

<?,Mac,?,?,?,?><?,?,?,?,XVGA,?> ,?,?,?,?><?,?,?,?,?,America> G3

S3

Dopo i primi 3 esempi, quali ipotesi sopravvivono?

<?,Mac,?,?,XVGA,America> S2

<?,Mac,?,?,?,?> <?,?,?,?,XVGA,?> , <?,?,?,?,?,America> G3

S3

<?,Mac,?,?,XVGA,?> <?,Mac,?,?,?,America> , <?,?,?,?,XVGA,America>

Come dovrebbe essere classificati questi esempi: d4 = <edu,Mac,IE,Ven,XVGA,America> ???????d5 = <org,Unix,NetCom,Gio,VGA,Europa> ???????d6 = <com,PC,Net2,Mer,XVGA,America> ???????

PositivoNegativo?? Come cambia VS??

Un altro esempio (apprendere una funzione 3-monomial)

TRUE

zzyyxx

xyzzxyzyxzyxyzxzyxzyxzyx

FALSE

xzxyzxyxyzyxzyyxzyzxzyzxyx

),( yx

),,,( zyx

Complessità • Supponiamo che la funzione obiettivo, o concetto, abbia la forma

di un monomial

• Per esempio,supponiamo il concetto “esatto” sia

(sempre vero!!) per cui h=(?,?,….?)• Se gli esempi in D sono descritti da n attributi booleani, es

d0=(<1,0,0,…..0>,1), occorrono nel caso peggiore 2n-1 esempi per apprendere il concetto (ogni attributo può essere 0,1 o ? ) Devo avere evidenza del fatto che c=1 per ogni valore di ogni attributo!)

• L’algoritmo dovrà eseguire 2n-1 passi!

cn an 1 an 2 ...a0ai 0,1 ,

c1 1

BIAS

• “Bias” o inclinazione è ogni criterio utilizzato (oltre ai dati di training) per preferire un’ipotesi ad un’altra

• inclinazioni: – la scelta del modello di rappresentazione per H (ad esempio, h è una

congiunzione di variabili booleane, o una rete neurale..)

– La scelta dell’ algoritmo di ricerca nello spazio H (ad esempio, la scelta dell’algoritmo Find_S ha un’inclinazione per ipotesi massimamente specifiche)

Uno spazio “biased”

• Se scelgo di utilizzare k-monomials, come nel caso precedente, non posso rappresentare ipotesi del tipo:

• La scelta della funzione c ha dunque orientato l’apprendimento verso un sottoinsieme di ipotesi che non è detto sia adatto ad apprendere soluzioni per il problema considerato

(warm cloudy ) ( cool sunny )

Un apprendista privo di inclinazioni• Idea: seleziona uno spazio H che esprima ogni concetto apprendibile (cioè, H

X* il power set di X)• H’ :l’insieme delle ipotesi che si ottengono combinando ipotesi di H

(congiunzione di letterali) mediante gli operatori Es: (piattaforma=Unix piattaforma= Mac) ((Piattaforma=PC)D: D+ {x1,x2,..}, D- {y1,y2,..} (esempi+ e esempi-)Sx1x2x3….xi (si limita ad accettare gli esempi positivi)G y1 y2.. yj..(si limita a escluder gli esempi negativi)Ogni nuovo esempio aggiunge una disgiunzione a S (se +) o una congiunzione a

G (se -)Ma in questo modo, i soli esempi classificabili da S e G sono gli esempi osservati!

Per convergere, bisognerebbe far osservare all’algoritmo ogni possibile elemento di X!

In assenza di un’inclinazione non è possibile apprendere alcuna generalizzazione degli esempi osservati!!

Un’inclinazione è necessaria!

• La “bontà” di un sistema di apprendimento discende dalla adeguatezza dell’inclinazione prescelta

• Come scegliere una buona inclinazione?– Conoscenza del dominio– Conoscenza della sorgente dei dati di

apprendimento– Semplicità e generalità (rasoio di Occam)

Alcuni aspetti correlati all’apprendimento di concetti da esempi

1. Dimensionamento del learning set D (studio delle curve di apprendimento)

2. Sovradattamento

3. Rumore

4. Attributi irrilevanti

1. Studio delle Curve di apprendimento

• Problema: se sottopongo al sistema un insieme di esempi insufficienti, o rumorosi, o ambigui, posso apprendere ipotesi il cui potere predittivo è insufficente.

• Un algoritmo di appendimento è buono se può prevedere con buona precisione la classificazione di esempi non visti

1. Curve di apprendimentoCome variano le prestazioni del sistema di apprendimentoall'aumentare del learning set

Misure di prestazione: nTP=numero di veri positivinTN= numero di veri negativi nFP=numero di falsi positivinFN= numero di falsi negativiAccuratezza= (nTP+ nTN)/( nTP+ nTN+ nFP+ nFP)Accuracy

Dimensione del LS

1

0

2. Sovradattamento

Def. Dato uno spazio di ipotesi H, una ipotesi h si dice sovradattata (overfit) rispetto ai dati di apprendimento D se esiste una ipotesi alternativa h' tale che h commette un errore minore di h' sul set di addestramento D, ma h' produce un errore minore sui dati di test T.

2. Sovradattamento

• Quali sono le cause del sovradattamento?• Errori nella classificazione dei dati in D• Esempi idiosincratici (la distribuzione di probabilità dei

fenomeni in D non è la stessa di X, es molti esempi di balene nell’apprendimento di una definizione di mammifero)

• Regolarità incidentali fra i dati (es. molti pazienti che soffrono di diabete abitano in una certa area - ma nell'area è stata fatta una campagna di prevenzione!)

• Attributi irrilevanti (colore dei capelli nell’esempio dell’agente esaminatore)

3. RumoreIn alcuni casi, due o più esempi con la stessa descrizione possono avere classificazioni diverse (questo può essere dovuto ad ambiguità, oppure ad errori, o ad un insieme di attributi non sufficentemente descrittivo) (Esempio: optical character recognition)

4. Attributi irrilevantiSupponiamo di considerare il problema dellapredizione del lancio di un dado.Consideriamo i seguenti attributi che descrivonogli esempi:Ora, Mese, Colore del dado

Fintanto che non si trovano esempi condescrizioni identiche, il sistema sarà in grado dicostruire un modello predittivo, che saràtotalmente inattendibile.

Conclusioni• Apprendimento da esempi:

– Rappresentare lo spazio delle istanze– Rappresentare la funzione obiettivo, detta in questo caso funzione di

classificazione c– Creare un insieme di addestramento– Identificare un algoritmo

• Problemi:– La scelta della funzione c determina una “inclinazione”– La scelta degli attributi per rappresentare le istanze ha anche essa un

rilievo: ad esempio attributi irrilevanti possono influire negativamente– Il dimensionamento di D ha effetti sull’apprendimento (curve di

adattamento e problema dell’overfitting o sovradattamento)– La presenza di rumore o attributi non noti in D può rallentare

l’apprendimento, o impedirlo nel caso di algoritmi che apprendono solo ipotesi consistenti con D

Conclusioni (2)

• Abbiamo studiato due “semplici” algoritmi:

Find-S e VS• Quali problemi pongono, rispetto a quelli elencati

nella precedente slide?– Forte “bias” determinato dalla scelta di c: un k-

monomial

– Apprendono solo classificatori CONSISTENTI con D, quindi non sono toleranti al rumore!!

Prossimo algoritmo: decision trees. Minore bias, tollerarumore