Dirichlet-prosessiseosmalli

• Kesäkuu 23, 2014
• Vasilis Vryniotis
• . 2 kommenttia

Tämä blogi on sarjan neljäs osa Klusterointi Dirichlet-prosessiseosmalleilla. Aiemmissa artikkeleissa keskustelimme äärellisistä Dirichlet-sekoitusmalleista ja otimme niiden mallin rajan äärettömille k-klustereille, mikä johti meidät Dirichlet-prosessien käyttöönottoon. Kuten näimme, tavoitteemme on rakentaa sekoitusmalli, joka ei vaadi meitä määrittelemään k klusterien / komponenttien määrää alusta alkaen. Jälkeen esittämällä erilaisia ​​esityksiä Dirichlet-prosesseista, on nyt aika käyttää tosiasiallisesti DP: itä äärettömän sekoitusmallin rakentamiseen, joka antaa meille mahdollisuuden ryhmitellä. Tämän artikkelin tavoitteena on määritellä Dirichlet-prosessisekoitusmallit ja keskustella kiinalaisen ravintolaprosessin ja Gibbs-näytteenoton käytöstä. Jos et ole lukenut aiempia viestejä, on erittäin suositeltavaa tehdä niin, koska aihe on vähän teoreettinen ja vaatii hyvää ymmärrystä mallin rakentamisesta.

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.

1. Dirichlet-prosessiseosmallin määritelmä

Dirichlet-prosessien käyttäminen antaa meille mahdollisuuden sekoitusmallille, jossa on ääretön komponentti, jonka voidaan ajatella ottavan äärellisen mallin raja k: lle äärettömyyteen. Oletetaan, että meillä on seuraava malli:

Kaava 1: Dirichlet-prosessiseosmalli

Missä G on määritelty ja käytetään lyhyenä merkintänä mikä on deltafunktio, joka vie yhden, jos ja 0 muualla. Θ_i ovat klusteriparametreja, joista otetaan näytteitä G: stä. Generatiivinen jakauma F määritetään klusteriparametreilla θ_i ja sitä käytetään luomaan x_i havaintoja. Viimeinkin voimme määritellä tiheysjakauman mikä on seosjakaumamme (laskettava ääretön seos) sekoitussuhteilla ja komponenttien sekoittaminen .

Kuva 1: Dirichlet-prosessiseoksen mallin graafinen malli

Yllä on DPMM: n vastaava graafinen malli. G₀ on DP: n perusjakauma ja se valitaan yleensä konjugaatiksi ennen generatiivista jakaumaa F, jotta laskennat olisivat helpompia ja houkuttelevia matemaattisia ominaisuuksia hyödynnettävissä. Α on Dirichlet-prosessin skalaarinen hyperparametri ja vaikuttaa saamien klustereiden lukumäärään. Mitä suurempi α-arvo, sitä enemmän rypäleitä; mitä pienempi α, sitä vähemmän klustereita. Meidän on huomattava, että arvo α ilmaisee uskon vahvuus julkaisussa G₀. Suuri arvo osoittaa, että suurin osa näytteistä on erillisiä ja niiden arvot keskittyvät G: hen₀. G on satunnainen jakauma DP: stä otetun parametritilan Θ yli, joka antaa todennäköisyydet parametreille. Θ_i on parametrivektori, joka on vedetty G-jakaumasta ja sisältää klusterin parametrit, F-jakauma parametroidaan θ_i ja x_i on datapiste, jonka generatiivinen jakelu F.

On tärkeää huomata, että θ_i ovat elementtejä space-parametritilassa ja ne ”konfiguroivat” klusterimme. Niitä voidaan pitää myös piilevinä muuttujina x: llä_i joka kertoo meille mistä komponentista / klusterista x_i tulee ja mitkä ovat tämän komponentin parametrit. Siten jokaiselle x: lle_i että havaitsemme, piirrämme θ_i G-jakaumasta. Jokaisella piirtämisellä jakauma muuttuu edellisistä valinnoista riippuen. Kuten näimme Blackwell-MacQueen urn -mallissa, G-jakauma voidaan integroida ja tulevaisuuden sele_i riippuvat vain G: stä₀: . Parametrien θi arviointi edellisestä kaavasta ei ole aina mahdollista, koska monet toteutukset (kuten kiinalainen ravintolaprosessi) sisältävät eksponentiaalisesti kasvavat k komponentit. Siten käytetään likimääräisiä laskentamenetelmiä, kuten Gibbs-näytteenotto. Lopuksi meidän on huomattava, että vaikka k-klusterit ovat äärettömiä, aktiivisten klusterien lukumäärä on . Siten θ_i toistaa ja osoittaa klusterointivaikutusta.

2. Määrittelemällä ääretön sekoitusmalli kiinalaisella ravintolaprosessilla

Edellisessä segmentissä määritelty malli on matemaattisesti vankka, silti sillä on suuri haitta: jokaiselle uudelle x: lle_i että havaitsemme, meidän on otettava uusi θ_i ottaen huomioon aikaisemmat values-arvot. Ongelmana on, että monissa tapauksissa näiden parametrien näytteenotto voi olla vaikea ja laskennallisesti kallis tehtävä.

Vaihtoehtoinen lähestymistapa on käyttää kiinalaista ravintolaprosessia piilevien muuttujien z mallintamiseen_i klusteritehtävistä. Tällä tavalla using: n käytön sijasta_i Käytämme piilevää muuttujaa z merkitsemään sekä klusterin parametreja että klusterimäärityksiä_i osoittaa klusterin tunnus ja määrittää klusteriparametrit tämän arvon avulla. Seurauksena on, että meidän ei enää tarvitse ottaa näytteitä time joka kerta kun saamme uuden havainnon, vaan saamme sen sijaan klusterimäärityksen ottamalla näytteen z_i CRP: ltä. Tämän järjestelmän avulla uudesta θ otetaan näytteitä vain silloin, kun meidän on luotava uusi klusteri. Seuraavassa esittelemme tämän lähestymistavan mallin:

Kaava 2: Seosmalli CRP: n kanssa

Yllä oleva on generatiivinen malli, joka kuvaa kuinka x_i ja klusterit luodaan. Klusterianalyysin suorittamiseen on käytettävä havaintoja x_i ja arvioi klusteritehtävät z_i.

3. Seoksen mallin päätelmät ja Gibbs-näytteenotto

Valitettavasti koska Dirichlet-prosessit eivät ole parametrejä, me ei voi käyttää EM-algoritmia estimoida piilevät muuttujat, jotka tallentavat klusterimääritykset. Tehtävien arvioimiseksi käytämme Pudotut Gibbs-näytteet.

Collapsed Gibbs -näytteenotto on yksinkertainen Markov Chain Monte Carlo (MCMC) -algoritmi. Se on nopea ja antaa meille mahdollisuuden integroida joitain muuttujia samalla kun näytteitä toisesta muuttujasta. Siitä huolimatta nämä algoritmit vaativat meitä valitsemaan G₀ joka on konjugaatti ennen F-generatiivista jakautumista, jotta pystytään ratkaisemaan analyyttisesti yhtälöt ja pystyä ottamaan näytteitä suoraan .

Ryhmittymien Gibbs-näytteenottojen vaiheet, joita me arvioimme klusterimäärityksiin, ovat seuraavat:

• Alusta z_i klusterimääritykset satunnaisesti
• Toista kunnes lähentyminen
• Valitse satunnaisesti ax_i
  
• Pidä toinen z_j kiinteä jokaiselle j ≠ i: lle:
• Määritä uusi arvo z: lle_i laskemalla ”CRP-todennäköisyys”, joka riippuu z: stä_j ja x_j kaikista j ≠ i:

Seuraavassa artikkelissa keskitymme siihen, miten rypäleanalyysi suoritetaan Dirichlet Process Mixture -malleja käyttämällä. Määrittelemme kaksi erilaista Dirichlet-prosessisekoitusmallia, jotka käyttävät kiinalaista ravintolaprosessia ja Collapsed Gibbs -näytteenottoa ryhmittelyyn jatkuvissa tietoaineistoissa ja asiakirjoissa.