ML - 34 - Clustering III

Se avessimo a disposizione il dataset completo \((\mathbf{X}, \mathbf{Z})\), sarebbe possibile effettuare una stima di massima verosimiglianza per ottenere i valori dei parametri \(\theta\) e \(\pi\). In particolare,

• Per i coefficienti di mistura \(\pi_k\) abbiamo

  \[\pi_k = \frac{n_k}{n}\]

  dove \(n_k\) è il numero di elementi in cui l'associata variabile \(z\) è proprio \(k\), ovvero gli elementi generati a partire dalla \(k\) esima distribuzione della mistura.

• Per i parametri dei componenti \(\theta_k = (\mu_k, \Sigma_k)\), possiamo utilizzare le solite stime per le gaussiane, ovvero

  \[\begin{split} \mu_k &= \frac{1}{n_k} \sum\limits_{x \in C_k} x \\ \Sigma_k &= \frac{1}{n_k} \sum\limits_{x \in C_k} (x - \mu_k)(x - \mu_k)^T \end{split}\]

In particolare quindi conoscendo \(\mathbf{Z}\) siamo in grado di separare i valori osservati in sottoinsiemi rappresentati i vari clusters, e quindi a partire da ciascun cluster saremmo in grado di effettuare le solite stime per media e matrice di covarianza.

I risultati mostrati prima derivano dalla massimizzazione rispetto a \(\pi_k, \mu_k, \Sigma_k\), per \(k=1,\ldots,K\) della log-likelihood ottenuta da

\[\begin{split} l(\Sigma, \mu, \pi | \mathbf{X}, \mathbf{Z}) &= \log p(\mathbf{X}, \mathbf{Z} | \Sigma, \mu, \pi) \\ &= \log \prod\limits_{i = 1}^n \prod\limits_{k = 1}^K \pi_k^{\zeta_{i,k}} \mathcal{N}(x_i | \mu_k, \Sigma_k)^{\zeta_{i, k}} \\ &= \sum\limits_{i = 1}^n \sum\limits_{k = 1}^K \zeta_{i, k} \Big(\log \pi_k + \log \mathcal{N}(x_i | \mu_k, \Sigma_k \Big) \\ \end{split}\]

dove \(\zeta_{i, k}\) è la \(k\) esima componente della codifica 1-to-K di \(z_i\), ovvero \(\zeta_{i, k} = 1\) se e solo se \(z_i = k\) e \(0\) altrimenti. Detto in altre parole, abbiamo che \(\zeta_{i, k} = 1\) se e solo se l' \(i\) esimo elemento osservato è stato generato a partire dalla \(k\) esima distribuzione della mistura.

Il problema però è che noi l'insieme \(\mathbf{Z}\) non lo conosciamo, e quindi la log-likelihood del dataset completo non può essere definita, in quanto gli insiemi \(C_k\) non sono noti.

L'idea quindi è quella di lasciare stare la log-likelihood dove ciascun \(z_i\) è specificato, ma di concentrarsi invece sul valor medio della log-likelihood rispetto alla distribuzione \(p(\mathbf{Z}|\mathbf{X})\). In pratica questo cambiamento consiste nel sostituire nella formula precedente al valore \(\zeta_{i, k}\) il valore di probabilità \(p(z_i = k | x_i)\). Otteniamo quindi,

\[\begin{split} \mathbb{E}_{p(\mathbf{Z}|\mathbf{X})}\Big[l(\Sigma, \mu, \pi | \mathbf{X}, \mathbf{Z}) \Big] &= \sum\limits_{i = 1}^n \sum\limits_{k = 1}^K p(z_i = k | x_i) \cdot \Big(\log \pi_k + \log \mathcal{N}(x_i | \mu_k, \Sigma_k \Big) \\ &= \sum\limits_{i = 1}^n \sum\limits_{k = 1}^K \gamma_k(x_i) \cdot \Big(\log \pi_k + \log \mathcal{N}(x_i | \mu_k, \Sigma_k \Big) \\ \end{split}\]

in quanto avevamo già osservato che \(p(z_i = k | x_i) = \gamma_k(x_i)\). Come è possibile vedere poi, questa espressione può essere calcolata nel momento in cui conosco \(p(\mathbf{Z}|\mathbf{X})\), ovvero l'insieme dei valori \(\gamma_k(x_i)\).

Descriviamo quindi l'algoritmo iterativo in modo esplicito:

• Iniziamo definendo una stima iniziale per \(mu_j, \Sigma_j\) e \(\pi_j\) per \(j=1,\ldots,K\).

• Si iterano i seguenti passi fino a quando un determinato test di convergenza è verificato:

  • Si calcola il valore \(\gamma_j(x_i)\) per \(j=1,\ldots,K\) con la seguente formula

    \[\gamma_j(x_i) = \frac{\pi_j \cdot \mathcal{N}(x_i | \mu_j, \Sigma_j)}{\sum_{k=1}^K \pi_k \mathcal{N}(x_i | \mu_j, \Sigma_j)}\]

  • Si aggiornano i valori dei parametri

    \[\begin{split} \pi_j &= \frac{\sum\limits_{i = 1}^n \gamma_j(x_i)}{n} \\ \\ \mu_j &= \frac{1}{n_j} \sum\limits_{i = 1}^n \gamma_j(x_i) \cdot x_i \\ \\ \Sigma_j &= \frac{1}{n_j} \sum\limits_{i = 1}^n \gamma_j(x_i)(x_i - \mu_j)(x_i - \mu_j)^T \\ \end{split}\]

Notiamo che il test di convergenza menzionato potrebbe far riferimento, ad esempio, all'incremento della log-likelihood durante l'ultima iterazione.

Questo algoritmo è l'applicazione di uno schema più generale che prende il nome di Expectation-Maximization. Questo schema è generalizzabile a tutti i modelli in cui compaiono delle variabili latenti.