Rejection sampling: differenze tra le versioni

Versione delle 13:51, 2 lug 2019

Versione attuale delle 10:31, 16 mar 2025

(14 versioni intermedie di 11 utenti non mostrate)

Riga 1:

In [[analisi |numerica]] e in [[statistica computazionale]], '''rejection sampling''' è una tecnica di base utilizzata per generare osservazioni da una [[Variabile casuale#Distribuzione di probabilità|distribuzione]] . È anche comunemente chiamato il '''metodo di acceptantacceptance-rejection''' o "algoritmo di '''accept-rejection'''".

Rejection sampling si basa sul fatto che, per campionare una [[variabile casuale]] in una dimensione, si può eseguire un campionamento uniformemente casuale del grafico cartesiano bidimensionale e mantenere i campioni nella '''regione''' sotto il grafico della sua funzione di densità. <ref>{{Cita libro|autore=Casella|nome=George|autore2=Robert|nome2=Christian P.|nome3=Martin T.|autore3=Wells|titolo=Generalized Accept-Reject sampling schemes|url=https://archive.org/details/bub_gb_wnXtK_LRbO0C|anno=2004|editore=Institute of Mathematical Statistics|pp=342–347[https://archive.org/details/bub_gb_wnXtK_LRbO0C/page/n360 342]–347|ISBN=9780940600614|DOI=10.1214/lnms/1196285403}}</ref> <ref name="radford03">{{Cita pubblicazione|autore=Neal|nome=Radford M.|anno=2003|titolo=Slice Sampling|url=https://archive.org/details/sim_annals-of-statistics_2003-06_31_3/page/705|rivista=[[Annals of Statistics]]|volume=31|numero=3|pp=705–767705-767|doi=10.1214/aos/1056562461}}</ref> <ref name="bishop06">{{Cita libro|autore=Bishop|nome=Christopher|titolo=Pattern Recognition and Machine Learning|url=https://archive.org/details/patternrecogniti0000bish|anno=2006|editore=[[Springer Science+Business Media|Springer]]|capitolo=11.4: Slice sampling|ISBN=978-0-387-31073-2}}</ref> Si noti che questa proprietà può essere estesa a funzioni in N-dimensioni.

== Descrizione ==

Per visualizzare la motivazione alla base del rejection sampling, immagina di rappresentare graficamente la [[funzione di densità]] di una variabile casuale su una grande tavola rettangolare e di lanciare delle freccette. Supponiamo che le freccette siano distribuite uniformemente attorno al tabellone. Ora rimuovi tutte le freccette che si trovano al di fuori dell'area sotto la curva. I dardi rimanenti saranno distribuiti uniformemente all'interno dell'area sotto la curva e le posizioni lungo l'asse x di queste frecce saranno distribuite in base alla densità della variabile casuale. Questo perché c'è più spazio per le freccette per atterrare dove la curva è più alta e quindi la densità di probabilità è maggiore.

L'esempio appena descritto è una particolare forma di rejection sampling in cui la [[proposal distribution]] è uniforme (quindi il suo grafico è un rettangolo). La forma generale di rejection sampling presuppone che la tavola dell'esempio precedente non sia necessariamente rettangolare ma sia modellata secondo una certa distribuzione dalla quale il campionamento risulta facile (ad esempio, utilizzando il [[Metodo dell'inversione|campionamento di inversione]]) e che sia almeno almeno alta come il punto più alto della distribuzione dalla quale vogliamo campionare. Se ciò non è vero, ci potrebbero essere parti dell'area che vogliamo campionare che non potranno essere raggiunte. Rejection sampling funziona come segue:

# Campiona un punto sull'asse x dalla [[proposal distribution]].

# Traccia una linea verticale in questa posizione x, fino alla curva della [[proposal distribution]].

# Campiona uniformemente lungo questa linea da 0 al massimo della [[funzione di densità di probabilità]]. Se il valore campionato è maggiore del valore della distribuzione desiderata su questa linea verticale, tornare al punto 1.

Questo algoritmo può essere utilizzato per campionare dall'area sotto qualsiasi curva, indipendentemente dal fatto che l'integrale della funzione abbia valore 1. In effetti, il ridimensionamento di una funzione con una costante non ha alcun effetto sulle posizioni x campionate. Pertanto, l'algoritmo può essere utilizzato per campionare da una distribuzione la cui [[Normalizzazione (matematica)|costante di normalizzazione]] è sconosciuta, che è comune nella [[statistica computazionale]] .

Come semplice esempio geometrico, supponiamo di voler generare un punto casuale all'interno del cerchio unitario. Il primo step è generare un punto candidato (<math>(x,y)</math><math>x,y </math>) dove <math>x </math> <math>x </math>e <math>y </math> <math>y </math>sono indipendenti e uniformemente distribuiti tra &#x2212; -1 e 1. Se <math>x^2+y^2 \leq 1 </math> allora il punto è all'interno del cerchio unitario ed è accettato, altrimenti è rifiutato e viene generato un nuovo candidato.

Un esempio più complicato utilizzato per generare in modo efficiente [[Numeri pseudo-casuali|numeri pseudocasuali]] [[Distribuzione normale|normalmente distribuiti]] è l'[[Algoritmo Ziggurat|algoritmo ziggurat]].

== Algoritmo ==

L'algoritmo di rejection semplingsampling genera valori di campionamento da una distribuzione target <math>X </math> con [[funzione di densità di probabilità]] arbitraria <math>f(x) </math> utilizzando una [[proposal distribution]] <math>Y </math> con densità di probabilità <math>g(x) </math>.

L'algoritmo (usato da [[John von Neumann]] e risalente a Buffon e al [[Ago di Buffon|suo ago]]) per ottenere un campione dalla distribuzione <math>X </math> con densità <math>f(x)</math> utilizzando campioni dalla distribuzione <math>Y </math> con densità <math>g(x) </math> è il seguente:

* Campiona <math display="inline">y</math> dalla distribuzione <math>Y </math>e un campione <math display="inline">u </math> a partire da <math>\mathrm{Unif}(0,1)</math> (distribuzione uniforme sull'intervallo <math>[0,1]</math>).

* Controlla se <math display="inline">u<f(y)/Mg(y) </math> con <math>1 < M < \infty</math> sul [[supporto (matematica)|supporto]] di <math>X </math>:

** se ciò vale, accetta <math>y </math> come un campione tratto da <math>f(x)</math>;

** in caso contrario, rifiuta il valore di <math>y </math> e torna allo step precedente (fase di campionamento).

== Svantaggi ==

Il probelmaproblema principale dell'algoritmo di rejection sampling è che può generare un numero molto elevato di campioni che poi vengnovengono scartati, soprattutto nel caso in cui la funzione campionata è concertataconcentrata in una certa regione. Per molte distribuzioni, questo probelmaproblema può essere risolto utilizzando una versione adattiva dell'algoritmo (seevedi [[Rejection sampling|adaptive rejection sampling]]). In altre dimensioni, è necessario utilizzare approcci differenti, come per esempio metodi [[Markov Chain Monte Carlo]], tra i quali [[Algoritmo di Metropolis-Hastings|Metropolis sampling]] o [[Campionamento di Gibbs|Gibbs sampling]].

== Note ==

<references/>

== Voci correlate ==

*[[Statistica computazionale]]

*[[Analisi numerica]]

== Note ==

<references/>

[[Categoria:Analisi numerica]]