Het Dirichlet-procesmengselmodel

• 23 June 2014
• Vasilis Vryniotis
• . 2 opmerkingen

Deze blogpost is het vierde deel van de serie over Clustering met Dirichlet-procesmengselmodellen. In eerdere artikelen bespraken we de eindige Dirichlet-mengmodellen en namen we de limiet van hun model voor oneindige k-clusters, wat ons leidde tot de introductie van Dirichlet-processen. Zoals we zagen, is ons doel om een ​​mengmodel te bouwen waarbij we niet vanaf het begin het aantal k clusters / componenten hoeven te specificeren. Na met verschillende weergaven van Dirichlet-processen, is het nu tijd om DP's daadwerkelijk te gebruiken om een ​​oneindig Mengselmodel te construeren waarmee we clustering kunnen uitvoeren. Het doel van dit artikel is om de Dirichlet Process Mixture Models te definiëren en het gebruik van Chinese Restaurant Process en Gibbs Sampling te bespreken. Als je de vorige berichten niet hebt gelezen, wordt het ten zeerste aanbevolen om dit te doen, omdat het onderwerp een beetje theoretisch is en een goed begrip van de constructie van het model vereist.

Update: het Datumbox Machine Learning Framework is nu open-source en gratis voor Download. Bekijk het pakket com.datumbox.framework.machinelearning.clustering om de implementatie van Dirichlet Process Mixture Models in Java te zien.

1. Definitie van Dirichlet-procesmengselmodel

Door Dirichlet-processen te gebruiken, kunnen we een mengmodel hebben met oneindige componenten waarvan gedacht kan worden dat ze de limiet van het eindige model voor k tot oneindig nemen. Laten we aannemen dat we het volgende model hebben:

Vergelijking 1: Dirichlet-procesmengselmodel

Waar G wordt gedefinieerd als en gebruikt als een korte notatie voor wat een deltafunctie is die 1 als nodig heeft en 0 elders. De θ_i zijn de clusterparameters die worden bemonsterd uit G. De generatieve verdeling F wordt geconfigureerd door clusterparameters θ_i en wordt gebruikt om x te genereren_i observaties. Ten slotte kunnen we een dichtheidsverdeling definiëren dat is onze mengselverdeling (telbaar oneindig mengsel) met mengverhoudingen en mengcomponenten .

Figuur 1: Grafisch model van Dirichlet Process Mixture Model

Hierboven zien we het equivalente grafische model van de DPMM. De G₀ is de basisverdeling van DP en het wordt meestal geselecteerd als conjugaat vóór onze generatieve verdeling F om de berekeningen gemakkelijker te maken en gebruik te maken van de aantrekkelijke wiskundige eigenschappen. De α is de scalaire hyperparameter van het Dirichlet-proces en beïnvloedt het aantal clusters dat we zullen krijgen. Hoe groter de waarde van α, hoe meer clusters; hoe kleiner de α, hoe minder clusters. We moeten opmerken dat de waarde van α uitdrukt de kracht van geloven in G₀. Een grote waarde geeft aan dat de meeste monsters afzonderlijk zullen zijn en waarden hebben die zijn geconcentreerd op G₀. De G is een willekeurige verdeling over Θ parameterruimte bemonsterd uit de DP die kansen aan de parameters toewijst. De θ_i is een parametervector die is afgeleid van de G-distributie en de parameters van het cluster bevat, F-distributie wordt geparametriseerd door θ_i en x_i is het datapunt gegenereerd door de Generative Distribution F.

Het is belangrijk op te merken dat de θ_i zijn elementen van de parameterruimte space en ze "configureren" onze clusters. Ze kunnen ook worden gezien als latente variabelen op x_i die ons vertellen van welk onderdeel / cluster de x_i komt vandaan en wat zijn de parameters van dit onderdeel. Dus voor elke x_i die we waarnemen, tekenen we een θ_i van de G-verdeling. Bij elke trekking verandert de verdeling afhankelijk van de vorige selecties. Zoals we zagen in het Blackwell-MacQueen urnschema, kan de G-verdeling worden geïntegreerd en onze toekomstige selecties van θ_i alleen afhankelijk van G₀: . Het schatten van de parameters θi uit de vorige formule is niet altijd haalbaar omdat veel implementaties (zoals het Chinese restaurantproces) de opsomming via de exponentieel toenemende k componenten. Daarom worden benaderde rekenmethoden gebruikt, zoals Gibbs Sampling. Ten slotte moeten we opmerken dat hoewel de k-clusters oneindig zijn, het aantal actieve clusters dat wel is . Dus de θ_i zal zich herhalen en een clusterend effect vertonen.

2. Het Chinese restaurantproces gebruiken om een ​​oneindig mengselmodel te definiëren

Het in het vorige segment gedefinieerde model is wiskundig solide, maar heeft toch een groot nadeel: voor elke nieuwe x_i die we waarnemen, moeten we een nieuwe θ bemonsteren_i rekening houdend met de eerdere waarden van θ. Het probleem is dat het bemonsteren van deze parameters in veel gevallen een moeilijke en computationeel dure taak kan zijn.

Een alternatieve benadering is om het Chinese restaurantproces te gebruiken om de latente variabelen z te modelleren_i clusteropdrachten. Op deze manier in plaats van θ te gebruiken_i om zowel de clusterparameters als de clustertoewijzingen aan te geven, gebruiken we de latente variabele z_i om de cluster-id aan te geven en gebruik vervolgens deze waarde om de clusterparameters toe te wijzen. Als gevolg hiervan hoeven we niet langer een sample te bemonsteren elke keer dat we een nieuwe waarneming krijgen, maar in plaats daarvan krijgen we de clustertoewijzing door bemonstering z_i van CRP. Met dit schema wordt een nieuwe θ alleen bemonsterd als we een nieuw cluster moeten maken. Hieronder presenteren we het model van deze aanpak:

Vergelijking 2: mengselmodel met CRP

Het bovenstaande is een generatief model dat beschrijft hoe de gegevens x_i en de clusters worden gegenereerd. Om de clusteranalyse uit te voeren, moeten we de waarnemingen x gebruiken_i en schat de clustertoewijzingen z_i.

3. Mengselmodel Inferentie en Gibbs-bemonstering

Helaas, aangezien Dirichlet-processen niet-parametrisch zijn, hebben wij kan geen EM-algoritme gebruiken om de latente variabelen te schatten die de clustertoewijzingen opslaan. Om de opdrachten te kunnen inschatten gebruiken we de Ingestorte Gibbs-bemonstering.

De samengevouwen Gibbs-bemonstering is een eenvoudig Markov Chain Monte Carlo (MCMC) -algoritme. Het is snel en stelt ons in staat om enkele variabelen te integreren terwijl we een andere variabele bemonsteren. Desalniettemin vereisen deze algoritmen dat we een G selecteren₀ wat een conjugaat is voorafgaand aan F generatieve distributie om analytisch de vergelijkingen op te kunnen lossen en rechtstreeks te kunnen bemonsteren van .

De stappen van de Collapsed Gibbs Sampling die we zullen gebruiken om de clustertoewijzingen te schatten, zijn de volgende:

• Initialiseer de z_i clusteropdrachten willekeurig
• Herhaal tot convergentie
• Selecteer willekeurig bijl_i
  
• Bewaar de andere z_j opgelost voor elke j ≠ i:
• Wijs een nieuwe waarde toe aan z_i door de "CRP-kans" te berekenen die afhangt van z_j en x_j van alle j ≠ i:

In het volgende artikel zullen we ons concentreren op het uitvoeren van clusteranalyse met behulp van Dirichlet Process Mixture-modellen. We zullen twee verschillende Dirichlet Process Mixture-modellen definiëren die het Chinese restaurantproces en de Collapsed Gibbs Sampling gebruiken om clustering uit te voeren op continue datasets en documenten.