Learning finite MixtureModels
Giuseppe Manco
Clustering





La problematica del clustering è relativa al learning
non supervisionato
Abbiamo un dataset con istanze la cui etichetta è
sconosciuta
Obiettivo del clustering è individuare raggruppamenti
delle istanze del dataset
I raggruppamenti devono essere tali per cui ci sia alta
similarità fra le istanze delle stesso cluster, mentre ci
sia alta dissimilarità fra le istanze di cluster differenti
Il clusterer deve ricostruire la struttura nascosta alla
base dei dati a disposizione
Model-based Clustering



In questo approccio si suppone che le istanze del
dataset siano state generate a partire da un mix di
modelli probabilistici
Per questa ragione si parla anche di Probabilistic
Clustering
Il clusterer, quindi, deve stimare quali siano i
parametri delle distribuzioni che hanno più
verosimilmente generato il dataset di training
Stima per massima verosimiglianza
(maximum likelihood) (1/2)


Avendo i dati che provengono da una distribuzione di
forma nota si vogliono stimare i parametri per cui è
più verosimile osservare i dati che si hanno
effettivamente a disposizione
Sia X  x1 , x2 , , xN  il dataset a disposizione, si
definisce la likelihood come:

 

N

L  | X  P X |    p xi | 

i1

Dove  rappresenta il vettore di tutti i parametri della
distribuzione
Stima per massima verosimiglianza
(maximum likelihood) (2/2)


Si devono quindi trovare quali siano i parametri della
distribuzione che massimizzano la likelihood
Spesso si massimizza il logaritmo della likelihood, la
log-likelihood, perché si possono ottenere
espressioni analitiche più semplici:
 N
 N
log  L  | X    log   p  xi |      log  p  xi |   
 i 1
 i 1
Mixture-Model (1/5)



Per il clustering si utilizza l’approccio a mixturemodel
In questo contesto ogni istanza viene generata
scegliendo prima, secondo una data probabilità, una
particolare distribuzione e poi si genera l’istanza in
accordo alla distribuzione scelta
M
La distribuzione per una istanza è:
p  x     k pk  x 
k 1

Dove  k è la probabilità che venga scelta la k-ma
distribuzione, e prende il nome di mixing probability, e pk  x 
è la k-ma distribuzione
Model-Based Clustering

Clustering basato su modelli probabilistici
 Si
assume che dati siano distribuiti secondo
un mix di funzioni di densità

Per ogni funzione i parametri non sono noti
EM
 Bayesian clustering

Finite Mixture Models
K
p (x)   p(x, ck )
k 1
Finite Mixture Models
K
p (x)   p (x, ck )
k 1
K
  p (x | ck ) p (ck )
k 1
Finite Mixture Models
K
p(x)   p(x, ck )
k 1
K
  p(x | ck )p(ck )
k 1
K
  p(x | ck,  k )  k
k 1
Finite Mixture Models
K
p(x)   p(x, ck )
k 1
K
  p(x | ck )p(ck )
k 1
K
  p(x | ck,  k )  k
k 1
Modellok
Pesok
Parametrik
Esempio: Mistura di Gaussiane

Gaussian mixtures:
K
p(x)   p(x | ck,  k )  k
k 1
Esempio: Mistura di Gaussiane

Gaussian mixtures:
K
p(x)   p(x | ck,  k )  k
k 1
Ogni componente è una densità gaussiana
con media mk covarianza Sk
Example: Mixture of Gaussians

Gaussian mixtures:
K
p(x)   p(x | ck,  k )  k
k 1
Ogni componente è una densità gaussiana
con media mk e covarianza Sk
Esempio: K=2, 1-dim:
{} = {m1 , s1 , m2 , s2 , 1, π2}
0.5
p(x)
0.4
Component 1
Component 2
0.3
0.2
0.1
0
-5
0
5
10
5
10
0.5
p(x)
0.4
Mixture Model
0.3
0.2
0.1
0
-5
0
x
0.5
p(x)
0.4
Component 1
Component 2
0.3
0.2
0.1
0
-5
0
5
10
5
10
0.5
p(x)
0.4
Mixture Model
0.3
0.2
0.1
0
-5
0
x
2
p(x)
1.5
Component Models
1
0.5
0
-5
0
5
10
5
10
0.5
p(x)
0.4
Mixture Model
0.3
0.2
0.1
0
-5
0
x
Esempio: Mixture di Naïve
Bayes
K
p(x)   p(x | ck,  k )  k
k 1
Esempio: Mixture di Naïve
Bayes
K
p(x)   p(x | ck,  k )  k
k 1
d
p(x | ck , k )   p( xj | ck )
j 1
Esempio: Mixture di Naïve
Bayes
K
p(x)   p(x | ck,  k )  k
k 1
d
p(x | ck , k )   p( xj | ck )
j 1
Indipendenza condizionale per
ogni componente
Mixtures di Naïve Bayes
Termini
1
1
1
1
1
1
1
1
1
1
Documenti
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Mixtures di Naïve Bayes
Termini
1
1
1
1
1
1
1
1
1
1
Documenti
1
1
1
1
1
1
Componente 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Componente 2
Esempio: Mixtures di multinomiali



Le distribuzioni multinomiali modellano il ripetersi di
esperimenti indipendenti che possono portare a più
risultati: come il lancio di un dado (“Qual è la
probabilità che su 4 lanci esca due volte ‘1’ una
volta ‘3’ ed una volta ‘6’?)
Una multinomiale è caratterizzata dai parametri s c
che indica qual è la probabilità che si verifichi un
evento di classe c
Poiché facciamo riferimento ad un mixture-model di
k
multinomiali, poniamo s c la probabilità che si
verifichi l’evento di classe c nella multinomiale k
Esempio: Mixtures di multinomiali


Nel nostro caso, quindi, i dati che osserviamo sono
1
2
S
c
x

n
,
n
,
,
n
n
nella forma: i
i
i
i , dove
i è il numero
di eventi di classe c per l’istanza i
La probabilità di osservare una particolare istanza
generata da una distribuzione multinomiale è:

pk  xi | yik  1,  k 

 S j
  ni  !
j 1



S
j
n
 i!
j 1
 s 
S
c 1
c
n
i
k
c
Mixture-Model (2/5)

La log-likelihood in questo caso vale:
 N

log  L  | X    log   p  xi |   
 i 1

 N M

 log     k pk  xi |  k  
 i 1 k 1

M

  log    k pk  xi |  k  
i 1
 k 1

N
Sommatoria dentro il logaritmo!

Questa funzione risulta molto complessa da ottimizzare…
Mixture-Model (3/5)
Si utilizza uno stratagemma: si suppone l’esistenza
delle variabili yik che indicano se l’istanza i è stata
generata dalla distribuzione k
 La variabile yik vale 1 se l’istanza i è stata generata
dalla distribuzione k, vale 0 altrimenti.
 Queste variabili soddisfano la condizione:

M
y
k 1
ik
 1, i  1,
,N
Mixture-Model (4/5)

In questo caso la likelihood e quindi la log-likelihood
valgono:

 

N

M
L  | X ,Y  P X ,Y |     yik pk xi , yik  1, k

log L  | X ,Y

i1 k 1

 N M

 log    yik pk xi , yik  1, k 
 i1 k 1



 M

  log   yik pk xi , yik  1, k 
 k 1

i1
N


Solo un termine della sommatoria è
diverso da zero…
Mixture-Model (5/5)

Per quanto evidenziato possiamo semplificare
l’espressione della log-likelihood:

log L  | X ,Y


   y
N
M
i1 k 1
ik
 
log pk xi , yik  1, k

Questa espressione è aleatoria perché contiene le
variabili aleatorie yik
Si può soltanto massimizzarne il valore atteso
Expectation-Maximization (1/11)



Questo algoritmo di clustering viene utilizzato per stimare i
parametri del mixture-model che è alla base di un dataset
L’algoritmo migliora iterativamente il valore atteso della loglikelihood del mixture-model e con esso la stima dei parametri
dei modelli
È caratterizzato da due passi:



Expectation: nel quale si effettua un assegnamento “soft” delle istanze
ai cluster (si calcola la probabilità che un’istanza appartenga ad un
cluster)
Maximization: nel quale si utilizzano gli assegnamenti del passo
precedente per stimare, in maniera pesata in base alla probabilità di
appartenenza di un’istanza al cluster, i parametri dei modelli
Si iterano Expectation e Maximization fino alla convergenza dei
parametri che si stanno stimando
Expectation-Maximization (2/11)
Passo Expectation (g-ma iterazione)

Si definisce la funzione:

Q  ,

 g 1

 g 1 

 E log  L  | X , Y   | X ,

Questa è funzione dei parametri , ed il valore atteso
è calcolato a partire dalle stime dell’iterazione
precedente sui dati di training
Expectation-Maximization (3/11)
{Expectation}

L’espressione della funzione Q può essere riscritta
come:
N M

Q  ,

g 1

g 1
 E    yik log pk xi | yik  1, k  k | X ,

 i1 k 1

 
N
 
 
M
 
g 1
   E  yik | xi , k  log pk xi | yik  1, k  k


i1 k 1
per definizione di valore atteso



E  yik | xi , k  g 1   1 p yik  1| xi ,k  g 1  0  p yik  0 | xi , k  g 1



 p yik  1| xi ,k  g 1   ik  g 
Responsibility: è la probabilità che sia stata la distribuzione k a generare
l’istanza i, considerando corretti i parametri stimati all’iterazione
precedente
Expectation-Maximization (4/11)
{Expectation}

Valendo la relazione P(A,B|C)=P(A|B,C)P(B|C)
possiamo scrivere che:
 ik
g
 E  yik | xi ,   g 1  


p xi , yik  1|   g 1

p xi |   g 1

p yik  1|  
M


g 1
 

 p x | y
 g 1
p
y

1|

 ij
j 1
Probabilità a priori che venga scelta la
distribuzione k: la mixing probability

pk xi | yik  1,  
j
i
ij
g 1

 1,   g 1


 k  g 1  p yik  1|   g 1

Expectation-Maximization (5/11)
Passo Maximization (g-ma iterazione)

Si devono individuare i valori di  affinché venga
massimizzata la funzione Q, ovvero:

  g   arg max Q  ,   g 1



Per far questo calcoliamo le derivate parziali della
funzione Q rispetto a tutti i parametri  e le poniamo
a zero
Expectation-Maximization (6/11)
{Maximization di gaussiane}

La massimizzazione deve rispettare i seguenti
vincoli:
M

k 1

k
1
Utilizziamo, quindi, i moltiplicatori di Lagrange:
 M (g) 
f  ,    Q  ,
     j  1
 j 1

N M
 M (g) 
(g)
   ik log  pk xi yik  1, k       j  1
i 1 k 1
 j 1


( g 1)

Expectation-Maximization (6/11)
{Maximization di multinomiali}

La massimizzazione deve rispettare i seguenti
vincoli:
M
S
 k  1
k
s
 j 1
k 1

k  1,
,M
j 1
Utilizziamo, quindi, i moltiplicatori di Lagrange:
 M g  M
 S p g  
f  ,    Q  ,
     j  1    p   s t  1

 j 1
 p 1  t 1
N M
 M g  M
 S p g  
g
   ik log  pk  xi | yik  1,  k        j  1    p   s t  1
i 1 k 1

 j 1
 p 1  t 1

 g 1

Expectation-Maximization (7/11)
{Maximization}
Calcolo delle mixing probability:
f  ,    ... 
N
M
   ik
i 1 k 1
g
 M g  M
 p  xi , yik  1|  k  
 S p g  
log 
      j  1    p   s t  1
k



 j 1
 p 1  t 1
Expectation-Maximization (8/11)
{Maximization}

Derivando l’espressione mostrata:
N
f  ,  
 ir  g 
 ...    g     0
 r
i 1  r
 r
g

1
N



i 1
N
 rg 
g
i 1
N M
g

 ij
i 1 j 1
ir
f  ,   M  g 
  j 1  0

j 1
g

 ir
M

j 1
g
ij
M


 ...   p yij  1| xi ,  g 1  1
j 1
r
g
1

N
N
g

 ir
i 1
Expectation-Maximization (9/11)
{Maximization di gaussiane}
Calcolo dei parametri
delle gaussiane:
f  ,    ... 
 x m  


 i


N M
M
  1
 2 S 2  


(g)
(g)


   ik  log 
e
       j  1
i 1 k 1
  2 S

   j 1

 
Expectation-Maximization
(10/11)
{Maximization}

Derivando l’espressione
mostrata:
f  ,  
(g)
m k
f  ,  
(g)
 k
f  ,  

mk
(g)
   ik
(g)
xi
i
k
(g)
   ik
(g)
xi  m k xi  m k 
T
i
k
(g)
1

N

i
(g)
ik
Expectation-Maximization (9/11)
{Maximization di multinomiali}
Calcolo dei parametri delle multinomiali:
f  ,    ... 

 S j  

   ni  !  S
N M
j 1
g 
   nc log s k  g 
   ik    log   S

i
c

j
i 1 k 1
c 1

  ni ! 
 j 1









 M g  M
 S p g  

      j  1    p   s t  1

 j 1
 p 1  t 1



Expectation-Maximization (10/11)
{Maximization}

Derivando l’espressione mostrata:
f  ,   N  iz  g  nir
  z  g   z  0
z
s r
i 1 s r
S
f  ,  
 1   s tz  g   0
z
t 1
N
s rz  g  
g r

 iz ni
i 1
N
S
g t

 iz ni
i 1 t 1
Expectation-Maximization (11/11)

Ricapitolando
 Expectation:
 ik
g


 k  g 1 pk xi | yik  1,  g 1
M

j 1
 g 1
j

p j xi | yij  1,

 g 1

 ... 
k
 g 1
c 1
S
g

1
 
M

j 1
 s
S
j
k  g 1
c
 s
c 1
j  g 1
c
 Maximization:
N
s
kg
c

g c

 ik ni
i 1
N
S
g t

 ik ni
i 1 t 1
k
g
1

N
N
g

 ik
i 1

nic

nic
ANEMIA PATIENTS AND CONTROLS
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
EM ITERATION 1
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
EM ITERATION 3
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
EM ITERATION 5
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
EM ITERATION 10
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
EM ITERATION 15
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
EM ITERATION 25
Red Blood Cell Hemoglobin Concentration
4.4
4.3
4.2
4.1
4
3.9
3.8
3.7
3.3
3.4
3.5
3.6
3.7
Red Blood Cell Volume
3.8
3.9
4
LOG-LIKELIHOOD AS A FUNCTION OF EM ITERATIONS
490
480
Log-Likelihood
470
460
450
440
430
420
410
400
0
5
10
15
EM Iteration
20
25
Inizializzazione (1/14)


EM ha necessita di una inizializzazione
Come in tutte le tecniche di hill climbing, il risultato
dipende fortemente dalla scelta del punto iniziale
Scelta del numero di cluster (1/12)



EM, come altri algoritmi di clustering, richiede in input
il numero di cluster in cui clusterizzare il dataset di
training
Si possono sfruttare tecniche per la stima del numero
di cluster da utilizzare
Ci sono vari approcci:
 Deterministici:
come ad esempio i metodi basati
sull’information theory tipo MML e MDL, ed altri;
 Stocastici: come ad esempio la cross-validazione, ed altri;
Scelta del numero di cluster (2/12)




L’approccio utilizzato in questo lavoro e quello della
cross-validazione
Di certo non si può utilizzare la sola likelihood sui dati
di training per stimare il numero di cluster
Infatti più cluster si utilizzano più i dati verranno fittati
meglio (la log-likelihood dei dati di training è una
funzione crescente nel numero di cluster utilizzati)
Disponendo di un dataset indipendente da quello di
training per effettuare solamente test, la sua loglikelihood potrebbe risultare utile
Scelta del numero di cluster (3/12)




train
Supponiamo di avere un dataset X
per il training,
test
X
ed un altro dataset,
, per effettuare il testing
Supponiamo che sia p  x  la “vera” distribuzione alla
base dei due dataset
k 
k 
train
x |
X
Poniamo p
la distribuzione che EM
ha ricavato a partire dal dataset di training utilizzando
k cluster
k 
X train indichiamo i parametri
Con la notazione 
stimati da EM utilizzando k cluster





Scelta del numero di cluster (4/12)

La funzione

 
L   k   X train  | X train  P X train |   k   X train 


indica la likelihood dei parametri stimati rispetto al
dataset di training (è una funzione crescente di k)
La funzione

 
L   k   X train  | X test  P X test |   k   X train 

indica la likelihood dei parametri stimati rispetto al
dataset di test; indica quanto verosimilmente le
istanze del dataset di test provengano dalla
k 
k 
train
p
x
|

X
 
distribuzione stimata


Scelta del numero di cluster (5/12)

La log-likelihood relativa è:
 
lktest  log L   k   X train  | X test


che è una funzione di k fissati i restanti parametri ed
il dataset di training
Questa funzione, intuitivamente, dovrebbe risultare
più utile nella stima del numero corretto di cluster.
Mostriamo che ciò è vero…
Scelta del numero di cluster (6/12)

Poniamo opportunamente:
test
ik  

 
lk
1

log L   k   X train  | X test
Ntest
Ntest

che è l’opposto della log-likelihood per istanza
Calcoliamone il valore atteso:
E ik 
 

 lktest 
1
log P X test |   k   X train  
 E 

...


E


N
Ntest 
test 

sono variabili aleatorie
  Ntest  k 

1
k 
train
che provengono tutte

E log   p xi |   X   
Ntest   i 1
dalla stessa distribuzione

p  x , quella “vera”
1 Ntest 
k 
k 
train

 ...  
E
log
p
x
|

X



i

Ntest i 1 

 


Scelta del numero di cluster (7/12)
Sostituiamo xi con x̂ ed otteniamo:
1 N
log p  k   xˆ |   k   X train   
E
E ik   

  

test
N test

i 1

 
1
N test E log p  k  xˆ |   k   X train  


N test

 
   p  xˆ  log p  k  xˆ |   k   X train  dxˆ

p  xˆ 

 ...   p  xˆ  log  k 
 p xˆ |   k   X train 



è indipendente da k, e
misura l’entropia della
distribuzione p  x 



 dxˆ  p  xˆ  log  1  dxˆ

 p  xˆ  




distanza di Kullback-Leibler, misura la distanza fra due distribuzioni;
è sempre positiva e vale zero quando le distribuzioni coincidono
Scelta del numero di cluster (8/12)



La log-likelihood del dataset di test, opportunamente
scalata, è una stima della distanza fra le due
distribuzioni, quella “vera” e quella ricavata da EM
Quasi mai si dispone di un ampio dataset di test
indipendente da quello di training
Si utilizzano ripetutamente porzioni del dataset di
training per effettuare il test: in questo caso si parla di
cross-validazione
Scelta del numero di cluster (9/12)
{cross-validazione}


Supponiamo che si effettui M volte la ripartizione del
dataset di training e sia Si la porzione utilizzata per il
calcolo della log-likelihood di test
La log-likelihood di cross-validazione è:
1
cv
lk 
M
1

M
k 
train
log
L

X
\ Si  | Si


 
 log  P  S | 

train
X
\ Si 


M
i 1
M
i 1
i
k 
la media delle log-likelihood delle porzioni utilizzate
per il test
Scelta del numero di cluster (10/12)
{Monte Carlo Cross-Validation}





Ci sono vari approcci per fare cross-validazione, quello
utilizzato è la Monte Carlo Cross-Validation
Con questa metodologia il dataset di test viene ripetutamente
suddiviso in due parti, una per il training l’altra per il testing
Ad ogni iterazione di cross-validazione si provano tutti i
clustering con numero di cluster da 1 ad un valore massimo
fornito dall’utente
b indica la porzione di dataset da utilizzare per il testing
Sperimentalmente si è visto come valori di bpari a 0,5 ed M
compreso tra 20 e 50, siano buoni nella maggior parte dei casi
Riferimenti
[1] Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning:
Data Mining, Inference, and Prediction; Springer Series in Statistics. New York, NY: Springer
Verlag, 2001.
[2] Robert A. Adams, Calcolo Differenziale 2: Funzioni di più variabili; (seconda edizione).
Milano, Italy: Casa Editrice Ambrosiana, 2000.
[3] Padhraic Smyth, Clustering using Monte Carlo Cross-Validation, in E. Simoudis, J. Han, and
U. M. Fayyad, Proceedings of the Second International Conference on Knowledge Discovery
and Data Mining (KDD-96), Menlo Park, CA: AAAI Press, pp 126-133, 1996.
[4] Padhraic Smyth, Model Selection for Probabilistic Clustering using Cross-Validated
Likelihood, Technical Report UCI-ICS 98-09, Department of Information and Computer
Science, University of California, Irvine, CA, 1998.
[5] Thomas M. Cover, and Joy A. Thomas, Elements of Information Theory; Wiley Series in
Telecommunications. New York, NY: John Wiley & Sons, 1991.
[6] Pasquale Erto, Probabilità e Statistica per le scienze e l’ingegneria; collana di istruzione
scientifica, serie di statistica. Milano, Italy, 1999.
[7] Ian H. Witten, and Eibe Frank (2005), Data Mining: Practical machine learning tools and
techniques, (2nd Edition). San Francisco, CA: Morgan Kaufmann, 2005.