Apprendimento Automatico:
Apprendimento Non Supervisionato
Roberto Navigli
1
Cap. 8 & 9 [Tan, Steinbach, Kumar]
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
Supervisione nell’Apprendimento
(arancio, rotondo, classe=
(giallo, lungo, classe=
)
(giallo, rotondo, classe=
(giallo, lungo, classe=
colore
)
forma
)
)
algoritmo di apprendimento
supervisionato
colore
(arancio, rotondo)
(giallo, rotondo)
(giallo, rotondo)
(giallo, lungo)
algoritmo di apprendimento
non supervisionato
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
.
.. .
forma
2
Clustering
• Suddivide esempi non etichettati in sottoinsiemi disgiunti
(cluster), tali che:
– Gli esempi in uno stesso gruppo sono “molto” simili
– Gli esempi in gruppi diversi sono “molto” differenti
• Scopre nuove categorie in modo non supervisionato
(a priori non vengono fornite etichette per le categorie)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
3
Clustering: un esempio
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
4
Clustering: un esempio
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
5
Clustering: un esempio
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
6
Clustering: un esempio
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
7
Tipi di Clustering
• Clustering gerarchico (hierarchical clustering)
– Formano cluster iterativamente utilizzando cluster
precedentemente costituiti
• Clustering partitivo (partitional clustering)
– Crea una sola partizione degli esempi in cluster minimizzando
una certa funzione di costo
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
8
Clustering Gerarchico
• Costruisce una tassonomia gerarchica ad albero a partire
da un insieme di esempi non etichettati
animale
vertebrato
pesce rettile anfibio mammif.
invertebrato
verme insetto crostaceo
• L’applicazione ricorsiva di un algoritmo di clustering può
produrre un clustering gerarchico
• Distinguiamo due tipi di clustering gerarchico:
– Agglomerativo (bottom-up)
– Divisivo (top-down)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
9
Clustering Partitivo
• I metodi di clustering partitivo ottengono una singola
partizione dei dati, invece di una struttura di clustering
(es. albero di clustering)
• Richiedono di specificare il numero di cluster k
desiderati
• Il numero di cluster k può essere determinato
automaticamente generando esplicitamente clustering
per diversi valori di k e scegliendo il miglior risultato
secondo la funzione di valutazione del clustering
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
10
Clustering Gerarchico Agglomerativo
• Assume l’esistenza di una funzione di similarità per determinare la
similarità di due istanze
• Algoritmo:
Parti con un cluster per ogni istanza
Finché non c’è un solo cluster:
Determina i due cluster ci e cj più simili
Sostituisci ci e cj con un singolo cluster ci  cj
• La “storia” di fusione costituisce un albero binario o gerarchia di
clustering (dendrogramma)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
11
Metriche per determinare la distanza
• Nota: se la distanza è normalizzata tra 0 e 1, la
similarità sim(x, y) è data da 1-d(x, y)
• Distanza euclidea (norma L2):
 
L2 ( x , y ) 
m
2
(
x

y
)
 i i
i 1
• Norma L1 (o distanza di Manhattan):
m
 
L1 ( x , y )   xi  yi
i 1
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
12
Cosine Similarity
m
 
 
x y
cos( x , y )    
xy
x y
i
i 1
m
x
i 1
2
i
i
m
2
y
 i
i 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
13
Coefficiente di Jaccard
m
 
J ( x, y) 
 (x
 1  yi  1)
 (x
 0  yi  0)
i
i 1
m
i 1
i
• Esempio: coefficiente di Jaccard tra 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
14
Misurare la Similarità tra Cluster
• Nel clustering gerarchico agglomerativo, utilizziamo una
funzione di similarità che determina la similarità tra due
istanze: sim(x, y)
• Come calcolare la similarità di due cluster ci e cj sapendo
come calcolare la similarità tra due istanze nei due
cluster?
– Single Link: Similarità dei due membri più simili
– Complete Link: Similarità dei due membri meno simili
– Group Average: Similarità media tra i membri
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
15
Single Link
Agglomerative Clustering
• Utilizziamo la similarità massima tra coppie di istanze:
 
sim (ci ,c j )  max sim ( x , y )
xci , yc j
• A causa di un effetto concatenamento, può restituire
cluster “lunghi e fini”
– Adeguato in certi domini, come il raggruppamento di isole
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
16
Esempio di Single Link
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
17
Complete Link Agglomerative Clustering
• Basato sulla minima similarità tra coppie di istanze:
 
sim (ci ,c j )  min sim ( x , y )
xci , yc j
• Crea cluster più sferici, normalmente preferibili
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
18
Esempio di Complete Link
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
19
Calcolare la Similarità tra Cluster
• Dopo aver fuso i cluster ci e cj, la similarità del clustering
ottenuto rispetto a un altro cluster arbitrario ck può
essere calcolata come segue:
– Single Link:
sim ((ci  c j ), ck )  max( sim (ci , ck ), sim (c j , ck ))
– Complete Link:
sim ((ci  c j ), ck )  min( sim (ci , ck ), sim (c j , ck ))
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
20
Group Average
Agglomerative Clustering
•
Per determinare la similarità tra ci e cj usa la similarità media su tutte le
coppie nell’unione di ci e cj.
 
1
sim (ci , c j ) 
sim ( x , y )


ci  c j ( ci  c j  1) x( ci c j ) y( ci c j ): y  x
•
•
Compromesso tra single e complete link.
Se si vogliono cluster più sferici e netti, si deve determinare la similarità
media tra coppie ordinate di istanze nei due cluster (invece che tra coppie di
istanze nell’unione):
1
sim (ci , c j ) 
ci c j
 
  sim ( x, y)


xci yc j
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
21
Clustering Partitivo
• Si deve fornire il numero desiderato di cluster k
• Si scelgono k istanze a caso, una per cluster, chiamate semi
(seeds)
– Si formano i k cluster iniziali sulla base dei semi
• Itera, riallocando tutte le istanze sui diversi cluster per migliorare il
clustering complessivo
• Ci si ferma quando il clustering converge o dopo un numero
prefissato di iterazioni
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
22
K-means
• Assume istanze a valori reali
• I cluster sono basati su centroidi o media dei punti in
un cluster c:

1
 (c) 
x

| c | xc
• Le istanze vengono riassegnate ai cluster sulla base
della distanza rispetto ai centroidi dei cluster attuali
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
23
Algoritmo K-means
K-means(distanza d, insieme delle istanze X)
Seleziona k istanze a caso {s1, s2, …, sk} X come semi.
Finché clustering non converge o si raggiunge criterio di stop:
Per ogni istanza x  X:
Assegna x al cluster cj tale che d(x, sj) è minimale
Aggiorna i semi al centroide di ogni cluster, ovvero
per ogni cluster cj:
sj = (cj)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
24
K-means: Esempio (k=2)
Scegli i semi
Riassegna i cluster
Calcola i centroidi
Riassegna i cluster
x
x
x
x
Calcola i centroidi
Riassegna i cluster
Convergenza!
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
25
Obiettivo di K-means
• L’obiettivo di k-means è di minimizzare la somma del quadrato della
distanza di ciascun punto in X rispetto al centroide del cluster cui è
assegnato:
k

i 1
2
d
(
x
,

)

i
xci
• Così come per gli algoritmi genetici, trovare il minimo globale è un
problema NP-hard
• E’ garantito che l’algoritmo k-means converga a un minimo locale
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
26
Ad ogni passo, K-means cerca il clustering ottimale
• Dimostrazione (assumiamo x a una sola dimensione per semplicità):
 K
 
 i 1

( i  x) 

K
xci


 k
i 1
2
 ( i  x) 2


 k
xci
 (  k  x) 2
  2(  k  x )  0

 k
xck
xck
 2   x  0
k
xck

xck
k

xck
x
xck
| ck |  k 
k 
x
xck
1
x

| ck | xck
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
27
Scelta dei Semi
• I risultati possono variare notevolmente sulla base della
selezione dei semi
• Alcuni semi possono portare a un basso tasso di
convergenza o a convergere su clustering sub-ottimali
• Si possono selezionare buoni semi usando euristiche o
come risultato di un altro metodo
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
28
Scelta di semi ottimale
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
29
Scelta di semi non ottimale
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
30
Text Clustering
• I metodi di clustering possono essere applicati a documenti di testo
in modo semplice
• Tipicamente, si rappresenta un documento mediante vettori
TF*IDF (term frequency*inverse document frequency)
normalizzati e si utilizza la similarità del coseno
• Applicazioni:
– Durante la fase di recupero dei documenti di un sistema di Information
Retrieval (IR), si possono fornire documenti nello stesso cluster di
quello inizialmente recuperato per aumentare la recall del sistema
– I risultati di un sistema di IR possono essere presentati per gruppi
– Produzione automatizzata di tassonomie gerarchiche di documenti per
scopi di navigazione (stile Yahoo & DMOZ).
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
31
Clustering basato su grafi
• Basati su una rappresentazione dei dati sotto forma di
grafo di prossimità:
– Un nodo è un’istanza
– Un arco rappresenta la prossimità tra due istanze (es. distanza)
f1
0.3
0.5
f2
0.5
0.2
0.3
f3
f4
0.4
0.1
f5
0.2
f6
– Eventuale passo di pre-processing: sparsificazione del grafo
• Per ogni nodo, mantieni solo i k vicini più simili o i vicini la cui similarità è >
di una certa soglia
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
32
Esempi di clustering di grafi a vari livelli di granularità
Da: G Karypis, V Kumar (1999). "A Fast and High Quality Multilevel Scheme for Partitioning
Irregular Graphs". Siam Journal on Scientific Computing.
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
33
MST (Minimum Spanning Tree) Clustering
• Clustering basato sul concetto di albero ricoprente
– Un albero ricoprente minimo è un sottografo che 1) non ha cicli,
2) contiene tutti i nodi del grafo, 3) ha il minimo peso totale tra
tutti gli alberi ricoprenti
• E’ un algoritmo di tipo gerarchico divisivo
MST-Clustering(G)
• Calcola il MST per il grafo di dissimilarità
• Finché non rimangono solo cluster singoletti
– Crea un nuovo cluster eliminando un arco corrispondente alla
maggiore dissimilarità
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
34
Esempio
f1
0.3
0.5
f2
0.5
0.2
0.3
f3
f4
0.4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
35
Esempio
f1
0.3
0.5
f2
0.5
0.2
0.3
f3
f4
0.4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
36
Esempio
f2
f1
0.3
0.2
0.3
f3
f4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
37
Esempio
f2
f1
0.3
0.2
0.3
f3
f4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
38
Esempio
f2
f1
0.3
0.2
f3
f4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
39
Esempio
f2
f1
0.3
0.2
f3
f4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
40
Esempio
f2
f1
0.2
f3
f4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
41
Esempio
f2
f1
0.2
f3
f4
0.1
f5
0.2
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
42
Esempio
f2
f1
0.2
f3
f4
0.1
f5
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
43
Esempio
f2
f1
f3
f5
f4
f6
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
44
Hard vs. Soft Clustering
• Tipicamente il clustering assume che ogni istanza sia
assegnata a un solo cluster
– Questo non permette di esprimere l’incertezza riguardo
l’appartenenza di un’istanza a più cluster
• Il soft clustering fornisce una distribuzione di
probabilità per ogni istanza rispetto all’appartenenza a
ciascun cluster
– Le probabilità di appartenenza di ogni istanza su tutti i cluster
devono sommare a 1
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
45
Problemi nell’Apprendimento Non Supervisionato
• Come valutare il clustering?
– Valutazione interna:
• Separazione netta dei cluster (ad es., l’obiettivo di K-means)
• Corrispondenza con un modello probabilistico dei dati
– Valutazione esterna
• Confronta i cluster con etichette di classe note su dati di
benchmark
• Pseudowords
• Clustering sovrapponibili
• Collo di bottiglia della conoscenza
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
46
Valutazione esterna del clustering
• Supponiamo di avere un insieme di dati annotati con classi scelte a
mano
• Applichiamo il nostro algoritmo di clustering
• Valutiamo misure di aderenza del clustering rispetto al dataset
• Entropia:
pij 
• Purezza:
mij
mj
L
K
, H (c j )   pij log pij , H (C )  
i 1
j 1
K
Pu(c j )  max pij , Pu(C )  
• dove:
i 1,..., L
mj
j 1
mj
m
m
H (c j )
Pu(c j )
– mij è il numero di istanze nel cluster j di classe i
– mj è il numero di istanze nel cluster j
– m è il numero complessivo di istanze
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
47
Esempio di valutazione esterna con entropia e purezza
• Ho un dataset di 10 istanze (m=10)
• Supponiamo di ottenere il seguente clustering:
c2
c1
• Classi associate a mano alle istanze:
(1) ,
(2)
• m1=6, m2=4
• m1(1)=4, m1(2)=2, m2(1)=1, m2(2)=3
6
4
6
4
4 2
2
4
1
1 3
3
H (c1 )  H (c2 )  ( log  log )  ( log  log )
10
10
10 6
6 6
6 10 4
4 4
4
6
4
6 4 4 3 43 7
Pu (C )  Pu (c1 )  Pu(c2 ) 



10
10
10 6 10 4
10
10
H (C ) 
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
48
Collo di bottiglia della conoscenza
• Spesso si pone un problema di disponibilità e creazione
di dataset annotati
• Metodi debolmente supervisionati o semi-supervisionati
• Es. Metodi di Bootstrapping
– Si utilizzano pochi esempi annotati a mano A (semi) e moltissimi
esempi non annotati U
– Si addestra un classificatore su A e si classificano gli esempi in U; i
“migliori” esempi in U vengono aggiunti ad A. Si ripete il processo
finché U non è vuoto o si raggiunge una certa soglia
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
49
Collo di bottiglia della conoscenza
• Spesso si pone un problema di disponibilità e creazione
di dataset annotati
• Metodi debolmente supervisionati o semi-supervisionati
• Es. Active learning
– Si addestra un classificatore con un insieme di addestramento A
– Si annotano automaticamente i dati in un insieme non etichettato U
– Si selezionano quelle istanze per le quali il classificatore ha avuto
un basso grado di confidenza (istanze incerte)
– Si chiede l’intervento umano nel validare quelle istanze
– Si aggiungono le istanze validate all’insieme di addestramento A
– Si ripete il processo finché non si raggiunge una condizione di
terminazione (es. una soglia fissata di confidenza)
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
50
Task: Word Sense Induction (Induzione di significati)
• Data una parola, vogliamo apprendere le classi di
significato che essa esprime:
bar =
,
,
, … ,
• Obiettivo: dato un insieme di parole che appaiono
insieme alla parola obiettivo (cooccorrenze) in un
dataset di riferimento, raggruppare le cooccorrenze in
accezioni
• Si esprime ogni accezione mediante un insieme di
parole. Ad esempio:
– bar1 = { counter, drink, pub, …, restaurant }
– bar2 = { chocolate, soap, wax, cake, …, tablet }
– bar3 = { wood, metal, piece, rigid, fasten, weapon, …, escape }
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
51
Valutazione WSI: Pseudoparole (Schutze, 1992)
• Si crea un dataset contenente istanze (ovvero, parole) che
si sanno appartenere tutte a una singola classe di
significato:
– Es. parole monosemiche (con un solo significato)
– Pizza, kalashnikov
• Dati gli esempi di pizza e kalashnikov:
–
–
–
–
Ieri siamo andati a mangiare una
pizza
al ristorante
Margherita:
pizza
con margherita e pomodoro
Sparò un colpo di kalashnikov in aria.
Chi mise il kalashnikov in mano al bambino?
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
52
Valutazione WSI: Pseudoparole (Schutze, 1992)
• Si crea un dataset contenente istanze (ovvero, parole) che
si sanno appartenere tutte a una singola classe di
significato:
– Es. parole monosemiche (con un solo significato)
– Pizza, kalashnikov
• Dati gli esempi di pizza e kalashnikov:
–
–
–
–
Ieri siamo andati a mangiare una pizzakalashnikov al ristorante
Margherita: pizzakalashnikov con margherita e pomodoro
Sparò un colpo di pizzakalashnikov in aria.
Chi mise il pizzakalashnikov in mano al bambino?
• Si crea una pseudoparola pizzakalashnikov che
rimpiazza le occorrenze di pizza e kalashnikov
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
53
Valutazione WSI: Pseudoparole (Schutze, 1992)
• Si crea un dataset contenente istanze (ovvero, parole)
che si sanno appartenere tutte a una singola classe di
significato:
– Es. parole monosemiche (con un solo significato)
– Pizza, kalashnikov
• Dati gli esempi di pizza e kalashnikov si crea una
pseudoparola pizzakalashnikov
• Tutte le occorrenze delle due parole vengono sostituite
con la pseudoparola (ma è nota la classe corretta per
ciascuna istanza)
– Si può generare un dataset con n classi usando n parole
• Si applica l’algoritmo di clustering alle cooccorrenze di
pizzakalashnikov
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
54
Precisione e Recall (cf. (Bordag, 2006))
• Dato un cluster del nostro clustering, come determinare se
è corretto oppure no?
– La sua precisione di retrieval (rP) è la percentuale di parole
relative a una parola originaria (es. pizza o kalashnikov)
– La sua recall di retrieval (rR) è la percentuale di cooccorrenze
della parola originaria contenute nel cluster
– Un cluster è considerato accurato se rP ≥ soglia-p e rR ≥ soglia-r
• Si calcolano precisione e recall per determinare la qualità
dell’intero clustering
– Precisione: frazione di cluster “accurati”
– Recall: numero di cluster “accurati” diviso numero di pseudoparole
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
55
Applicazione: Clustering-based Information Retrieval
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
56
Applicazione: Clustering-based Information Retrieval
Apprendimento Automatico: Apprendimento Non Supervisionato
Roberto Navigli
57