Il modello della miscela di processo di Dirichlet

• 23 Giugno 2014
• Vasilis Vryniotis
• . 2 commenti

Questo post sul blog è la quarta parte della serie Clustering con modelli di miscele di processo Dirichlet. In articoli precedenti abbiamo discusso i modelli di miscele di Dirichlet finiti e abbiamo preso il limite del loro modello per infiniti cluster di k che ci ha portato all'introduzione dei processi di Dirichlet. Come abbiamo visto, il nostro obiettivo è costruire un modello di miscela che non ci richieda di specificare il numero di k cluster / componenti dall'inizio. Dopo presentando diverse rappresentazioni dei processi di Dirichlet, ora è il momento di utilizzare effettivamente i DP per costruire un modello Mixture infinito che ci consenta di eseguire il clustering. L'obiettivo di questo articolo è definire i modelli di miscela di processo di Dirichlet e discutere l'uso del processo di ristorazione cinese e del campionamento di Gibbs. Se non hai letto i post precedenti, si consiglia vivamente di farlo poiché l'argomento è un po 'teorico e richiede una buona comprensione della costruzione del modello.

Aggiornamento: Datumbox Machine Learning Framework è ora open-source e gratuito scaricare. Dai un'occhiata al pacchetto com.datumbox.framework.machinelearning.clustering per vedere l'implementazione dei modelli di miscela di processo di Dirichlet in Java.

1. Definizione del modello di miscela di processo di Dirichlet

L'uso di Dirichlet Processes ci permette di avere un modello di miscela con infiniti componenti che si può pensare che prenda il limite del modello finito per k all'infinito. Supponiamo di avere il seguente modello:

Equazione 1: Modello della miscela di processo di Dirichlet

Dove G è definito come ed usato come una breve notazione per che è una funzione delta che richiede 1 if e 0 altrove. Il θ_i sono i parametri del cluster che sono campionati da G. La distribuzione generativa F è configurata dai parametri del cluster θ_i e viene usato per generare x_i osservazioni. Finalmente possiamo definire una distribuzione di densità che è la nostra distribuzione della miscela (miscela infinita numerabile) con proporzioni di miscelazione e miscelazione di componenti .

Figura 1: Modello grafico del modello della miscela di processo di Dirichlet

Sopra possiamo vedere l'equivalente modello grafico del DPMM. La G₀ è la distribuzione di base di DP ed è solitamente selezionata per essere coniugata prima della nostra distribuzione generativa F al fine di semplificare i calcoli e utilizzare le proprietà matematiche interessanti. L'α è l'iperparametro scalare del processo di Dirichlet e influenza il numero di cluster che otterremo. Maggiore è il valore di α, più i cluster; più piccolo è α meno cluster. Dobbiamo notare che il valore di α esprime la forza di credere ns₀. Un valore elevato indica che la maggior parte dei campioni sarà distinta e avrà valori concentrati su G₀. G è una distribuzione casuale nello spazio dei parametri Θ campionato dal DP che assegna le probabilità ai parametri. Il θ_i è un vettore di parametri che viene disegnato dalla distribuzione G e contiene i parametri del cluster, la distribuzione F è parametrizzata da θ_i e x_i è il punto dati generato dalla Generative Distribution F.

È importante notare che θ_i sono elementi dello spazio dei parametri Θ e "configurano" i nostri cluster. Possono anche essere visti come variabili latenti su x_i che ci dice da quale componente / cluster la x_i viene e quali sono i parametri di questo componente. Quindi per ogni x_i che osserviamo, disegniamo un θ_i dalla distribuzione G. Ad ogni sorteggio la distribuzione cambia in base alle selezioni precedenti. Come abbiamo visto nello schema dell'urna Blackwell-MacQueen, la distribuzione G può essere integrata e le nostre selezioni future di θ_i dipende solo da G₀: . Stimare i parametri θi dalla formula precedente non è sempre possibile perché molte implementazioni (come il processo di ristorazione cinese) comportano l'enumerazione attraverso il aumento esponenziale dei componenti k. Pertanto vengono utilizzati metodi computazionali approssimativi come il campionamento di Gibbs. Infine, dovremmo notare che anche se i cluster k sono infiniti, lo è il numero di cluster attivi . Quindi il θ_i ripeterà ed esibirà un effetto di raggruppamento.

2. Utilizzo del processo di ristorazione cinese per definire un modello di miscela infinita

Il modello definito nel segmento precedente è matematicamente solido, tuttavia presenta un grosso svantaggio: per ogni nuova x_i che osserviamo, dobbiamo provare un nuovo θ_i tenendo conto dei valori precedenti di θ. Il problema è che in molti casi il campionamento di questi parametri può essere un'attività difficile e computazionalmente costosa.

Un approccio alternativo consiste nell'utilizzare il processo del ristorante cinese per modellare le variabili latenti z_i delle assegnazioni di cluster. In questo modo invece di usare θ_i per indicare sia i parametri del cluster che le assegnazioni del cluster, usiamo la variabile latente z_i per indicare l'id del cluster e quindi utilizzare questo valore per assegnare i parametri del cluster. Di conseguenza, non è più necessario campionare un θ ogni volta che riceviamo una nuova osservazione, ma invece otteniamo l'assegnazione del cluster campionando z_i da CRP. Con questo schema un nuovo θ viene campionato solo quando è necessario creare un nuovo cluster. Di seguito presentiamo il modello di questo approccio:

Equazione 2: Modello di miscela con CRP

Quanto sopra è un modello generativo che descrive come i dati x_i e i cluster vengono generati. Per eseguire l'analisi del cluster dobbiamo usare le osservazioni x_i e stimare le assegnazioni dei cluster z_i.

3. Inference Model Inference e Gibbs Sampling

Sfortunatamente, poiché i processi di Dirichlet non sono parametrici, noi non è possibile utilizzare l'algoritmo EM per stimare le variabili latenti che memorizzano le assegnazioni dei cluster. Per stimare gli incarichi useremo il Campionamento Gibbs collassato.

Il campionamento Gibbs compresso è un semplice algoritmo Markov Chain Monte Carlo (MCMC). È veloce e ci consente di integrare alcune variabili durante il campionamento di un'altra variabile. Tuttavia, questo algoritmo ci richiede di selezionare una G₀ che è un coniugato precedente alla distribuzione generativa F per essere in grado di risolvere analiticamente le equazioni ed essere in grado di campionare direttamente da .

I passaggi del campionamento di Gibbs compresso che utilizzeremo per stimare le assegnazioni dei cluster sono i seguenti:

• Inizializza la z_i assegnazioni di cluster in modo casuale
• Ripetere fino alla convergenza
• Seleziona ascia a caso_i
  
• Mantieni l'altro z_j risolto per ogni j ≠ i:
• Assegna un nuovo valore su z_i calcolando la "probabilità CRP" che dipende da z_j e x_j di tutti i j ≠ i:

Nel prossimo articolo ci concentreremo su come eseguire l'analisi dei cluster utilizzando i modelli di miscela di processo di Dirichlet. Definiremo due diversi modelli di miscela di processo di Dirichlet che utilizzano il processo di ristorazione cinese e il campionamento di Gibbs compresso al fine di eseguire il clustering su set di dati e documenti continui.