Dirichlet Process Mixing Model

• Juni 23, 2014
• Vasilis Vryniotis
• . 2 kommentarer

Dette blogginnlegget er den fjerde delen av serien om Gruppering med Dirichlet prosessblandingsmodeller. I tidligere artikler diskuterte vi de endelige Dirichlet-blandingsmodellene og vi tok grensen for deres modell for uendelige k-klynger som førte oss til introduksjonen av Dirichlet-prosesser. Som vi så, er målet vårt å bygge en blandingsmodell som ikke krever at vi spesifiserer antall k klynger/komponenter fra begynnelsen. Etter presentere ulike representasjoner av Dirichlet-prosesser, er det nå på tide å faktisk bruke DP-er for å konstruere en uendelig blandingsmodell som gjør oss i stand til å utføre klynging. Målet med denne artikkelen er å definere Dirichlet-prosessblandingsmodellene og diskutere bruken av kinesisk restaurantprosess og Gibbs Sampling. Hvis du ikke har lest de tidligere innleggene, anbefales det på det sterkeste å gjøre det da temaet er litt teoretisk og krever god forståelse for konstruksjonen av modellen.

Oppdatering: Datumbox Machine Learning Framework er nå åpen kildekode og gratis å nedlasting. Sjekk ut pakken com.datumbox.framework.machinelearning.clustering for å se implementeringen av Dirichlet Process Mixture Models i Java.

1. Definisjon av Dirichlet prosessblandingsmodell

Ved å bruke Dirichlet-prosesser kan vi ha en blandingsmodell med uendelige komponenter som kan tenkes å ta grensen for den endelige modellen for k til uendelig. La oss anta at vi har følgende modell:

Ligning 1: Dirichlet prosessblandingsmodell

Hvor G er definert som og brukes som en kort notasjon for som er en delta-funksjon som tar 1 hvis og 0 andre steder. θ_i er klyngeparametrene som er samplet fra G. Den generative fordelingen F er konfigurert av klyngeparametrene θ_i og brukes til å generere x_i observasjoner. Til slutt kan vi definere en tetthetsfordeling som er vår blandingsdistribusjon (telbar uendelig blanding) med blandingsforhold og blande komponenter .

Figur 1: Grafisk modell av Dirichlet prosessblandingsmodell

Ovenfor kan vi se den tilsvarende grafiske modellen til DPMM. G₀ er basisfordelingen til DP og den velges vanligvis til å være konjugert før vår generative distribusjon F for å gjøre beregningene enklere og bruke de tiltalende matematiske egenskapene. α er den skalære hyperparameteren til Dirichlet Process og påvirker antall klynger vi vil få. Jo større verdien av α, jo flere klynger; jo mindre α jo færre klynger. Vi bør merke oss at verdien av α uttrykker troens styrke i G₀. En stor verdi indikerer at de fleste prøvene vil være distinkte og ha verdier konsentrert om G₀. G er en tilfeldig fordeling over Θ parameterrom samplet fra DP som tildeler sannsynligheter til parameterne. θ_i er en parametervektor som er trukket fra G-fordelingen og inneholder parametrene til klyngen, F-fordelingen er parameterisert av θ_i og x_i er datapunktet generert av den generative distribusjonen F.

Det er viktig å merke seg at θ_i er elementer i Θ-parameterrommet og de "konfigurerer" våre klynger. De kan også sees på som latente variabler på x_i som forteller oss fra hvilken komponent/klynge x_i kommer fra og hva er parametrene til denne komponenten. Altså for hver x_i som vi observerer, tegner vi en θ_i fra G-fordelingen. For hver trekning endres fordelingen avhengig av de tidligere valgene. Som vi så i Blackwell-MacQueen urneskjemaet, kan G-distribusjonen integreres og våre fremtidige valg av θ_i bare avhengig av G₀: . Å estimere parametrene θi fra den forrige formelen er ikke alltid mulig fordi mange implementeringer (som for eksempel kinesisk restaurantprosess) involverer oppregning gjennom eksponentielt økende k komponenter. Derfor brukes omtrentlige beregningsmetoder som Gibbs Sampling. Til slutt bør vi merke oss at selv om k-klynger er uendelige, er antallet aktive klynger . Dermed θ_i vil gjenta og vise en klyngeeffekt.

2. Bruke den kinesiske restaurantprosessen for å definere en uendelig blandingsmodell

Modellen definert i forrige segment er matematisk solid, men den har likevel en stor ulempe: for hver ny x_i som vi observerer, må vi prøve en ny θ_i tar i betraktning de tidligere verdiene av θ. Problemet er at i mange tilfeller kan prøvetaking av disse parameterne være en vanskelig og beregningsmessig kostbar oppgave.

En alternativ tilnærming er å bruke den kinesiske restaurantprosessen for å modellere de latente variablene z_i av klyngeoppdrag. På denne måten i stedet for å bruke θ_i for å betegne både klyngeparametrene og klyngetilordningene bruker vi den latente variabelen z_i for å indikere klynge-ID, og ​​bruk deretter denne verdien til å tilordne klyngeparameterne. Som et resultat trenger vi ikke lenger å sample en θ hver gang vi får en ny observasjon, men i stedet får vi klyngetilordningen ved å prøve z_i fra CRP. Med dette skjemaet blir en ny θ samplet bare når vi trenger å opprette en ny klynge. Nedenfor presenterer vi modellen for denne tilnærmingen:

Ligning 2: Blandingsmodell med CRP

Ovenstående er en generativ modell som beskriver hvordan dataene x_i og klyngene genereres. For å utføre klyngeanalysen må vi bruke observasjonene x_i og estimere klyngetilordningene z_i.

3. Blandingsmodellslutning og Gibbs-prøvetaking

Dessverre siden Dirichlet-prosesser er ikke-parametriske, har vi kan ikke bruke EM-algoritmen å estimere de latente variablene som lagrer klyngetilordningene. For å estimere oppdragene vil vi bruke Kollapset Gibbs Sampling.

The Collapsed Gibbs Sampling er en enkel Markov Chain Monte Carlo (MCMC) algoritme. Det er raskt og gjør det mulig for oss å integrere ut noen variabler mens vi prøver en annen variabel. Ikke desto mindre krever disse algoritmene at vi velger en G₀ som er et konjugat forut for F generativ fordeling for å kunne løse analytisk likningene og kunne prøve direkte fra .

Trinnene i Collapsed Gibbs Sampling som vi vil bruke for å estimere klyngetilordningene er følgende:

• Initialiser z_i klyngeoppdrag tilfeldig
• Gjenta til konvergens
• Velg tilfeldig en x_i
  
• Behold den andre z_j fast for hver j≠i:
• Tilordne en ny verdi på z_i ved å beregne "CRP-sannsynligheten" som avhenger av z_j og x_j av alle j≠i:

I den neste artikkelen vil vi fokusere på hvordan du utfører klyngeanalyse ved å bruke Dirichlet Process Mixture-modeller. Vi vil definere to forskjellige Dirichlet-prosessblandingsmodeller som bruker den kinesiske restaurantprosessen og den kollapsede Gibbs-prøvetakingen for å utføre klynging på kontinuerlige datasett og dokumenter.