Apprendimento Automatico:
Apprendimento Pigro (Lazy Learning)
Roberto Navigli
Cap. 5.3 [Tan, Steinbeck & Kumar]
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
1
Concetto di base: Pigrizia
Pigrizia mentale (Devoto-Oli 2008): atteggiamento di chi
trascura l’arricchimento delle proprie conoscenze […]
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
2
In altre parole
• Il principio di base è quello di ritardare il processo di
modellazione dell’insieme di addestramento finché non
è richiesto per classificare le istanze di test
– Lazy learner vs. eager learner
• Il più semplice lazy learner: rote classifier
– Apprende tutto a memoria
– Classifica solo ciò che fa match con almeno un esempio
dell’insieme di addestramento
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
3
Siamo seri!
• Per rendere l’approccio più flessibile, cerchiamo gli
esempi di addestramento relativamente più simili
all’istanza di test
• “Se cammina come una papera, fa qua qua come una
papera e somiglia fisicamente a una papera, allora
probabilmente è una papera!”
– Apprendimento basato su istanze
• Un noto rappresentante è l’algoritmo k-Nearest
Neighbours (kNN)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
4
Chi sono i k “vicini più vicini”?
• Le istanze sono rappresentate mediante punti nello
spazio m-dimensionale degli m attributi
• I k “vicini più vicini” (nearest neighbours) di un’istanza di
test x sono i k punti dell’insieme d’addestramento più
vicini a x
+
- +
-
+ +
x+ +
+ +
+
+
+
k=1
+
- +
-
+ +
x+ +
+ +
+
+
+
k=2
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
+
- +
-
+ +
x+ +
+ +
+
+
+
k=3
5
Come avviene la classificazione?
• Si sceglie la classe di maggioranza dei k esempi più
vicini:
yˆ  arg max
yY
  ( y, y )
( xi , yi )Dx
i
dove Dx è il sottoinsieme di D dei k esempi più vicini a x
(majority voting)
• Se k è troppo piccolo si rischia overfitting dovuto al
rumore nell’insieme di addestramento
• Se k è troppo grande, potremmo includere istanze
troppo dissimili dall’istanza di test
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
6
Algoritmo kNN
kNN(k, D)
For each istanza di test x do



Calcola d(x, xi) per ogni esempio (xi, yi)  D
Determina l’insieme Dx  D dei k esempi più vicini a x
Classifica x: yˆ  arg max
 ( y, yi )
yY

( xi , yi )Dx
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
7
Posso migliorare la classificazione?
• Vista la dipendenza dalla scelta di k, è possibile
migliorare la classificazione di kNN pesando il
contributo di ciascun esempio secondo la sua distanza:
1
wi 
d ( x, xi ) 2
• Quindi la classe di maggioranza è scelta come segue:
yˆ  arg max
yY
 w  ( y, y )
( xi , yi )Dx
i
i
(majority voting pesato sulla distanza)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
8
Alcune metriche per determinare la distanza
• Distanza euclidea:
 
d ( x, y) 
m
2
(
x

y
)
 j j
j 1
• Distanza di Manhattan (o city block):
m
 
d ( x, y)   x j  y j
j 1
• Distanza di Minkowski (generalizzazione):
 
d ( x, y)  r
m
| x
j 1
r

y
|
j
j
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
9
Misure di Prossimità: Cosine Similarity
• Nota: se la distanza è normalizzata tra 0 e 1, la similarità
sim(x, y) è data da 1-d(x, y)
m
 
 
xy
cos( x , y )    
xy
x
j 1
m
x
j 1
j
yj
m
2
j
2
y
 j
j 1
• Esempio: similarità del coseno di due vettori di documenti:

x  (1,1,1,0,0,1)

y  (1,0,0,1,1,1)
  1 1  1  0  1  0  0 1  0 1  1 1 2 1
cos( x , y ) 
 
4 2
4 4
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
10
Misure di Prossimità: Coefficiente di Jaccard
m
 
J ( x, y) 
 (x
j 1
m
 (x
j 1
j
j
 1  y j  1)
 0  y j  0)
• Esempio: similarità di Jaccard di due vettori di documenti:

x  (1,1,1,0,0,1)

y  (1,0,0,1,1,1)
  2
J ( x, y) 
6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
11
kNN “in a nutshell”
• Vantaggi:
– Non è necessario appprendere né costruire un’astrazione
(modello) a partire dai dati
– kNN può adattare i propri confini di decisione in modo arbitrario,
producendo una rappresentazione del modello più flessibile
– Si può arricchire incrementalmente l’insieme di addestramento
• Svantaggi:
– Classificare le istanze di test è costoso, perché dobbiamo
calcolare i valori di prossimità tra ciascun esempio di
addestramento e l’istanza di test
– Essendo la classificazione fatta in modo locale (al contrario
degli alberi di decisione), kNN è suscettibile al rumore
– La misura di prossimità può essere dominata da alcuni attributi
(es. altezza vs. peso)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
12
Esercizio
• Provate ad adattare l’algoritmo ID3 al paradigma di
apprendimento pigro
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
13