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)
Basato sull’informazione a disposizione
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
f : V1  V2  V3  ..  O
• La misura della prestazione consiste nel minimizzare l’errore di
approssimazione della funzione obiettivo sugli esempi a disposizione
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 sul ruolo dell’apprendista
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?
Apprendimento da Esempi
(example-based learning)
Apprendimento induttivo, o da
esempi
y
y O, x V
f :V  O
x
• 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.
Definizione formale del problema
Dato:
• Un insieme di osservazioni (esempi, istanze) xX
(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 aV, 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: X0,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 ndimensionale )
• 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
sopra
ripiani:#
1


 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
Scelta della funzione obiettivo
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 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=marzo
Rappresentazione vettoriale delle istanze, es: x:<1,0,0>
Funzione obiettivo: 3-monomial (congiunzione di n3
letterali)
c=abc con H: ( abc,abc,abc,abc,abc,abc,abc,abc,ab,ab,...
)
Esempi: D= (<0,0,0>,0) (<1,0,0>,1) (<1,0,1>,1)
h  ab
• Se esistono varie ipotesi che si adattano ai dati, ci deve
essere un criterio di preferenza
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: c  a1  a2  a5 esprimibile anche come
un vettore (1,0,?,?,1)
Esempi D
Un esempio: apprendere un profilo di utente
per web browsing
attributo
D=
Dominio Piattafor
ma
Browser
Giorno
Schermo Continen Click?
te
edu
com
com
org
Net3
NetCom
IExpl
Net2
Lu
Lu
Sab
Gio
XVGA
XVGA
VGA
XVGA
Mac
Mac
PC
Unix
America
America
Asia
Europa
Si
Si
No
Si
c
• Assunzione: gli esempi non contengono errori (NON
SEMPRE VERO!!!)
valori
• “Click” è il nostro concetto c ed assume valori in (0,1)
Rappresentare le ipotesi
• Supponiamo che le ipotesi h in H abbiano la forma di congiunzione di
k letterali (k6 nell’esempio):
i
1
2
3
4
5
6
v
• h:  va ,vb ,vc , vd ,ve ,v f  dove j rappresenta il valore j-esimo
dell’attributo i-esimo (es Schermo=XVGA)
• Ogni letterale vij 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?
H  (3  2)  (3  2)  (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. h1  gen h2 iff x X,h2 (x)  1  h1 (x)  1
– h2 è vera solo se lo è h1
– Es: h1=<edu,Mac,?,Lun,?,?>
h2=<edu,Mac,IE,Lun,?,Europa>
Ordinamenti per generalità sullo
spazio delle ipotesi
X
H
h3
h2
h1
X: istanze
H:ipotesi
generalità
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:
i
a
– Per ogni condizione su un attributo j in h, esegui:
i
• Se xi non è “coperto” da h, sostituisci a j con la
condizione immediatamente più generale che sia
soddisfatta da x
3. Emetti l’ipotesi h
esempio
X
h0 H
h1
h2,3
h4
generalità
D
X1= (<edu,mac,Net3,Lun,XVGA,America>,1)
X2= (<com,mac,Net3,Mar,XVGA,America>,1)
X3= (<com,PC,IE,Sab,VGA,Eur>,0)
X4= (<org,Unix,Net2,Mer,XVGA,America>,1)
H
h0 = <0,0,0,0,0,0>
h1=<edu,mac,Net3,Lun,XVGA,America>
h2=<?,mac,Net3,?,XVGA,America>
h3=<?,mac,Net3,?,XVGA,America>
h4=<?,?,?,?,XVGA,America>
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=hH  sS,gG t.c. ggenhgens
Algoritmo VS (1)
Gle ipotesi più generali in H
Sle 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
gG, gh
• Rimuovi da S ogni ipotesi s che sia più generale di
altre ipotesi in S
Esempio (a)
d1= (<edu,mac,Net3,Lun,XVGA,America>,1)
<edu,Mac,Net3,Lun,XVGA,America
<0,0,0,0,0,0>
>
S0
<?,?,?,?,?,?>
G0
Esempio (b)
<edu,Mac,Net3,Lun,XVGA,America
<?,Mac,?,?,XVGA,America> >
S1
<?,?,?,?,?,?>
G1
d2=(<com,mac,NetCom,Mar,XVGA,America>,1)
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>
S3
S2
<?,?,?,?,?,?>
<?,Mac,?,?,?,?><?,?,?,?,XVGA,?>
,?,?,?,?><?,?,?,?,?,America>G2

d3=(<com,PC,IE,Sa,VGA,Eur> 0)
G3
Dopo i primi 3 esempi, quali ipotesi
sopravvivono?
<?,Mac,?,?,XVGA,America>
<?,Mac,?,?,XVGA,?>
S3
S2
<?,Mac,?,?,?,America> , <?,?,?,?,XVGA,America>
<?,Mac,?,?,?,?> <?,?,?,?,XVGA,?> , <?,?,?,?,?,America> 
G3
Come dovrebbe essere classificati questi esempi:
Positivo
d4 = <edu,Mac,IE,Ven,XVGA,America> ???????
d5 = <org,Unix,NetCom,Gio,VGA,Europa> Negativo
???????
?? Come cambia VS??
d6 = <com,PC,Net2,Mer,XVGA,America> ???????
Un altro esempio (apprendere una
funzione 3-monomial)
TRUE
x x
y
y
 ( x y ), 
z
z
 ( x , y, z ), 
xy xz
yz x z yz x y yz x y yz xy xz
xy xz

x yz x yz x yz x yz xyz xyz xyz xyz
FALSE
Complessità
• Supponiamo che la funzione obiettivo, o concetto, abbia la
forma di un monomial
cn  an1  an2  ...a0
ai 0,1,
• Per esempio,supponiamo il concetto “esatto” sia
c1  1 (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!
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:
(warm cloudy)( cool sunny)

• 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
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-)
Sx1x2x3….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 apprendimento
Come variano le prestazioni del sistema di apprendimento
all'aumentare del learning set
Misure di prestazione: nTP=numero di veri positivi
nTN = numero di veri negativi nFP=numero di falsi positivi
nFN= numero di falsi negativi
Accuratezza= (nTP+ nTN )/( nTP+ nTN + nFP+ nFP)
Accuracy
1
0
Dimensione del LS
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. Rumore
In 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 irrilevanti
Supponi amo di considerare il problema della
predizione del lancio di un d ado.
Consideriamo i seguenti attributi che descrivono
gli esempi:
Ora, Mese, Colore del dado
Fintanto che non si trovano esempi con
descrizioni identiche, il sistema sarà in grado d i
costruire 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 kmonomial
– Apprendono solo classificatori CONSISTENTI con D,
quindi non sono toleranti al rumore!!
Prossimo algoritmo: decision trees. Minore bias, tollera
rumore