Dirichlet-prosessi kiinalainen ravintolaprosessi ja muut edustustot

• Voi 20, 2014
• Vasilis Vryniotis
• . Ei kommentteja

Tämä artikkeli on kolmas osa sarjasta Klusterointi Dirichlet-prosessiseosmalleilla. Edellisen kerran määritimme rajallisen seosmallin Dirichlet Distributionin pohjalta ja esitimme kysymyksiä siitä, miten voimme tehdä tämän mallin äärettömäksi. Keskustelimme lyhyesti mallin rajan ottamisesta, kun klustereiden k-lukumäärä on ääretön, mutta kuten korostimme, tällaisen kohteen olemassaolo ei ole triviaalia (toisin sanoen, miten me todella "otamme mallin rajan") ”?). Muistutuksena syy, miksi haluamme tehdä k: stä ääretön, johtuu siitä, että tällä tavalla meillä on ei-parametrinen malli, joka ei vaadi meitä määrittelemään ennalta klustereiden kokonaismäärää datassa.

Päivitys: Datumbox Machine Learning Framework on nyt avoimen lähdekoodin ja ilmainen download. Tutustu pakettiin com.datumbox.framework.machinelearning.clustering nähdäksesi Dirichlet-prosessisekoitusmallien käyttöönotto Javassa.

Vaikka tavoitteemme on rakentaa malli, joka kykenee suorittamaan klustereita aineistoissa, meidän on ennen sitä keskusteltava Dirichlet-prosesseista. Annamme sekä tarkat matemaattiset määritelmät että intuitiivisemmat selitykset DP: lle ja keskustelemme tavoista rakentaa prosessi. Näitä rakenteita / esityksiä voidaan pitää tapana löytää Dirichlet-prosessin esiintymisiä ”tosielämässä”.

Huolimatta siitä, että yritin mukauttaa tutkimusraporttiani siten, että näitä blogiviestejä on helpompi seurata, on silti tärkeää määritellä tarvittavat matemaattiset työkalut ja jakaumat, ennen kuin ryhdymme mallien käyttöön. Dirichlet-prosessimallit ovat aktiivisen tutkimuksen aihe, mutta ne edellyttävät tilastojen ja stokastisten prosessien hyvää tuntemusta ennen niiden käyttöä. Toinen ongelma on se, että kuten näemme tästä artikkelista, Dirichlet-prosessit voidaan esittää / rakentaa monin tavoin. Tämän seurauksena useat akateemiset artikkelit käyttävät täysin erilaisia ​​merkintöjä / käytäntöjä ja tutkivat ongelmaa eri näkökulmista. Tässä viestissä yritän selittää ne mahdollisimman yksinkertaisesti ja käyttää samaa merkintää. Toivottavasti asiat tulevat selvemmiksi kahdella tulevalla artikkelilla, jotka keskittyvät Dirichlet-prosessiseosmallien määrittelyyn ja siihen, miten niitä todella käytetään klusterianalyysin suorittamiseen.

1. Dirichlet-prosessin määritelmä

Dirichlet-prosessi Θ-avaruudessa on stokastinen prosessi. Se on todennäköisyysjakauma "todennäköisyysjakaumiin avaruudessa" ja a vedä siitä on erillinen jakauma. Muodollisemmin Dirichlet-jakauma on jakauma todennäköisyysmittareille. A todennäköisyysmitta on avaruuden ets - [0,1] osajoukkojen funktio. G on DP-hajautettu satunnaistodennäköisyysmitta, jota merkitään , jos jossakin osiossa (A₁,… A_n) avaruudesta Θ meillä on se .

Kuva 1: Lopullisten osioiden marginaalit ovat Dirichlet-jakautuneita.

DP: llä on kaksi parametria: Ensimmäinen on perusjakauma G₀ joka toimii kuin keskiarvo . Toinen on lujuusparametri α, joka on ehdottomasti positiivinen ja toimii kuten käänteisvarianssi . Se määrittää ulostulojakauman arvojen toistamisen laajuuden. Mitä suurempi arvo a, sitä pienempi toisto; mitä pienempi arvo, sitä korkeampi lähtöjakauman arvojen toisto. Lopuksi Θ-avaruus on parametritila, jolla määritämme DP: n. Lisäksi tila Θ on myös G: n määritysalue₀ joka on sama kuin G.

Yksinkertaisempi ja enemmän intuitiivisella tavalla Dirichlet-prosessin selittäminen on seuraava. Oletetaan, että meillä on tila Θ, joka voidaan jakaa millä tahansa äärellisellä tavalla (A₁,…, A_n) ja todennäköisyysjakauma G, joka osoittaa niille todennäköisyydet. G on spesifinen todennäköisyysjakauma Θ: lle, mutta on monia muita. Dirichlet-prosessi mallilla exactly mallintaa juuri tätä; se on jakauma kaikille mahdollisille avaruuden prob todennäköisyysjakaumille. Dirichlet-prosessi parametrisoidaan G: n kanssa₀ perusfunktio ja α-pitoisuusparametri. Voidaan sanoa, että G jakautuu DP: n mukaan parametreilla α ja G₀ jos todennäköisyyksien yhteisjakauma, jonka G osoittaa Θ: n osioille, seuraa Dirichlet-jakaumaa. Vaihtoehtoisesti voimme sanoa, että todennäköisyydet, jotka G antaa mihin tahansa ite: n rajalliseen osioon, seuraa Dirichlet-jakaumaa.

Kuva 2: Graafinen malli Dirichlet-prosessista

Viimeinkin yllä voimme nähdä graafinen malli DP: stä. Meidän on huomattava, että a on skalaarinen hyperparametri G₀ on DP: n, G: n perusjakauma, satunnainen jakauma Θ parametrialueelle, joka on otettu DP: stä ja joka antaa todennäköisyydet parametreille_i on parametrivektori, joka vedetään G-jakaumasta ja se on avaruuden element elementti.

2. Posterior Dirichlet -prosessit

Posterior Dirichlet -prosesseista keskustelivat Ferguson. Aloitetaan piirtämällä satunnainen todennäköisyysmitta G Dirichlet-prosessista, . Koska G on todennäköisyysjakauma over: lle, voimme myös ottaa otoksen tästä jakaumasta ja piirtää itsenäisiä identtisesti jakautuneita näytteitä θ₁,…, Θ_n ~ G. Koska Dirichlet-prosessista saadut vedot ovat erillisiä jakaumia, voimme edustaa jossa on lyhyt merkintätapa mikä on deltafunktio, joka vie yhden, jos ja 0 muualla. Tämän mielenkiintoinen vaikutus on, että koska G määritellään tällä tavalla, on positiivinen todennäköisyys, että eri näytteillä on sama arvo . Kuten näemme myöhemmin, tämä luo klusterointivaikutuksen, jota voidaan käyttää klusterianalyysin toteuttamiseen aineistoissa.

Käyttämällä yllä olevia määritelmiä ja havaintoja haluamme arvioida Dirichlet-prosessin takaosan näytteille θ. Siitä huolimatta, koska tiedämme sen ja käyttämällä Bayesin sääntöjä ja Dirichletin ja Multinomialin välistä liitosta meillä on se ja .

Yhtälö 1: Posterior Dirichlet -prosessi

Tämä ominaisuus on erittäin tärkeä ja sitä käyttävät erilaiset DP-esitykset.

3. Dirichlet-prosessin esitykset

Edellisissä segmenteissä määriteltiin Dirichlet-prosessi ja esitettiin sen teoreettinen malli. Yksi tärkeä kysymys, johon meidän on vastattava, on se, mistä tiedämme, että sellainen esine on olemassa ja miten voimme rakentaa ja edustaa Dirichlet-prosessi.

Ensimmäiset viitteet olemassaolosta antoi Ferguson joka käytti Kolmogorovin johdonmukaisuuslausetta, antoi Dirichlet-prosessin määritelmän ja kuvasi Posterior Dirichlet -prosessia. Jatkamalla tutkimustaan Blackwell ja MacQueen käytti de Finettin lauseen todistamaan tällaisen satunnaisen todennäköisyysmittauksen olemassaolon ja esitteli Blackwell-MacQueen -urnajärjestelmän, joka täyttää Dirichlet-prosessin ominaisuudet. Vuonna 1994 Sethuraman tarjosi yksinkertaisen ja suoran tavan rakentaa DP ottamalla käyttöön Stick-breaking -rakenne. Lopuksi toisen edustuksen tarjosi Aldous joka esitteli kiinalaisen ravintolaprosessin tehokkaana tapana rakentaa Dirichlet-prosessi.

Dirichlet-prosessin eri esitykset ovat matemaattisesti samanarvoisia, mutta niiden muotoilu eroaa toisistaan, koska ne tutkivat ongelmaa eri näkökulmista. Seuraavassa esitämme yleisimmät kirjallisuudessa esiintyvät esitykset ja keskitymme kiinalaiseen ravintolaprosessiin, joka tarjoaa yksinkertaisen ja laskennallisesti tehokkaan tavan rakentaa päättelyalgoritmeja Dirichlet-prosessille.

3.1 Blackwell-MacQueen -urnajärjestelmä

Blackwell-MacQueen -urnajärjestelmää voidaan käyttää kuvaamaan Dirichlet-prosessia, ja sen otti käyttöön Blackwell ja MacQueen. Se perustuu Pólyan urnajärjestelmään, joka voidaan nähdä päinvastaisena näytteenoton mallina ilman korvaamista. Pólya-urnakaaviossa oletamme, että meillä on läpinäkymätön urna, joka sisältää värillisiä palloja ja piirrämme palloja satunnaisesti. Piirrettäessä palloa tarkkailemme sen väriä, laitamme sen takaisin uraan ja lisätään vielä sama väri. Samanlaista järjestelmää käyttävät Blackwell ja MacQueen rakentamaan Dirichlet-prosessin.

Tämä kaavio tuottaa sarjan θ₁, θ₂,… kanssa ehdolliset todennäköisyydet . Tässä kaaviossa oletetaan, että G₀ on jakauma väreille ja jokaiselle θ_n edustaa uraan sijoitetun pallon väriä. algoritmi on seuraava:

· Aloitamme tyhjällä urnalla.

· Todennäköisyydellä verrannollinen α me piirrämme ja lisätään tämän värinen pallo uurnaan.

· Piirrämme todennäköisyydellä, joka on verrannollinen n-1: een, satunnaisen pallon urnasta, tarkkailemme sen väriä, sijoitamme sen takaisin urnaan ja lisäämme uraan samanvärisen lisäpallon.

Aikaisemmin aloitimme Dirichlet-prosessilla ja saimme Blackwell-MacQueen-järjestelmän. Aloitetaan nyt käänteisesti Blackwell-MacQueen-järjestelmästä ja johdetaan DP. Koska θ_i ne on piirretty iid-tavalla G: stä, niiden yhteinen jakauma on invariantti kaikille äärellisille permutaatioille ja siten ne ovat vaihdettavissa. Tästä syystä de Finettin lauseen avulla meillä on oltava jakauma toimenpiteiden välillä, jotta ne olisivat idiidejä, ja tämä jakauma on Dirichlet-prosessi. Tuloksena osoitamme, että Blackwell-MacQueen -urnajärjestelmä on DP: n esitys ja se antaa meille konkreettisen tavan rakentaa se. Kuten näemme myöhemmin, tämä järjestelmä vastaa matemaattisesti kiinalaista ravintolaprosessia.

3.2 Puikkorikko rakenne

Puikkorikko on vaihtoehtoinen tapa edustaa Dirichlet-prosessia Sethuraman. Se on rakentava tapa muodostaa jakelu ja käyttää analogian mukaisesti: Oletetaan, että meillä on keppi, jonka pituus on 1, murtamme sen asemassa β₁ ja osoitamme π₁ yhtä suuri kuin murtamamme tikun osan pituus. Toistetaan sama prosessi π: n saamiseksi₂, Pi₃,… jne; tämän järjestelmän määrittelytavan vuoksi voimme jatkaa sen tekemistä loputtomasti.

Edellä olevan perusteella π_k voidaan mallintaa , Jossa kun taas kuten edellisissä kaavioissa, θ: n näytteet otetaan suoraan Base-jakelulla . Näin ollen G-jakauma voidaan kirjoittaa π: llä painotettujen deltafunktioiden summana_k todennäköisyyksiä, joka on yhtä suuri kuin . Niinpä tikkuja rikkova rakenne antaa meille yksinkertaisen ja intuitiivisen tavan rakentaa Dirichlet-prosessi.

3.3 Kiinalainen ravintola-prosessi

Kiinalainen ravintola-prosessi, jonka esitteli Aldous, on toinen tehokas tapa edustaa Dirichlet-prosessia, ja se voidaan liittää suoraan Blackwell-MacQueen -urnajärjestelmään. Tämä järjestelmä käyttää analogian mukaisesti: Oletamme, että siellä on kiinalainen ravintola, jossa on äärettömän paljon pöytiä. Kun asiakkaat menevät ravintolaan, he istuvat satunnaisesti mille tahansa varatusta pöydästä tai haluavat istua ensimmäisen vapaan pöydän ääressä.

CRP määrittelee jakauman positiivisten kokonaislukujen osioiden tilassa. Aloitamme piirtämällä θ₁,… Θ_n Blackwell-MacQueen -urnajärjestelmästä. Kuten edellisissä segmenteissä keskustelimme, odotamme klusteroivan vaikutuksen ja siten ainutlaatuisten θ-arvojen k kokonaismäärä on merkittävästi pienempi kuin n. Siten tämä määrittelee joukon {1,2,…, n} osion k-ryhmässä. Näin ollen piirustus Blackwell-MacQueen -urna-kaaviosta indusoi satunnaisen osion joukosta {1,2,…, n}. Kiinalainen ravintola-prosessi on tämän aiheuttama jakelu osioille. Algoritmi on seuraava:

· Aloitamme tyhjällä ravintolalla.

· 1^st asiakas istuu aina 1^st taulukko

· N + 1^th Asiakkaalla on 2 vaihtoehtoa:

o Istu 1. vapaalla pöydällä todennäköisyydellä

o Istu millä tahansa k: sta varatusta taulukosta todennäköisyydellä
jossa on pöydällä istuvien ihmisten lukumäärä

Missä α on DP: n dispersioarvo ja n on ravintolassa olevien asiakkaiden kokonaismäärä tiettynä ajankohtana. Piilevä muuttuja z_i tallentaa i-taulukon numeron^th asiakas ja ottaa arvot välillä 1 - k_n missä k_n on varattujen pöytien kokonaismäärä, kun n asiakasta on ravintolassa. Meidän on huomattava, että k_n on aina pienempi tai yhtä suuri kuin n ja keskimäärin se on noin . Lopuksi on huomattava, että pöydän järjestelyn todennäköisyys on muuttumaton permutaatioihin. Siten z_i on vaihdettavissa, mikä tarkoittaa, että saman kokoisilla pöydillä on sama todennäköisyys.

Kiinalainen ravintola-prosessi on vahvasti yhteydessä Pólyan urnamalliin ja Dirichlet-prosessiin. CRP on tapa määrittää a jakelu osioille (taulukon määritykset) n pistettä ja niitä voidaan käyttää prioriteettina piilevän muuttujan z tilassa_i joka määrittää klusterimääritykset. CRP vastaa Pólyan urnamallia vain sillä erolla, että se ei määritä parametreja kullekin taulukolle / klusterille. Mennä CRP: stä Pólyan urnajärjestelmään me piirrämme kaikille taulukoille k = 1,2… ja sitten jokaiselle x: lle_i joka on ryhmitelty taulukkoon z_i määritä a . Toisin sanoen määritä uusi x_i taulukon parametri θ. Viimeinkin siitä lähtien emme voi määrittää tables loputtomiin taulukoihin alusta alkaen voimme vain määrittää uuden θ aina, kun joku istuu uudella pöydällä. Kaiken edellä mainitun vuoksi CRP voi auttaa meitä rakentamaan laskennallisesti tehokkaita algoritmeja klusterianalyysin suorittamiseksi aineistoissa.

Tässä viestissä keskustelimme Dirichlet-prosessista ja useista tavoista rakentaa se. Käytämme yllä olevia ideoita seuraavassa artikkelissa. Esittelemme Dirichlet-prosessiseosmallin ja käytämme kiinalaisen ravintolan edustusta rakentamaan Dirichlet-prosessin ja esimuottien klusterianalyysin. Jos unohdit muutaman pisteen, älä huoli, sillä asiat alkavat tulla selvemmiksi seuraavien kahden artikkelin kanssa.

Toivottavasti pidit tätä viestiä mielenkiintoisena. Jos teit niin, ota hetki jakaa se Facebookissa ja Twitterissä. 🙂