ML - 33 - Clustering II

Consideriamo la seguente immagine, in cui la curva blu è ottenuta come una mistura additiva delle altre curve.

È possibile dimostrare che quasi tutte le distribuzioni continue possono essere ottenute tramite una combinazione lineare di un numero abbastanza grand di gaussiane.

Andiamo quindi a considerare le derivate rispetto ai vari pesi \(\pi\)

\[\frac{\partial \mathcal{L}(\theta, \pi | \mathbf{X})}{\partial \pi_j} = \frac{\partial l(\theta, \pi | \mathbf{X})}{\partial \pi_j} - \lambda = 0\]

continuando i calcoli

\[\begin{split} \lambda = \frac{\partial l(\theta, \pi | \mathbf{X})}{\partial \pi_j} &= \frac{\partial}{\partial \pi_j} \Bigg[\sum\limits_{i = 1}^n \log{\Bigg(\sum\limits_{k = 1}^K \pi_k q(x_i|\theta_k) \Bigg)} \Bigg] \\ &= \sum\limits_{i = 1}^n \frac{\partial}{\partial \pi_j} \Bigg[ \log{\Bigg(\sum\limits_{k = 1}^K \pi_k q(x_i | \theta_k) \Bigg)}\Bigg] \\ &= \sum\limits_{i = 1}^n \frac{1}{\sum_{k = 1}^K \pi_k q(x_i | \theta_k) } \cdot \frac{\partial}{\partial \pi_j} \Bigg(\sum\limits_{k = 1}^K \pi_k q(x_i | \theta_k)\Bigg) \\ &= \sum\limits_{i = 1}^n \frac{1}{\sum_{k = 1}^K \pi_k q(x_i | \theta_k) } \cdot \sum\limits_{k = 1}^K \frac{\partial}{\partial \pi_j} \Bigg( \pi_k q(x_i | \theta_k)\Bigg) \\ &= \sum\limits_{i = 1}^N \frac{q(x_i | \theta_j)}{\sum_{k = 1}^K \pi_k q(x_i | \theta_k)} \\ &= \sum\limits_{i = 1}^n \frac{\gamma_j(x_i)}{\pi_j} \\ &= \frac{1}{\pi_j} \sum\limits_{i = 1}^n \gamma_j(x_i) \\ \end{split}\]

dove

\[\gamma_k(x) = \frac{\pi_k \cdot q(x | \theta_k)}{\sum_{j = 1}^K \pi_j \cdot q(x | \theta_j)}\]

Considerando invece la derivata rispetto a \(\lambda\) e ponendola uguale a \(0\) otteniamo

\[\frac{\partial \mathcal{L}(\theta, \pi | \mathbf{X}}{\partial \lambda} = \frac{\partial}{\partial \lambda}\Bigg(l(\theta, \pi | \mathbf{X}) + \lambda \Big(1 - \sum\limits_{i = 1}^K \pi_i \Big) \Bigg) = 0\]

il che equivale a dire

\[\sum\limits_{i = 1}^K \pi_i = 1\]

Componendo i due ultimi risultati otteniamo

\[\sum\limits_{j = 1}^K \pi_j = \frac{1}{\lambda} \sum\limits_{j = 1}^K \sum\limits_{i = 1}^n \gamma_j(x_i) = 1\]

il che implica

\[\begin{split} \lambda = \sum\limits_{j = 1}^K \sum\limits_{i = 1}^n \gamma_j(x_i) &= \sum\limits_{i = 1}^n \sum\limits_{j = 1}^K \gamma_j(x_i) \\ &= \sum\limits_{i = 1}^n \sum\limits_{j = 1}^K \frac{\pi_j q(x_i | \theta_j)}{\sum_{k = 1}^K \pi_k q(x_i | \theta_k)} \\ &= \sum\limits_{i = 1}^n 1 \\ &= n \end{split}\]

e quindi

\[\pi_k =\frac{1}{n} \sum\limits_{i = 1}^n \gamma_k(x_i)\]

Notiamo quindi che per ogni elemento della mistura \(j=1,\ldots,k\) considero sia il peso della combinazione lineare \(\pi_j\) che la funzione \(\gamma_j(x_i)\).

Infine, per quanto riguarda le derivata rispetto ai parametri \(\theta\), otteniamo

\[\begin{split} \frac{\partial \mathcal{L}(\theta, \pi | \mathbf{X})}{\partial \theta_j} &= \frac{\partial}{\partial \theta_j} \Bigg[ \sum\limits_{i = 1}^n \log{\Bigg(\sum\limits_{k = 1}^K \pi_k \cdot q(x_i | \theta_k) \Bigg)} \Bigg] \\ &= \sum\limits_{i = 1}^n \frac{\partial}{\partial \theta_j} \Bigg[\log{\Bigg( \sum\limits_{k = 1}^K \pi_k \cdot q(x_i | \theta_k) \Bigg)} \Bigg] \\ &\;\; \vdots \\ &= \sum\limits_{i = 1}^n \gamma_j(x_i) \cdot \frac{\partial \log{q(x_i | \theta_j)}}{\partial \theta_j} = 0 \\ \end{split}\]

Notiamo a questo punto che andare a massimizzare la log-likelihood in modo analitico (in forma chiusa) non è possibile, in quanto

• \(\pi\) e \(\theta\) possono essere derivati da \(\gamma_k(x_i)\)

• \(\gamma_k(x_i)\) può essere derivata da \(\pi\) e \(\theta\).

Per risolvere questo problema si procedere quindi in modo iterativo nel seguente modo:

• Si fissa una stima per \(\pi\) e \(\theta\), ovvero si ipotizza come è fatta la mistura.

• A partire da queste si stimano tutte le funzioni \(\gamma_k(x_i)\)

• A partire da questa si derivano delle nuove stime per \(\pi\) e \(\theta\)

e via dicendo, iterando questo procedimento.

Il seguente esempio mostra la generazione di un dataset utilizzando una mistura di \(3\) gaussiane.

Notiamo che nella figura più a sinistra abbiamo acesso sia a \(z_1, \ldots z_n\) che \(x_1, \ldots, x_n\), mentre la figura al centro corrisponde ad avere accesso solamente ai valori \(x_i\).

La combinazione tra valori osservabili e valori latenti prende il nome di dataset completo, ed è un'astrazione, in quanto i valori \(z_1, \ldots, z_n\) non sono valori fisicamente reali, ma rappresentano un modello per generare i dati \(x_1, \ldots, x_n\).

Infine, la figura a destra rappresenta un processo di inferenza in cui a partire dai soli dati osservati \(x_i\), si stima la probabilità che quel punto derivasse da ognuna delle \(3\) gaussiane utilizzate nella mistura.

Riflettendo sull'ultimo esempio è possibile osservare che con questo approccio a partire dal nostro dataset abbiamo ottenuto una descrizione probabilistica del clusterting.

In particolare abbiamo,

• Una descrizione probabilistica associata ad ogni distribuzione facente parte della mistura. Questa descrizione è paragonabile al prototipo che abbiamo introdotto nella discussione del clusterting deterministico.

• Per ogni elemento poi, abbiamo un valore di probabilità per ogni distribuzione, ovvero per ogni cluster, che rappresenta proprio la probabilità che quell'elemento appartiene a quel cluster. Così facendo abbiamo ottenuto una descrizione probabilistica di un clustering.

Analizziamo adesso più precisamente questa situazione di distribuzione con variabili latenti. Per come è stato definito il nostro modello abbiamo che

\[p(x | z = k, \theta, \pi) = p(x | z = k, \theta) = q(x | \theta_k)\]

se poi calcoliamo la marginalizzazione rispetto a \(z\) otteniamo

\[\begin{split} p(x | \theta, \pi) &= \sum\limits_{k = 1}^K p(x, z=k | \theta, \pi) \\ &= \sum\limits_{k = 1}^K p(x | z = k, \pi, \theta) \cdot p(z = k | \theta, \pi) \\ &= \sum\limits_{k = 1}^K (p | z = k, \theta) \cdot p(z = k | \pi) \\ &= \sum\limits_{k = 1}^K q(x | \theta_k) \cdot p(z = k | \pi) \\ \end{split}\]

Dato poi che per definizione abbiamo che

\[p(x | \theta, \pi) = \sum\limits_{k = 1}^K \pi_k \cdot q(x_i | \theta_k)\]

otteniamo

\[\pi_k = p(z = k | \pi)\]

Possiamo quindi interpretare il valore \(\pi_k\) come il valore di probabilità che il prossimo punto viene generato utilizzando la \(k\) esima distribuzione della mistura.

Collegata a questa interpretazione possiamo poi interpretare le funzioni \(\gamma_k(x)\) come segue

\[\begin{split} \gamma_k(x) &= \frac{\pi_k \cdot q(x | \theta_k) }{\sum_{j = 1}^K \pi_j q(x | \theta_j)} \\ &= \frac{p(z = k) \cdot p(x | z = k)}{\sum_{j = 1}^K p(z = j) p(x | z = j)} \\ &= p(z = k | x) \\ \end{split}\]

quindi \(\gamma_k(x)\) è la probabilità a posteriori che l'elemento considerato è stato generato con la \(k\) esima distribuzione. Dunque mentre \(\pi_k\) è la probabilità a priori, \(\gamma_k(x)\) è quella a posteriori. Il valore \(\gamma_k(x)\) è detto responsibility.