Ziggurat-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. maaliskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Ziggurat-algoritmi ( eng. Ziggurat Algorithm , Ziggurat Method ) on algoritmi näennäissatunnaisten lukujen näytteenottoon . Koska hän edustaa näytteenottoalgoritmien luokkaa, jolla on poikkeama , hän luottaa työssään tasaisesti jakautuneiden satunnaislukujen lähteeseen - yleensä pseudosatunnaislukugeneraattoriin tai ennalta laskettuun taulukkoon. Algoritmilla luodaan arvoja monotonisesti laskevan todennäköisyysjakauman perusteella . Sitä voidaan soveltaa myös symmetriseen unimodaaliseen jakaumaan, kuten normaalijakaumaan , valitsemalla arvoja sen toisesta puoliskosta ja sitten tarvittaessa muuttamalla symmetriseksi arvoksi aritmeettisen negaatiooperaation avulla. Yksi 1960-luvulla kehitetyn algoritmin tekijöistä on George Marsaglia .

Yksinkertaisimmassa tapauksessa algoritmin palauttaman arvon laskeminen vaatii vain yhden kelluvan ja yhden satunnaistaulukkoindeksin luomisen, jota seuraa yksi taulukkohaku, yksi kertolasku ja yksi vertailu. Joskus (paljon harvemmissa tapauksissa) tarvitaan monimutkaisempia laskelmia. Tämä algoritmi on kuitenkin laskennallisesti paljon nopeampi kuin kaksi yleisimmin käytettyä normaalijakauman satunnaislukujen generointimenetelmää: Marsaglian polaarimenetelmä ja Box-Muller-muunnos , jotka edellyttävät vähintään yhden logaritmin ja yhden neliön laskemista. juuri jokaiselle luodulle arvoparille. Koska Ziggurat-algoritmi on kuitenkin monimutkaisempi toteuttaa, sitä käytetään useimmiten tapauksissa, joissa tarvitaan suuri määrä satunnaislukuja.

Itse termi "Ziggurat Algorithm" esiintyy Marsaglian ja Wai Van Tsangin yhteisessä työssä vuonna 2000, ja se on saanut nimensä, koska se perustuu käsitteellisesti todennäköisyysjakauman kattamiseen suorakaiteen muotoisilla segmenteillä pinottuina päällekkäin pienenevän koon mukaan (kun alhaalta ylöspäin katsottuna), jolloin tuloksena on zikguraattia muistuttava hahmo .

Teoreettinen perusta

Ziggurat-algoritmi on bias-näytteenottoalgoritmi. Se luo satunnaisesti pisteen, joka poikkeaa hieman halutusta jakaumasta, ja tarkistaa sitten, osuuko luotu piste tarkalleen sen sisään. Jos ei, algoritmi yrittää uudelleen. Jos piste sijaitsee todennäköisyystiheysfunktion käyrän alla, niin sen x -koordinaatti on haluttu satunnaisluku halutulla jakaumalla.

Jakauma, josta algoritminäytteet koostuu alueista, joiden pinta-ala on yhtä suuri; suorakulmio kattaa pääosan halutusta jakaumasta ja on "pyramidi" ei-suorakulmaisella pohjalla, joka sisältää jakauman loppuosan tai "häntä". $n$ $n-1$

Tietylle kaikille määritetylle monotonisesti pienenevälle todennäköisyystiheysfunktiolle zikguratin kanta määritellään kaikiksi pisteiksi jakauman sisällä ja joidenkin alapuolella . Se koostuu suorakaiteen muotoisesta osasta - , ja (yleensä äärettömästä) jakauman jäännöksestä (häntä), jossa (ja ). $f(x)$ $x\geqslant 0$ $y_{1}=f(x_{1})$ $(0, 0)$ $(x_{1},y_{1})$ $x>x_{1}$ $y<y_{1}$

Tämän tason (kutsutaanko sitä tasoksi 0) pinta-ala on . Lisätään sen yläosaan uusi suorakaiteen muotoinen leveys- ja korkeustaso , jotta sen pinta-ala on myös yhtä suuri kuin . Tämän tason yläosa on korkeudella ja leikkaa tiheysfunktion kohdassa, jossa . Tämä taso sisältää kaikki tiheysfunktiopisteet välillä ja , mutta (toisin kuin perustaso) sisältää myös muita pisteitä, kuten , jotka eivät kuulu haluttuun jakaumaan. $A$ $x_{1}$ $A/x_{1}$ $A$ ${\displaystyle y_{2}=y_{1}+A/x_{1))$ $(x_{2},y_{2})$ $y_{2}=f(x_{2})$ $y_1$ $y_2$ ${\näyttötyyli (x_{1},y_{2})}$

Kaikki seuraavat tasot asetetaan päällekkäin samalla tavalla. Valmiiksi lasketun kokotaulukon käyttämiseksi ( käytetään hyvin usein), tulee valita sellainen , että ylempi suorakaiteen muotoinen taso numerolla saavuttaa jakauman huipun täsmälleen pisteessä . $n$ $n=256$ $x_{1}$ $x_{n}=0$ $n-1$ ${\näyttötyyli (0,f(0))}$

Taso, jonka korkeus on numero , on paikan päällä ja se voidaan jakaa leveydeltään kahteen alueeseen: osaan alkaen - (yleensä suurempi), joka sisältyy kokonaan tiettyyn jakaumaan, ja osaan -lta - (pienempi), joka sisältyy vain osittain. $i$ $y_{i}$ $y_{i+1}$ $0$ $x_{{i+1}}$ $x_{{i+1}}$ $x_{i}$

Unohtaen hetkeksi kysymyksen tason 0 erikoistapauksesta, jolla on tasaisesti jakautuneet luvut ja , algoritmia voidaan kuvata seuraavasti: $U_{0}$ $U_{1}$ ${\näyttötyyli \in [0,1)}$

Valitse satunnainen taso . $0\leqslant i<n$
Laita . ${\displaystyle x=U_{0}x_{i))$
Jos , palauta . $x<x_{i+1}$ $x$
Laita . $y=y_{i}+U_{1}(y_{i+1}-y_{i})$
Laske . Jos , palauta . $f(x)$ $y<f(x)$ $x$
Muussa tapauksessa valitse uudet satunnaisluvut ja palaa vaiheeseen 1.

Vaihe 1 on tason satunnainen otanta. Vaiheessa 3 tarkistetaan, onko koordinaatti hyvin annetussa tiheysfunktiossa, vaikka koordinaatista ei olisikaan tietoa . Jos ei, vaihe 4 laskee koordinaatin ja vaihe 5 tarkistaa, onko se halutun alueen sisällä. $x$ $y$ $y$

Jos tasojen määrä on riittävän suuri ja niillä on pieni korkeus, niin sama "riskivyöhyke", joka tarkistetaan vaiheen 3 jälkeen, on hyvin pieni ja algoritmi pysähtyy vaiheeseen 3 merkittävän osan ajasta. Huomaa, että ylempi taso kuitenkin aina epäonnistuu tässä testissä, koska . $n$ $n-1$ $x_{n}=0$

Taso 0 voidaan jakaa myös keski- ja raja-alueeseen, mutta raja-alue sisältää loputtoman osan funktiosta. Jos haluat käyttää samaa algoritmia tarkastaaksesi, kuuluuko piste keskialueelle, kannattaa luoda dummy . Koordinaattipisteet käsitellään yksinkertaisesti, ja siinä harvinaisessa tapauksessa, että taso 0 ja valittiin , sinun on käytettävä erityistä varaalgoritmia valitaksesi satunnaisesti piste funktion "pyrstöstä". Koska tällaista varaalgoritmia käytetään erittäin harvoin (harvinaisuus on suhteellinen ja riippuu tasosta), sen nopeudella ei ole merkittävää vaikutusta yleiseen suorituskykyyn. $x_{0}=A/y_{1}$ ${\näyttötyyli x<x_{1))$ ${\displaystyle x\geqslant x_{1))$

Siten täydellinen Ziggurat-algoritmi epäsymmetriselle jakaumille on seuraava:

Valitse satunnainen taso . $0\leqslant i<n$
Laita . ${\displaystyle x=U_{0}x_{i))$
Jos , palauta . $x<x_{i+1}$ $x$
Jos , luo piste "hännästä" käyttämällä varaalgoritmia. $i = 0$
Laita . $y=y_{i}+U_{1}(y_{i+1}-y_{i})$
Laske . Jos , palauta . $f(x)$ $y<f(x)$ $x$
Muussa tapauksessa valitse uudet satunnaisluvut ja palaa vaiheeseen 1.

Symmetrisen jakauman tapauksessa tulos voidaan tietysti yksinkertaisesti kääntää 50% ajasta. Se voi usein olla kätevää luoda ja testata vaiheessa 3 . $U_{0}\in (-1,1)$ $|x|<x_{i+1}$

Varaalgoritmit funktion hännän

Koska Ziggurat-algoritmi luo vain suurimman osan arvoista erittäin nopeasti ja vaatii varaalgoritmin tapauksissa , asiat ovat monimutkaisempia kuin suora 6-vaiheinen toteutus. Varaalgoritmi riippuu annetusta jakaumasta. $x>x_{1}$

Eksponentiaalisen jakauman tapauksessa häntä on jakaumakappaleen muodossa. Yksi tapa on palata alkeisimpaan algoritmiin ja laittaa . Toinen tapa on kutsua rekursiivisesti Ziggurat-algoritmia ja lisätä tulokseen. $E=-\ln(U_{1})$ $x=x_{1}-\ln(U_{1})$ $x_{1}$

Normaalijakauman tapauksessa Marsaglia ehdottaa kompaktia algoritmia:

Laita . ${\displaystyle x=-\ln(U_{1})/x_{1))$
Laita . $y=-\ln(U_{2})$
Jos , palauta . $2y>x^{2}$ ${\näyttötyyli x+x_{1))$
Muussa tapauksessa palaa vaiheeseen 1.

Koska taulukot ovat enemmän tai vähemmän tyypillisiä kokoja, vaiheen 3 testi onnistuu melkein aina. $x_{1}\noin 3,5$

Optimoinnit

Algoritmi voidaan tehdä tehokkaasti käyttämällä esilaskettuja taulukoita ja , mutta on olemassa muutamia muutoksia, jotka nopeuttavat sitä entisestään: $x_{i}$ $y_{i}=f(x_{i})$

Mikään algoritmissa ei riipu siitä, onko todennäköisyysjakaumafunktio normalisoitu (integraalin arvo on 1), joten normalisointivakion poistaminen voi nopeuttaa laskentaa . $f(x)$
Useimmat tasaisesti jakautuneet satunnaislukugeneraattorit perustuvat satunnaiskokonaislukugeneraattoreihin, jotka palauttavat kokonaisluvun alueelta . Taulukossa voit käyttää suoraan sellaisia numeroita kuin . $[0.2^{32}-1]$ ${\displaystyle 2^{-32}x_{i))$ $U_{0}$
Jos työskennellään symmetristen jakaumien kanssa käyttämällä symmetriaa edellä kuvatulla tavalla, satunnainen kokonaisluku voidaan tulkita etumerkillisenä lukuna alueella , ja voidaan käyttää skaalaustekijää . $U_{0}$ $[-2^{31},2^{31}-1]$ $2^{-31}$
Sen sijaan , että verrattaisiin vaiheeseen 3, on mahdollista laskea etukäteen ja verrata suoraan tähän arvoon. Jos on kokonaislukujen satunnaislukugeneraattori, arvot voidaan kertoa etukäteen (tai tapauksen mukaan) niin, että tehdään kokonaislukuvertailu. ${\displaystyle U_{0}x_{i))$ $x_{{i+1}}$ ${\displaystyle x_{i+1}/x_{i))$ $U_{0}$ $U_{0}$ $2^{32}$ $2^{{31}}$
Kahden yllä olevan muutoksen myötä raaka-arvotaulukkoa ei enää tarvita, ja se voidaan poistaa. $x_{i}$
IEEE 754 : n yhden tarkkuuden liukulukugeneraattorissa , joka käyttää 24-bittistä mantissaa (mukaan lukien implisiittinen 1), 32-bittisen kokonaisluvun satunnaisluvun vähiten merkitseviä bittejä ei käytetä. Näitä bittejä voidaan käyttää tason valinnassa. (tässä [1] ongelman ydin on kuvattu yksityiskohtaisesti).

Taulukon luominen

Taulukko voidaan joko pitää valmiiksi laskettuna ja täydellisenä tai vain sisällyttää arvot , , ja toteutus lähdekoodiin ja laskea loput arvot satunnaislukugeneraattorin alustuksen yhteydessä (riippuen siitä, mitä meille kalliimpi: laskentaaika tai muisti). $x_{i}$ $y_{i}$ $n$ $y_1$ $A$ $f^{{-1}}(y)$

Voit löytää ja . Toista zikguratin kaikilla tasoilla. Sen pitäisi onnistua lopulta . $x_{i}=f^{-1}(y_{i})$ $y_{i+1}=y_{i}+A/x_{i}$ $n-1$ $y_{n}=f(0)$

Taulukon lopulliseen täyttöön tulee laittaa ja hyväksyen pienet epäjohdonmukaisuudet (jos ne todella tulivat pieniksi) pyöristysvirheiksi . $x_{n}=0$ $y_{n}=f(0)$

Hae ja $x_{1}$ $A$

Jos alkuarvo on (laskettu, jos ei tarkalleen, niin likimääräinen), jää vain laskea funktion loppuosan pinta-ala, jolle . Voit laskea numeerisilla integrointimenetelmillä . $x_{1}$ $t$ $x>x_{1}$

Lisäksi sieltä on mahdollista löytää , hännän osan alueelta on pohjatason alue: . $x_{1}$ $y_{1}=f(x_{1})$ $t$ $A=x_{1}y_{1}+t$

Sitten sarja ja lasketaan edellä esitetyllä tavalla. Jos jollekin , niin alkuperäinen arvo oli liian pieni, mikä johti suureen alueeseen . Jos , niin alkuperäinen arvo oli liian suuri. $y_{i}$ $x_{i}$ $y_{i}>f(0)$ $i<n$ $x_{1}$ $A$ $y_{n}<f(0)$ $x_{1}$

Yllä olevan perusteella voit käyttää yhtälöiden numeerista ratkaisua (esimerkiksi puolittamismenetelmää ) löytääksesi arvon , jonka arvo on mahdollisimman lähellä . Vaihtoehtoisesti voidaan harkita ja löytää arvoja ylimmän tason alueelle, , mahdollisimman lähellä haluttua arvoa . $x_{1}$ ${\displaystyle y_{n-1))$ $f(0)$ $x_{n-1}(f(0)-y_{n-1})$ $A$

Muistiinpanot

↑ Jurgen A. Doornik. "Parannettu Ziggurat-menetelmä normaalien satunnaisnäytteiden luomiseksi" (englanniksi) // Nuffield College, Oxford. - 2005. Arkistoitu 7. maaliskuuta 2016.

Kirjallisuus

George Marsaglia Ziggurat-menetelmä satunnaismuuttujien luomiseksi // Journal of Statistical Software . - 2000. - 7 s. - URL : verkkosivusto
Jürgen A. Doornik . Parannettu Ziggurat-menetelmä normaalien satunnaisnäytteiden luomiseen. - Nuffield College, Oxford: 2005. - 9 s. - URL: työpaikka
David B. Thomas, Philip HW Leong, Wayne Luk, John D. Villasenor . Gaussin satunnaislukugeneraattorit // ACM Computing Surveys. - 2007. - 38 s. - URL: työpaikka
Boaz Nadler . Suunnitteluvirheitä Ziggurat- ja Monty Python -menetelmien toteutuksessa (ja joitain huomautuksia Matlab randnista) // The Journal of Business. - 2006. - 16 s. - URL: työpaikka
Edrees, Hassan M.; Cheung, Brian; Sandora, McCullen; Nummey, David; Stefan, Deian . Laitteistooptimoitu Ziggurat-algoritmi nopeille Gaussin satunnaislukugeneraattoreille // 2009 kansainvälinen konferenssi uudelleenkonfiguroitavien järjestelmien ja algoritmien suunnittelusta. Las Vegas. - URL: sivusto
Marsaglia, George . Muuttujan luominen normaalijakauman hännän pohjasta // Technometrics. - 1964. - V. 6, nro 1. - C 101-102. - URL: sivusto

Linkit

Normaalin ja eksponentiaalisen tiheyden funktioiden algoritmin C-toteutus on olennaisesti kopio artikkelin koodista.
Toteutus C# -kielellä ja katsaus itse algoritmiin.
MathWorksin Ziggurat Random Normal Generator -blogit, lähettänyt Cleve Moler, 18. toukokuuta 2015.