Dirichlet-procesblandingsmodellen

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

Dette blogindlæg er fjerde del af serien om Klyngning med Dirichlet-procesblandingsmodeller. I tidligere artikler diskuterede vi de endelige Dirichlet-blandingsmodeller, og vi tog grænsen for deres model for uendelige k-klynger, hvilket førte os til introduktionen af ​​Dirichlet-processer. Som vi så, er vores mål at bygge en blandingsmodel, som ikke kræver, at vi specificerer antallet af k klynger/komponenter fra begyndelsen. Efter præsentation af forskellige repræsentationer af Dirichlet-processer, er det nu tid til rent faktisk at bruge DP'er til at konstruere en uendelig blandingsmodel, der gør os i stand til at udføre klyngedannelse. Målet med denne artikel er at definere Dirichlet-procesblandingsmodellerne og diskutere brugen af ​​kinesisk restaurantproces og Gibbs-prøveudtagning. Hvis du ikke har læst de tidligere indlæg, kan det varmt anbefales at gøre det, da emnet er lidt teoretisk og kræver god forståelse for opbygningen af ​​modellen.

Opdatering: Datumbox Machine Learning Framework er nu open source og gratis til downloade. Tjek pakken com.datumbox.framework.machinelearning.clustering for at se implementeringen af ​​Dirichlet Process Mixture Models i Java.

1. Definition af Dirichlet-procesblandingsmodel

Ved at bruge Dirichlet-processer kan vi have en blandingsmodel med uendelige komponenter, som kan tænkes at tage grænsen for den endelige model for k til uendelig. Lad os antage, at vi har følgende model:

Ligning 1: Dirichlet-procesblandingsmodel

Hvor G er defineret som , bruges som en kort notation for som er en deltafunktion, der tager 1 if og 0 andre steder. θ_i er klyngeparametrene, som er samplet fra G. Den generative fordeling F er konfigureret af klyngeparametrene θ_i og bruges til at generere x_i observationer. Endelig kan vi definere en tæthedsfordeling som er vores blandingsfordeling (tællelig uendelig blanding) med blandingsforhold og blanding af komponenter .

Figur 1: Grafisk model af Dirichlet-procesblandingsmodel

Ovenfor kan vi se den tilsvarende grafiske model af DPMM. G₀ er basisfordelingen af ​​DP, og den vælges normalt til at være konjugeret før vores generative fordeling F for at gøre beregningerne nemmere og gøre brug af de tiltalende matematiske egenskaber. α er den skalære hyperparameter af Dirichlet Process og påvirker antallet af klynger, vi får. Jo større værdien af ​​α er, jo flere klynger; jo mindre α jo færre klynger. Vi skal bemærke, at værdien af ​​α udtrykker troens styrke i G₀. En stor værdi indikerer, at de fleste af prøverne vil være forskellige og have værdier koncentreret om G₀. G'et er en tilfældig fordeling over Θ parameterrum samplet fra DP'en, som tildeler sandsynligheder til parametrene. θ_i er en parametervektor, som er tegnet fra G-fordelingen og indeholder klyngens parametre, F-fordelingen er parametriseret med θ_i og x_i er datapunktet genereret af den generative distribution F.

Det er vigtigt at bemærke, at θ_i er elementer i Θ-parameterrummet, og de "konfigurerer" vores klynger. De kan også ses som latente variable på x_i som fortæller os fra hvilken komponent/klynge x'et_i kommer fra, og hvad er parametrene for denne komponent. Altså for hvert x_i at vi observerer, tegner vi en θ_i fra G-fordelingen. For hver trækning ændres fordelingen afhængigt af de tidligere valg. Som vi så i Blackwell-MacQueen urne-skemaet, kan G-fordelingen integreres og vores fremtidige valg af θ_i afhænger kun af G₀: . Det er ikke altid muligt at estimere parametrene θi fra den foregående formel, fordi mange implementeringer (såsom kinesisk restaurantproces) involverer opregning gennem eksponentielt stigende k komponenter. Således anvendes omtrentlige beregningsmetoder, såsom Gibbs Sampling. Til sidst skal vi bemærke, at selvom k-klyngerne er uendelige, er antallet af aktive klynger det . Således er θ_i vil gentage og udvise en klyngeeffekt.

2. Brug af den kinesiske restaurantproces til at definere en uendelig blandingsmodel

Modellen defineret i det forrige segment er matematisk solid, ikke desto mindre har den en stor ulempe: for hver ny x_i at vi observerer, skal vi prøve en ny θ_i under hensyntagen til de tidligere værdier af θ. Problemet er, at sampling af disse parametre i mange tilfælde kan være en vanskelig og beregningsmæssigt dyr opgave.

En alternativ tilgang er at bruge den kinesiske restaurantproces til at modellere de latente variable z_i af klyngeopgaver. På denne måde i stedet for at bruge θ_i for at betegne både klyngeparametrene og klyngetildelingerne bruger vi den latente variabel z_i for at angive klynge-id'et, og brug derefter denne værdi til at tildele klyngeparametrene. Som et resultat behøver vi ikke længere at sample en θ hver gang vi får en ny observation, men i stedet får vi klyngetildelingen ved at prøve z_i fra CRP. Med dette skema udtages en ny θ kun, når vi skal oprette en ny klynge. Nedenfor præsenterer vi modellen for denne tilgang:

Ligning 2: Blandingsmodel med CRP

Ovenstående er en generativ model, der beskriver, hvordan dataene x_i og klyngerne genereres. For at udføre klyngeanalysen skal vi bruge observationerne x_i og estimer klyngetildelingerne z_i.

3. Blandingsmodelinferens og Gibbs-prøveudtagning

Da Dirichlet-processer er ikke-parametriske, har vi desværre kan ikke bruge EM-algoritmen at estimere de latente variabler, som lagrer klyngetildelingerne. For at estimere opgaverne vil vi bruge Kollapset Gibbs Sampling.

The Collapsed Gibbs Sampling er en simpel Markov Chain Monte Carlo (MCMC) algoritme. Det er hurtigt og gør det muligt for os at integrere nogle variabler, mens vi prøver en anden variabel. Ikke desto mindre kræver disse algoritmer, at vi vælger en G₀ som er et konjugat forud for F generativ fordeling for analytisk at kunne løse ligningerne og kunne sample direkte fra .

Trinene i Collapsed Gibbs Sampling, som vi vil bruge til at estimere klyngetildelingerne, er følgende:

• Initialiser z'et_i klyngetildelinger tilfældigt
• Gentag indtil konvergens
• Vælg tilfældigt økse_i
  
• Behold det andet z_j fast for hver j≠i:
• Tildel en ny værdi på z_i ved at beregne "CRP-sandsynligheden", der afhænger af z_j og x_j af alle j≠i:

I den næste artikel vil vi fokusere på, hvordan man udfører klyngeanalyse ved at bruge Dirichlet Process Mixture-modeller. Vi vil definere to forskellige Dirichlet-procesblandingsmodeller, som bruger den kinesiske restaurantproces og den kollapsede Gibbs-sampling for at udføre klyngedannelse på kontinuerlige datasæt og dokumenter.