Dirichlet bearbetar den kinesiska restaurangprocessen och andra framställningar

• Maj 20, 2014
• Vasilis Vryniotis
• . Inga kommentarer

Den här artikeln är den tredje delen av serien Clustering with Dirichlet Process Mixture Models. Förra gången definierade vi Finite Mixture Model baserat på Dirichlet Distribution och vi ställde frågor om hur vi kan göra denna modell oändlig. Vi diskuterade kort tanken att ta gränsen för modellen när k-antalet kluster tenderar att vara oändligt, men som vi betonade är existensen av ett sådant objekt inte trivialt (med andra ord, hur tar vi egentligen gränsen för en modell ”?). Som en påminnelse är anledningen till att vi vill göra k oändlig för att vi på detta sätt kommer att ha en icke-parametrisk modell som inte kräver att vi fördefinierar det totala antalet kluster inom datan.

Uppdatering: Datumbox Machine Learning Framework är nu öppen källkod och gratis att ladda ner. Kolla in paketet com.datumbox.framework.machinelearning.clustering för att se implementeringen av Dirichlet Process Mixture Models i Java.

Även om vårt mål är att bygga en modell som kan utföra kluster på datauppsättningar, innan vi måste diskutera om Dirichlet-processer. Vi kommer att tillhandahålla både de strikta matematiska definitionerna och de mer intuitiva förklaringarna till DP och vi kommer att diskutera sätt att konstruera processen. Dessa konstruktioner / framställningar kan ses som ett sätt att hitta förekomster av Dirichlet-processen i det "verkliga livet".

Trots att jag försökte anpassa min forskningsrapport på ett sådant sätt att dessa blogginlägg är lättare att följa, är det fortfarande viktigt att definiera nödvändiga matematiska verktyg och distributioner innan vi hoppar in i modellerna. Dirichlet-processmodeller är ett ämne för aktiv forskning, men de kräver en god förståelse för statistik och stokastiska processer innan de används. Ett annat problem är att som vi kommer att se i den här artikeln kan Dirichlet-processer representeras / konstrueras på många sätt. Som ett resultat använder flera akademiska artiklar helt olika notationer / konventioner och undersöker problemet ur olika synvinklar. I det här inlägget försöker jag förklara dem så enkelt som möjligt och använda samma notation. Förhoppningsvis kommer det att bli tydligare med de två kommande artiklarna som fokuserar på definitionen av Dirichlet Process Mixture Models och hur man faktiskt använder dem för att utföra klusteranalys.

1. Definition av Dirichlet-processen

En Dirichlet-process över ett Θ-utrymme är en stokastisk process. Det är en sannolikhetsfördelning över "sannolikhetsfördelningar över Θ utrymme" och a dra från det är en diskret fördelning. Mer formellt är en Dirichlet-distribution en fördelning över sannolikhetsåtgärder. A sannolikhetsmått är en funktion av delmängder av utrymme Θ till [0,1]. G är ett DP-fördelat slumpmässigt sannolikhetsmått, betecknat som , om för någon partition (A₁, ... A_n) av rymden Θ vi har det .

Figur 1: Marginaler på slutliga partitioner är Dirichlet-distribuerade.

DP har två parametrar: Den första är basfördelningen G₀ som fungerar som ett medelvärde . Den andra är styrka-parametern α som är strikt positiv och fungerar som invers varians . Det bestämmer omfattningen av repetitionen av värdena för utmatningsfördelningen. Ju högre värde a är, desto mindre blir repetitionen; ju mindre värdet desto högre upprepning av värdena för utdelningsfördelningen. Slutligen är Θ-utrymmet det parameterutrymme som vi definierar DP på. Dessutom är utrymmet Θ också definitionsutrymmet för G₀ som är samma som den av G.

En enklare och mer intuitivt sätt för att förklara en Dirichlet-process är följande. Antag att vi har ett utrymme Θ som kan delas upp på något begränsat sätt (A₁, ..., A_n) och en sannolikhetsfördelning G som tilldelar dem sannolikheter. G är en specifik sannolikhetsfördelning över Θ men det finns många andra. Dirichlet-processen på Θ modellerar exakt detta; det är en fördelning över alla möjliga sannolikhetsfördelningar på rymden Θ. Dirichlet-processen är parametrerad med G₀ basfunktion och α-koncentrationsparametern. Vi kan säga att G fördelas enligt DP med parametrarna α och G₀ om den gemensamma fördelningen av sannolikheterna som G tilldelar partitionerna av Θ följer Dirichlet-fördelningen. Alternativt kan vi säga att sannolikheterna som G tilldelar någon begränsad partition av Θ följer Dirichlet-distribution.

Figur 2: Grafisk modell av Dirichlet-processen

Slutligen ovan kan vi se grafisk modell av en DP. Vi bör notera att α är en skalär hyperparameter, G₀ är basfördelningen för DP, G en slumpmässig fördelning över Θ parameterutrymme samplat från DP som tilldelar sannolikheter till parametrarna och θ_i är en parametervektor som dras från G-fördelningen och det är ett element i Θ-rymden.

2. Posterior Dirichlet-processer

Posterior Dirichlet Processes diskuterades av Ferguson. Vi börjar med att rita ett slumpmässigt sannolikhetsmått G från en Dirichlet-process, . Eftersom G är en sannolikhetsfördelning över Θ kan vi också sampla från denna fördelning och rita oberoende identiskt fördelade prover θ₁,…, Θ_n ~ G. Eftersom drag från en Dirichlet-process är diskreta distributioner kan vi representera var är en kort notering för vilket är en delta-funktion som tar 1 om och 0 någon annanstans. En intressant effekt av detta är att eftersom G definieras på detta sätt finns det en positiv sannolikhet för att olika prover har samma värde . Som vi kommer att se senare skapar detta en klustereffekt som kan användas för att utföra klusteranalys på datamängder.

Genom att använda ovanstående definitioner och observationer vill vi uppskatta den bakre delen av Dirichlet-processen med tanke på proverna θ. Ändå eftersom vi vet det och genom att använda Bayes-reglerna och konjugatet mellan Dirichlet och Multinomial har vi det och .

Ekvation 1: Posterior Dirichlet Process

Den här egenskapen är mycket viktig och används av de olika DP-representationerna.

3. Dirichlet-processrepresentationer

I de tidigare segmenten definierade vi Dirichlet-processen och presenterade dess teoretiska modell. En viktig fråga som vi måste svara på är hur vi vet att ett sådant objekt existerar och hur vi kan konstruera och representera en Dirichlet-process.

De första indikationerna på existens tillhandahölls av Ferguson som använde Kolmogorov Consistency Theorem, gav definitionen av en Dirichlet-process och beskrev den Posterior Dirichlet-processen. Fortsätter sin forskning, Blackwell och MacQueen använde de Finettis teorem för att bevisa förekomsten av ett sådant slumpmässigt sannolikhetsmått och introducerade Blackwell-MacQueen-urnschemat som uppfyller egenskaperna hos Dirichlet Process. 1994 Sethuraman gav ett ytterligare enkelt och direkt sätt att konstruera en DP genom att införa den stick-breaking-konstruktionen. Slutligen tillhandahölls en annan representation av Aldous som introducerade den kinesiska restaurangprocessen som ett effektivt sätt att konstruera en Dirichlet-process.

De olika representationerna av Dirichlet-processen är matematiskt ekvivalenta men deras formulering skiljer sig åt eftersom de undersöker problemet ur olika synvinklar. Nedan presenterar vi de vanligaste representationerna som finns i litteraturen och vi fokuserar på den kinesiska restaurangprocessen som ger ett enkelt och beräkningseffektivt sätt att konstruera inferensalgoritmer för Dirichlet Process.

3.1 Blackwell-MacQueen-urnsystemet

Blackwell-MacQueen-urnschemat kan användas för att representera en Dirichlet-process och den introducerades av Blackwell och MacQueen. Det är baserat på Pólya-urnschemat som kan ses som den motsatta modellen för provtagning utan utbyte. I Pólya-urnschemat antar vi att vi har en icke-transparent urn som innehåller färgade kulor och vi ritar slumpmässigt. När vi drar en boll observerar vi dess färg, vi lägger tillbaka den i urnan och vi lägger till en ytterligare boll av samma färg. Ett liknande schema används av Blackwell och MacQueen för att konstruera en Dirichlet-process.

Detta schema ger en sekvens av θ₁,θ₂, ... med villkorade sannolikheter . I detta schema antar vi att G₀ är en fördelning över färger och varje θ_n representerar färgen på bollen som placeras i urnen. De algoritm enligt följande:

· Vi börjar med en tom urna.

· Med sannolikhet proportionell mot α vi ritar och vi lägger till en boll av denna färg i urnen.

· Med sannolikheten proportionell mot n-1 drar vi en slumpmässig boll från urnen, vi observerar dess färg, vi placerar den tillbaka till urnen och vi lägger till en ytterligare boll av samma färg i urnen.

Tidigare började vi med en Dirichlet-process och härledde Blackwell-MacQueen-schemat. Låt oss nu börja omvända från Blackwell-MacQueen-schemat och härleda DP. Sedan θ_i drogs på ett iid sätt från G, kommer deras gemensamma fördelning att vara oförändrad för alla ändliga permutationer och därmed är de utbytbara. Följaktligen genom att använda de Finettis teorem har vi att det måste finnas en fördelning över åtgärder för att göra dem idiska och denna distribution är Dirichlet-processen. Som ett resultat bevisar vi att Blackwell-MacQueen-urnsystemet är en representation av DP och det ger oss ett konkret sätt att konstruera det. Som vi kommer att se senare motsvarar detta schema matematiskt den kinesiska restaurangprocessen.

3.2 Den pinnbrytande konstruktionen

Den stick-breaking konstruktion är ett alternativt sätt att representera en Dirichlet-process som introducerades av Sethuraman. Det är ett konstruktivt sätt att bilda distribution och använder följande analogi: Vi antar att vi har en pinne med längd 1, vi bryter den i position β₁ och vi tilldelar π₁ lika med längden på den del av pinnen som vi bröt. Vi upprepar samma process för att få π₂, Pi₃,… etc; på grund av hur detta system definieras kan vi fortsätta göra det oändliga tider.

Baserat på ovanstående π_k kan modelleras som Där medan som i föregående scheman samplas θ direkt av basfördelningen . Följaktligen kan G-fördelningen skrivas som en summa av delta-funktioner viktade med π_k sannolikheter som är lika med . Således ger den stickbrytande konstruktionen oss ett enkelt och intuitivt sätt att konstruera en Dirichlet-process.

3.3 Den kinesiska restaurangprocessen

Den kinesiska restaurangprocessen, som introducerades av Aldous, är ett annat effektivt sätt att representera en Dirichlet-process och den kan kopplas direkt till Blackwell-MacQueen-urnsschemat. Detta schema använder följande analogi: Vi antar att det finns en kinesisk restaurang med oändligt många bord. När kunderna går in i restaurangen sitter de slumpmässigt vid något av de ockuperade borden eller så väljer de att sitta vid det första tillgängliga tomma bordet.

CRP definierar en fördelning på de positiva heltalens partitionsutrymme. Vi börjar med att rita θ₁, ... θ_n från Blackwell-MacQueen-urnsschemat. Som vi diskuterade i de föregående segmenten förväntar vi oss en klustereffekt och därmed kommer det totala antalet unika θ-värden k att bli betydligt mindre än n. Således definierar detta en partition av uppsättningen {1,2,…, n} i k-kluster. Följaktligen inducerar ritning från Blackwell-MacQueen-urnschemat en slumpmässig partition av uppsättningen {1,2,…, n}. Den kinesiska restaurangprocessen är detta inducerad distribution över partitioner. Algoritmen är som följer:

· Vi börjar med en tom restaurang.

· Den 1^st kund sitter alltid på 1^st bord

· N + 1^th kunden har två alternativ:

o Sitt på det första lediga bordet med sannolikhet

o Sitt på någon av de kth ockuperade borden med sannolikhet
var är antalet personer som sitter på det bordet

Där α är dispersionsvärdet för DP och n är det totala antalet kunder i restaurangen vid en given tidpunkt. Den latenta variabeln z_i lagrar tabellnumret för i^th kund och tar värden från 1 till k_n där k_n är det totala antalet upptagna bord när n kunder är i restaurangen. Vi bör notera att k_n kommer alltid att vara mindre eller lika med n och i genomsnitt handlar det om . Slutligen bör vi notera att sannolikheten för bordsarrangemang är oförändrad för permutationer. Således z_i är utbytbart vilket innebär att tabeller med samma storlek på kunder har samma sannolikhet.

Den kinesiska restaurangprocessen är starkt kopplad till Pólya-urnsystemet och Dirichlet-processen. CRP är ett sätt att specificera en distribution över partitioner (tabelltilldelningar) på n poäng och kan användas som föregångare på mellanslaget för latent variabel z_i som bestämmer klustertilldelningarna. CRP motsvarar Pólyas urnschema med enda skillnad att den inte tilldelar parametrar till varje tabell / kluster. Att gå från CRP till Pólyas urnsschema vi ritar för alla tabeller k = 1,2 ... och sedan för varje x_i som är grupperad till tabell z_i tilldela en . Med andra ord tilldela den nya x_i parametern θ i tabellen. Äntligen sedan vi kan inte tilldela θ till oändliga tabeller från början kan vi bara tilldela en ny θ varje gång någon sitter på ett nytt bord. På grund av allt ovan kan CRP hjälpa oss att bygga beräkningseffektiva algoritmer för att utföra klusteranalys på datamängder.

I det här inlägget diskuterade vi Dirichlet-processen och flera sätt att konstruera den. Vi kommer att använda ovanstående idéer i nästa artikel. Vi kommer att introducera Dirichlet Process Mixture Model och vi kommer att använda den kinesiska restaurangrepresentationen för att konstruera Dirichlet Process och preform Cluster Analysis. Om du har missat några poäng oroa dig inte eftersom saker och ting kommer att börja bli tydligare med de kommande två artiklarna.

Jag hoppas att du tyckte det här inlägget var intressant. Om du gjorde det, ta en stund att dela den på Facebook och Twitter. 🙂