Algoritmo ziggurat: differenze tra le versioni

Versione delle 21:28, 1 lug 2019

Versione attuale delle 15:32, 29 apr 2023

(24 versioni intermedie di 19 utenti non mostrate)

Riga 1:

{{OF|informaticaalgoritmi|lugliogiugno 2019}}

{{F|algoritmi|giugno 2019|}}

{{Correggere|argomento=informatica|data=giugno 2019}}

L<nowiki>'</nowiki>'''algoritmo ziggurat''' è un [[algoritmo]] per il campionamento numerico pseudo-casuale. Appartenente alla classe degli algoritmi di [[rejection sampling]], si basa sull'utilizzo di una sorgente di numeri casuali uniformemente distribuiti, in genere un [[Numeri pseudo-casuali|generatore di numeri pseudo-casuali]], e di tabelle precalcolate. L'algoritmo viene utilizzato per generare valori da una [[Variabile casuale#Distribuzione di probabilità|distribuzione di probabilità]] [[Funzione monotona|decrescente monotona]]. Può anche essere applicato a distribuzioni unimodali [[Funzione simmetrica|simmetriche]], come la [[distribuzione normale]]. Fu sviluppato da George Marsaglia e altri negli anni '60.

Per produrre un valore con questo algoritmo è necessaria la generazione di un valore floating point casuale, di un indice di una tabella casuale, della ricerca del valore nella tabella, di una moltiplicazione e di un confronto. In alcuni casi sono necessari più passi. In ogni caso, l'algoritmo è computazionalmente più veloce rispetto ai due metodi più utilizzati per generare numeri random normalmente distribuiti che sono il [[metodo polare di Marsaglia]] e [[Box-Muller transform]]. Tuttavia, poiché l'algoritmo di ziggurat è complesso da implementare, solitamente è utilizzato quando deve essere generata una grande quantità di numeri random.

L<nowiki>'</nowiki>'''algoritmo ziggurat'''<ref>{{Cita web|url=https://www.no-regime.com/ru-it/wiki/Ziggurat_algorithm|titolo=Algoritmo di Ziggurat - Ziggurat algorithm - www.no-regime.com|sito=www.no-regime.com|lingua=it|accesso=2022-07-02}}</ref> è un [[algoritmo]] di [[rejection sampling]] utilizzato per il campionamento numerico pseudo-casuale. È stato sviluppato negli anni '60 da [[George Marsaglia]] ed è utilizzato per generare valori con una [[Variabile casuale#Distribuzione di probabilità|distribuzione di probabilità]] [[Funzione monotona|decrescente monotona]] partendo da una sorgente di numeri casuali uniformemente distribuiti (solitamente un [[Numeri pseudo-casuali|generatore di numeri pseudo-casuali]]) e da una tabella precalcolata. Può anche essere applicato a distribuzioni unimodali [[Funzione simmetrica|simmetriche]], come la [[distribuzione normale]].

Il termine ''algoritmo ziggurat'' risale all'articolo scritto da Marsaglia e Wai Wan Tsang nel 2000; è così chiamato perché è concettualmente basato sulla copertura della distribuzione di probabilità con segmenti rettangolari impilati in ordine decrescente di dimensioni, dando come risultato una figura che assomiglia ad una [[Ziqqurat|ziggurat]].

[[File:Ziggurat_method.gif|miniatura|300x300px| L'algoritmo Ziggurat utilizzato per generare valori campione con una [[distribuzione normale]] (solo i valori positivi sono mostrati per semplicità). I punti rosa sono inizialmente numeri casuali distribuiti uniformemente. La funzione di distribuzione desiderata viene prima segmentata in aree uguali "A". Uno strato ''i'' è selezionato a caso dalla fonte uniforme a sinistra. Quindi un valore casuale dalla sorgente viene moltiplicato per la larghezza del livello scelto e il risultato viene ''x'' testato per vedere in quale regione della fenditura cade. I possibili risultati sono: 1) (sinistra, regione nera) il campione chiaramente sotto la curva e viene passato direttamente all'output, 2) (a destra, regione a strisce verticali) il valore del campione può trovarsi sotto la curva e deve essere ulteriormente testato. In tal caso, viene generato un valore ''y'' casuale all'interno del layer scelto e confrontato con ''f (x)'' . Se inferiore, il punto è sotto la curva e viene emesso il valore ''x'' . In caso contrario, il punto scelto ''x'' viene rifiutato e l'algoritmo viene riavviato dall'inizio. ]]

L'algoritmo ziggurat è più veloce rispetto ad altri metodi di generazione di numeri casuali normalmente utilizzati, come ad esempio il metodo polare di Marsaglia e la [[trasformazione di Box-Muller]]. Tuttavia, poiché questo algoritmo è anche più complesso da implementare, solitamente è utilizzato solo a fronte di una grande richiesta di numeri pseudo-casuali.

Il termine ''ziggurat'' è stato utilizzato per la prima volta in un articolo di [[George Marsaglia]] e [[Wai Wan Tsang]] nel 2000. Lo chiamarono così per via del modo in cui distribuisce la [[probabilità]]: la distribuzione ricorda la forma di una [[Ziqqurat|ziggurat]]<ref>{{Cita web|url=https://iris.univr.it/handle/11562/942488|titolo=Piramidi e ziqqurat|sito=iris.univr.it|accesso=2022-07-02}}</ref> a causa dei segmenti rettangolari impilati in ordine decrescente da cui è formata.

[[File:Ziggurat_method.gif|miniatura|300x300px| L'algoritmo Ziggurat utilizzato per generare valori campione con una [[distribuzione normale]] (solo i valori positivi sono mostrati per semplicità). I punti rosa sono inizialmente numeri casuali distribuiti uniformemente. La funzione di distribuzione desiderata viene prima segmentata in aree uguali "A". Uno strato ''i'' è selezionato a caso dalla fonte uniforme a sinistra. Quindi un valore casuale dalla sorgente viene moltiplicato per la larghezza del livello scelto e il risultato viene testato ''x'' testatovolte per vedere in quale regione della fenditura cade. I possibili risultati sono: 1) (sinistra, regione nera) il campione è chiaramente sotto la curva e viene passato direttamente all'output, 2) (a destra, regione a strisce verticali) il valore del campione può trovarsi sotto la curva e deve essere ulteriormente testato. In tal caso, viene generato un valore ''y'' casuale all'interno del layerlivello scelto e confrontato con ''f (x)'' . Se inferiore, il punto è sotto la curva e viene emesso il valore ''x'' . In caso contrario, il punto scelto ''x'' viene rifiutato e l'algoritmo viene riavviato dall'inizio. ]]

== Teoria del funzionamento ==

L'algoritmo ziggurat è unbasato algoritmosulla ditecnica del [[rejection sampling]]: genera casualmente un punto in una distribuzione leggermente più grande delladi distribuzionequella desiderata, e controlla quindi verifica se il punto generato si trova all'interno della distribuzione desiderata. Dato un punto casuale al di sotto di una curva di [[densità di probabilità]], la sua coordinata ''x'' è unvalido numeroo casuale con la distribuzione desideratameno.

Dato un punto casuale al di sotto di una curva di [[densità di probabilità]], la sua coordinata ''x'' è un numero casuale con la distribuzione desiderata.

La distribuzione scelta dall'algoritmo ziggurat è composta da ''n'' regioni di uguale area.

La distribuzione scelta dall'algoritmo ziggurat è composta da ''n'' regioni di uguale area.

Data una funzione di [[densità di probabilità]] decrescente [[Funzione monotona|monotona]] ''f'' (''x''), definita per tutti ''x'' ≥ 0, la base della ziggurat è definita come tutti i punti all'interno della distribuzione e sotto ''y''₁ = ''f'' (''x''₁). Questo consiste in una regione rettangolare da (0, 0) a (''x''₁,''y''₁), più la coda (tipicamente infinita) della distribuzione, dove ''x'' > ''x''₁ (e ''y'' < ''y''₁).

QuestoData livellouna (stratofunzione 0)di ha[[densità areadi ''A.''probabilità]] Oltredecrescente a ciò, viene aggiunto uno strato rettangolare di[[Funzione larghezzamonotona|monotona]] ''xy''₁ e altezza= ''Af'' / (''x''₁), quindidefinita conper sempretutti areai valori ''A.x'' La≥ parte0, superiorela dibase questodella livelloziggurat siè trovadefinita acome ''y''₂tutti =i [[Parte interna|punti interni]] alla distribuzione e sottostanti la retta ''y''₁ += ''Af'' / (''x''₁). eQuesta intersecaconsiste lain funzioneuna diregione densitàrettangolare inindividuata undai puntopunti (0,0) a (''x''₂₁, ''y''₂₁), più la coda (tipicamente infinita) della distribuzione, dove ''yx'' ₂ = ''f''(''x''₂₁). Questo strato include ogni punto della funzione di densità tra(e ''y'' ₁ e ''y''₂₁,). maQuesto (alivello differenzaè deldetto livellostrato base)0 includeed ancheha puntiarea comepari (''x''₁,ad ''yA.''₂) che non si trovano nella distribuzione desiderata.

Sopra di esso, viene costruito un altro strato rettangolare di larghezza ''x''₁ e altezza ''A'' / ''x''₁, così da mantenere anche per esso un'area pari ad ''A.'' La parte superiore di questo livello si trova a ''y''₂ = ''y''₁ + ''A'' / ''x''₁ e interseca la funzione di densità di probabilità in un punto (''x''₂, ''y''₂), dove ''y'' ₂ = ''f'' (''x''₂). Questo strato include ogni punto della funzione di densità di probabilità compreso tra ''y''₁ e ''y''₂, ma, a differenza del livello base, include anche punti come (''x''₁, ''y''₂) che non si trovano nella distribuzione desiderata.

Ulteriori strati vengono poi impilati. Per utilizzare una tabella precalcolata di dimensione ''n'' (256 solitamente), viene scelta ''x''₁ tale che ''x''_''n'' = 0, il che significa che il livello superiore, il livello ''n'' - 1, raggiunge esattamente il picco di distribuzione a (0, ''f'' (0)).

Ulteriori strati vengono poi impilati mantenendo costante l'area. Per utilizzare una tabella precalcolata di dimensione ''n'' (256 solitamente), viene scelta ''x''₁ tale che ''x''_''n'' = 0, il che significa che il livello superiore, il livello ''n'' - 1, raggiunge esattamente il picco di distribuzione a (0, ''f'' (0)).

Lo strato ''i'' si estende verticalmente da ''y''_''i'' a ''y''_''i''+1 e può essere diviso orizzontalmente in due regioni: la porzione (generalmente più grande) da 0 a ''x''_''i''+1 che è interamente contenuta nella distribuzione desiderata e la porzione (piccola) da ''x''_''i''+1 a ''x''_''i'', che è solo parzialmente contenuta.

LoGeneralizzando, lo strato ''i''-esimo si estende verticalmente da ''y''_''i'' a ''y''_''i''+1 e può essere diviso orizzontalmente in due regioni: la porzione (generalmente più grande) da 0 a ''x''_''i''+1 che è interamente contenuta nella distribuzione desiderata, e la porzione (generalmente più piccola) da ''x''_''i''+1 a ''x''_''i'', che è solo parzialmente contenuta. nella distribuzione.

Ignorando per un momento il problema del livello 0, e date le variabili casuali uniformi ''U''₀ e ''U''₁ &nbsp;∈ [0,1), l'algoritmo ziggurat opera in questi passi:

Ignorando per un momento il problema del livello 0, e date le [[Variabile casuale|variabili casuali]] uniformi ''U''₀ e ''U''₁ &nbsp;∈ [0,1)], l'algoritmo ziggurat opera in questi passi:

# Scegli un livello casuale 0 ≤ ''i'' < ''n'' .

# Sia ''x'' = ''U''₀''x''_''i'' .

# Se ''x'' &#x3C;< ''x''_''i''+1, restituisci ''x''.

# Sia ''y'' = ''y''_''i'' + ''U''₁(''y''_{''i'' +1} - ''y''_''i'' ).

# Calcola ''f'' (''x''). Se ''y'' &#x3C;< ''f'' (''x''), restituisci ''x''.

# Altrimenti, scegli nuovi numeri casuali e torna al passaggio 1.

Il passaggio 1 equivale alla scelta di una coordinata ''y''. Il passaggio 3 verifica se la coordinata ''x'' è all'interno della funzione di densità desiderata. In caso contrario, il passo 4 sceglie una coordinata ''y'' e il passo 5 esegue il test di accettazione.

Si noti che per il livello superiore ''n'' - 1 questo test fallisce sempre, perché ''x'' _''n'' = 0.

=== Ottimizzazioni ===

L'algoritmo può essere eseguito in modo efficiente utilizzando tabelle precalcolate per ''x''_''i'' e ''y''_''i'' = ''f'' (''x''_''i''), ma esistonosi alcunepossono migliorieapportare alcuni miglioramenti per renderlo ancora più veloce:

* Nulla nellL'algoritmo ziggurat dipendenon ha niente che dipenda dalla normalizzazione della funzione di distribuzione di probabilità (integrale sotto la curva uguale a 1), quindi la rimozione delle [[Normalizzazione (matematica)|costanti di normalizzazione]] può accelerare il calcolo di ''f'' (''x'').

* Invece di confrontare ''U''₀''x_i'' con ''x''_''i''+1 al punto 3, è possibile precomputareprecalcolare ''x''_''i''+1 / ''x''_''i'' e confrontarlo con ''U''₀ direttamente. Se ''U'' ₀ è un generatore di numeri casuali intero, questi limiti possono essere premoltiplicatimoltiplicati diper 2 ³² (o 2 ³¹, a seconda dei casi) in modo da poter utilizzare un confronto ditra numeri interi.

* Quando si generano valori in virgola mobile a precisione singola (a standard [[IEEE 754]]), che hanno solo una mantissa a 24 bit (incluso l'iniziale implicita 1), i bit meno significativi di un numero casuale intero a [[32 bit]] non vengono utilizzati. Questi bit possono essere usati per selezionare il numero di livelli.

== Note ==

<references />

== Altri progetti ==

{{interprogetto}}

== Collegamenti esterni ==

* Nulla nell'algoritmo ziggurat dipende dalla normalizzazione della funzione di distribuzione di probabilità (integrale sotto la curva uguale a 1) quindi la rimozione delle [[Normalizzazione (matematica)|costanti di normalizzazione]] può accelerare il calcolo di ''f'' (''x'').

* Invece di confrontare ''U''₀''x_i'' con ''x''_''i''+1 al punto 3, è possibile precomputare ''x''_''i''+1 / ''x''_''i'' e confrontarlo con ''U''₀ direttamente. Se ''U'' ₀ è un generatore di numeri casuali intero, questi limiti possono essere premoltiplicati di 2 ³² (o 2 ³¹, a seconda dei casi) in modo da poter utilizzare un confronto di numeri interi.

* Quando si generano valori in virgola mobile a precisione singola [[IEEE 754]], che hanno solo una mantissa a 24 bit (incluso l'iniziale implicita 1), i bit meno significativi di un numero casuale intero a 32 bit non vengono utilizzati. Questi bit possono essere usati per selezionare il numero di livelli.

* [https://www.jstatsoft.org/article/view/v005i08 The Ziggurat Method for Generating Random Variables]

{{controllo d'autorità}}

{{portale|matematica}}