Avvisningsprøve - Rejection sampling

I numerisk analyse og beregningsstatistikk er avvisningsprøvetaking en grunnleggende teknikk som brukes til å generere observasjoner fra en distribusjon . Det kalles også vanligvis aksept-avvisning-metoden eller "aksepter-avvis algoritme" og er en type eksakt simuleringsmetode. Metoden fungerer for enhver distribusjon med en tetthet . ${\ displaystyle \ mathbb {R} ^{m}}$

Avvisningsprøvetaking er basert på observasjonen at for å prøve en tilfeldig variabel i en dimensjon, kan man utføre en jevnt tilfeldig prøvetaking av den todimensjonale kartesiske grafen, og beholde prøvene i regionen under grafen for dens tetthetsfunksjon. Vær oppmerksom på at denne egenskapen kan utvides til N -dimensjonsfunksjoner.

Beskrivelse

For å visualisere motivasjonen bak avvisningsprøvetaking, forestill deg å tegne tetthetsfunksjonen til en tilfeldig variabel på et stort rektangulært brett og kaste dart mot den. Anta at dartene er jevnt fordelt rundt brettet. Fjern nå alle pilene som er utenfor området under kurven. De resterende pilene vil bli fordelt jevnt innenfor området under kurven, og x-posisjonene til disse pilene vil bli fordelt i henhold til den tilfeldige variablens tetthet. Dette er fordi det er mest rom for dartene å lande der kurven er høyest og dermed er sannsynlighetstettheten størst.

Visualiseringen som nettopp beskrevet tilsvarer en bestemt form for avvisningsprøvetaking der "forslagsfordelingen" er jevn (derav grafen er et rektangel). Den generelle formen for avvisningsprøvetaking forutsetter at brettet ikke nødvendigvis er rektangulært, men er formet i henhold til tettheten til noen forslagsdistribusjon som vi vet hvordan vi skal prøve fra (for eksempel ved å bruke inversjonsprøvetaking ), og som er minst like høy ved hver punkt som fordelingen vi vil prøve fra, slik at førstnevnte omslutter sistnevnte helt. (Ellers ville det være deler av det buede området vi vil prøve fra som aldri kunne nås.)

Avvisningsprøver fungerer som følger:

Prøv et punkt på x-aksen fra forslagets fordeling.
Tegn en vertikal linje på denne x-posisjonen, opp til maksimal y-verdi av sannsynlighetstetthetsfunksjonen til forslagsfordelingen.
Prøve jevnt langs denne linjen fra 0 til maksimum for sannsynlighetstetthetsfunksjonen. Hvis den samplede verdien er større enn verdien av ønsket fordeling på denne vertikale linjen, avviser du x-verdien og går tilbake til trinn 1; ellers er x-verdien en prøve fra ønsket fordeling.

Denne algoritmen kan brukes til å prøve fra området under en hvilken som helst kurve, uavhengig av om funksjonen integreres til 1. Faktisk har skalering av en funksjon med en konstant ingen effekt på de samplede x-posisjonene. Dermed kan algoritmen brukes til å prøve fra en fordeling hvis normaliseringskonstant er ukjent, noe som er vanlig i beregningsstatistikk .

Teori

Avvisningsprøvetakingsmetoden genererer samplingsverdier fra en målfordeling med vilkårlig sannsynlighetstetthetsfunksjon ved å bruke en forslagsfordeling med sannsynlighetstetthet . Tanken er at man kan generere en prøveverdi fra ved i stedet å sampler fra og godta prøven fra med sannsynlighet , gjenta trekningene fra til en verdi er akseptert. her er en konstant, endelig begrenset til sannsynlighetsforholdet , tilfredsstillende over støtten til ; med andre ord, M må tilfredsstille for alle verdier av . Vær oppmerksom på at dette krever at støtten til må omfatte støtte fra - med andre ord, når som helst . ${\ displaystyle X}$ ${\ displaystyle f (x)}$ ${\ displaystyle Y}$ ${\ displaystyle g (x)}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Y}$ ${\ displaystyle f (x)/(Mg (x))}$ ${\ displaystyle Y}$ ${\ displaystyle M}$ ${\ displaystyle f (x)/g (x)}$ ${\ displaystyle 1 <M <\ infty}$ ${\ displaystyle X}$ ${\ displaystyle f (x) \ leq Mg (x)}$ ${\ displaystyle x}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle g (x)> 0}$ ${\ displaystyle f (x)> 0}$

Valideringen av denne metoden er konvoluttprinsippet: ved simulering av paret produserer man en jevn simulering over subgrafen til . Godta bare par slik at det produseres par jevnt fordelt over undergrafen til og dermed marginalt en simulering fra ${\ textstyle (x, v = u \ cdot Mg (x))}$ ${\ textstyle Mg (x)}$ ${\ textstyle u <f (x)/(Mg (x))}$ ${\ displaystyle (x, v)}$ ${\ displaystyle f (x)}$ ${\ displaystyle f (x).}$

Dette betyr at med nok replikater genererer algoritmen en prøve fra ønsket fordeling . Det er en rekke utvidelser til denne algoritmen, for eksempel Metropolis -algoritmen . ${\ displaystyle f (x)}$

Denne metoden vedrører det generelle feltet for Monte Carlo -teknikker, inkludert Markov -kjede Monte Carlo -algoritmer som også bruker en proxy -distribusjon for å oppnå simulering fra målfordelingen . Det danner grunnlaget for algoritmer som Metropolis -algoritmen . ${\ displaystyle f (x)}$

Den ubetingede aksept -sannsynligheten er andelen foreslåtte prøver som godtas, dvs.

{\ displaystyle {\ begynne {justert} \ mathbb {P} \ venstre (U \ leq {\ frac {f (Y)} {Mg (Y)}} \ høyre) & = \ operatorname {E} \ mathbf {1 } _ {\ venstre [U \ leq {\ frac {f (Y)} {Mg (Y)}} \ høyre]} \\ [6pt] & = E \ venstre [\ operatorname {E} [\ mathbf {1 } _ {\ left [U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right]} | Y] \ right] & ({\ text {by tower property}}) \\ [ 6pt] & = \ operatorname {E} \ left [\ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} {\ biggr |} Y \ right) \ right ] \\ [6pt] & = E \ venstre [{\ frac {f (Y)} {Mg (Y)}} \ høyre] & ({\ tekst {fordi}} \ Pr (U \ leq u) = u , {\ text {when}} U {\ text {er uniform på}} (0,1)) \\ [6pt] & = \ int \ limit _ {y: g (y)> 0} {\ frac { f (y)} {Mg (y)}} g (y) \, dy \\ [6pt] & = {\ frac {1} {M}} \ int \ limit _ {y: g (y)> 0 } f (y) \, dy \\ [6pt] & = {\ frac {1} {M}} & ({\ text {siden støtte for}} Y {\ text {inkluderer støtte for}} X) \ end {justert}}}

hvor , og verdien for hver gang genereres under tetthetsfunksjonen til forslagsfordelingen .

{\ displaystyle U \ sim \ mathrm {Unif} (0,1)}

{\ displaystyle y}

{\ displaystyle g (\ cdot)}

{\ displaystyle Y}

Antall prøver som kreves fra for å oppnå en akseptert verdi følger således en geometrisk fordeling med sannsynlighet , som har gjennomsnitt . Intuitivt er det forventede antallet iterasjoner som er nødvendig, som et mål på algoritmens beregningskompleksitet. ${\ displaystyle Y}$ ${\ displaystyle 1/M}$ ${\ displaystyle M}$ ${\ displaystyle M}$

Skriv om ligningen ovenfor,

{\ displaystyle M = {\ frac {1} {\ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right)}}}

Vær oppmerksom på at på grunn av formelen ovenfor, er det en sannsynlighet som bare kan ta verdier i intervallet . Når blir valgt nærmere en, er den ubetingede aksept -sannsynligheten høyere jo mindre forholdet varierer, siden er den øvre grensen for sannsynlighetsforholdet . I praksis foretrekkes en verdi på nærmere 1, ettersom det innebærer færre avviste prøver i gjennomsnitt og dermed færre iterasjoner av algoritmen. I denne forstand foretrekker man å ha så liten som mulig (mens den fortsatt er tilfredsstillende , noe som antyder at den generelt bør ligne på en eller annen måte. Vær imidlertid oppmerksom på at den ikke kan være lik 1: slikt vil antyde at det vil si at mål- og forslagfordelinger er faktisk den samme fordelingen.

{\ textstyle 1 \ leq M <\ infty}

{\ textstyle \ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right)}

{\ displaystyle [0,1]}

{\ displaystyle M}

{\ displaystyle M}

{\ textstyle f (x)/g (x)}

{\ displaystyle M}

{\ displaystyle M}

{\ displaystyle f (x) \ leq Mg (x)}

{\ displaystyle g (x)}

{\ displaystyle f (x)}

{\ displaystyle M}

{\ displaystyle f (x) = g (x)}

Avvisningsprøvetaking brukes oftest i tilfeller der formen for gjør prøvetaking vanskelig. En enkelt iterasjon av avvisningsalgoritmen krever prøvetaking fra forslagsfordelingen, tegning fra en jevn fordeling og evaluering av uttrykket. Avvisningsprøvetaking er dermed mer effektiv enn noen annen metode når M ganger kostnaden for disse operasjonene - som er den forventede kostnaden for å få en prøve med avvisningsprøve - er lavere enn kostnaden for å få en prøve ved hjelp av den andre metoden. ${\ displaystyle f (x)}$ ${\ displaystyle f (x)/(Mg (x))}$

Algoritme

Algoritmen (brukt av John von Neumann og datert tilbake til Buffon og hans nål ) for å få en prøve fra distribusjon med tetthet ved hjelp av prøver fra distribusjon med tetthet er som følger: ${\ displaystyle X}$ ${\ displaystyle f}$ ${\ displaystyle Y}$ ${\ displaystyle g}$

Skaff en prøve fra distribusjonen og en prøve fra (den jevne fordelingen over enhetsintervallet). ${\ displaystyle y}$ ${\ displaystyle Y}$ ${\ displaystyle u}$ ${\ displaystyle \ mathrm {Unif} (0,1)}$
Sjekk om ikke . ${\ textstyle u <f (y)/Mg (y)}$ ${\ textstyle u <f (y)/Mg (y)}$
- Hvis dette holder, godta som en prøve trukket fra ; ${\ displaystyle y}$ ${\ displaystyle f}$
- hvis ikke, avvis verdien av og gå tilbake til prøvetakingstrinnet. ${\ displaystyle y}$

Algoritmen vil ta et gjennomsnitt av iterasjoner for å få en prøve. ${\ displaystyle M}$

Fordeler fremfor prøvetaking ved bruk av naive metoder

Avvisningsprøving kan være langt mer effektiv sammenlignet med de naive metodene i noen situasjoner. For eksempel gitt et problem som prøvetaking betinget av gitt sett , dvs. noen ganger enkelt kan simuleres ved hjelp av naive metoder (f.eks. Ved invers transform -sampling ): ${\ textstyle X \ sim F (\ cdot)}$ ${\ displaystyle X}$ ${\ displaystyle A}$ ${\ textstyle X | X \ i A}$ ${\ textstyle X}$

Prøv uavhengig, og la de tilfredsstillende ${\ textstyle X \ sim F (\ cdot)}$ ${\ displaystyle \ {n \ geq 1: X_ {n} \ i A \}}$
Produksjon: ${\ displaystyle \ {X_ {1}, X_ {2}, ..., X_ {N}: X_ {i} \ i A, i = 1, ..., N \}}$

Problemet er at denne prøvetakingen kan være vanskelig og ineffektiv, hvis . Det forventede antallet iterasjoner vil være , som kan være nær uendelig. Selv når du bruker prøvetakingsmetoden for avvisning, er det dessuten alltid vanskelig å optimalisere grensen for sannsynlighetsforholdet. Oftere enn ikke er den stor og avvisningsraten er høy, algoritmen kan være svært ineffektiv. Den naturlige eksponentielle familien (hvis den eksisterer), også kjent som eksponentiell vipping, gir en klasse med forslagsfordelinger som kan senke beregningskompleksiteten, verdien av og fremskynde beregningene (se eksempler: arbeide med naturlige eksponentielle familier). ${\ textstyle \ mathbb {P} (X \ in A) \ ca 0}$ ${\ displaystyle {\ frac {1} {\ mathbb {P} (X \ in A)}}}$ ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle M}$

Eksempler: arbeid med naturlige eksponentielle familier

Gitt en tilfeldig variabel , er målfordelingen. Anta for enkelheten at tetthetsfunksjonen eksplisitt kan skrives som . Velg forslaget som ${\ displaystyle X \ sim F (\ cdot)}$ ${\ displaystyle F (x) = \ mathbb {P} (X \ leq x)}$ ${\ displaystyle f (x)}$

{\ displaystyle {\ begin {align} F _ {\ theta} (x) & = \ mathbb {E} \ left [\ exp (\ theta X- \ psi (\ theta)) \ mathbb {I} (X \ leq x) \ right] \\ & = \ int _ {-\ infty}^{x} e^{\ theta y- \ psi (\ theta)} f (y) dy \\ g _ {\ theta} (x) & = F '_ {\ theta} (x) = e^{\ theta x- \ psi (\ theta)} f (x) \ end {justert}}}

hvor og . Det er tydelig at den er fra en naturlig eksponentiell familie . Videre er sannsynlighetsforholdet

{\ displaystyle \ psi (\ theta) = \ log \ left (\ mathbb {E} \ exp (\ theta X) \ right)}

{\ displaystyle \ Theta = \ {\ theta: \ psi (\ theta) <\ infty \}}

{\ displaystyle \ {F _ {\ theta} (\ cdot) \} _ {\ theta \ in \ Theta}}

{\ displaystyle Z (x) = {\ frac {f (x)} {g _ {\ theta} (x)}} = {\ frac {f (x)} {e^{\ theta x- \ psi (\ theta)} f (x)}} = e^{-\ theta x+\ psi (\ theta)}}

Merk at det innebærer at det faktisk er en logg- øyeblikksgenereringsfunksjon , det vil si . Og det er lett å utlede loggmomentgenereringsfunksjonen til forslaget og derfor forslagets øyeblikk.

{\ displaystyle \ psi (\ theta) <\ infty}

{\ displaystyle \ psi (\ theta) = \ log \ mathbb {E} {\ exp (tX)} | _ {t = \ theta} = \ log M_ {X} (t) | _ {t = \ theta} }

{\ displaystyle {\ begynne {justert} \ psi _ {\ theta} (\ eta) & = \ log \ left (\ mathbb {E} _ {\ theta} \ exp (\ eta X) \ right) = \ psi (\ theta +\ eta)-\ psi (\ theta) <\ infty \\\ mathbb {E} _ {\ theta} (X) & = \ left. {\ frac {\ partiell \ psi _ {\ theta} (\ eta)} {\ partiell \ eta}} \ høyre | _ {\ eta = 0} \\\ mathrm {Var} _ {\ theta} (X) & = \ venstre. {\ frac {\ delvis ^{ 2} \ psi _ {\ theta} (\ eta)} {\ partiell ^{2} \ eta}} \ høyre | _ {\ eta = 0} \ ende {justert}}}

Som et enkelt eksempel, anta etter , med . Målet er å prøve , . Analysen går som følger.

{\ displaystyle F (\ cdot)}

{\ displaystyle X \ sim \ mathrm {N} (\ mu, \ sigma ^{2})}

{\ textstyle \ psi (\ theta) = \ theta \ mu +{\ frac {\ sigma ^{2} \ theta ^{2}} {2}}}

{\ displaystyle X | X \ in \ left [b, \ infty \ right]}

{\ displaystyle b> \ mu}

Velg formen på forslagsfordelingen , med loggmomentgenererende funksjon som , noe som videre innebærer at det er en normalfordeling . ${\ displaystyle F _ {\ theta} (\ cdot)}$ ${\ textstyle \ psi _ {\ theta} (\ eta) = \ psi (\ theta +\ eta)-\ psi (\ eta) = \ eta (\ mu +\ theta \ sigma ^{2}) +{\ frac {\ sigma ^{2} \ eta ^{2}} {2}}}$ ${\ displaystyle \ mathrm {N} (\ mu +\ theta \ sigma ^{2}, \ sigma ^{2})}$
Bestem godt valgt for forslaget distribusjon. I dette oppsettet er den intuitive måten å velge å sette , det vil si ${\ displaystyle \ theta ^{*}}$ ${\ displaystyle \ theta ^{*}}$ ${\ displaystyle \ mathbb {E} _ {\ theta} (X) = \ mu +\ theta \ sigma ^{2} = b}$ ${\ displaystyle \ theta ^{*} = {\ frac {b- \ mu} {\ sigma ^{2}}}}$
Skriv eksplisitt ut målet, forslaget og sannsynlighetsforholdet ${\ displaystyle {\ begynne {justert} f_ {X | X \ geq b} (x) & = {\ frac {f (x) \ mathbb {I} (x \ geq b)} {\ mathbb {P} ( x \ geq b)}} \\ g _ {\ theta ^{*}} (x) & = f (x) \ exp (\ theta ^{*} x- \ psi (\ theta ^{*})) \ \ Z (x) & = {\ frac {f_ {X | X \ geq b} (x)} {g _ {\ theta ^{*}} (x)}} = {\ frac {\ exp (-\ theta ^{*} x+\ psi (\ theta ^{*})) \ mathbb {I} (x \ geq b)} {\ mathbb {P} (x \ geq b)}} \ end {justert}}}$
Utled bundet til sannsynlighetsforholdet , som er en avtagende funksjon for dermed ${\ displaystyle M}$ ${\ displaystyle z (x)}$ ${\ displaystyle x \ in [b, \ infty]}$ ${\ displaystyle M = Z (b) = {\ frac {\ exp (-\ theta ^{*} b+\ psi (\ theta ^{*}))} {\ mathbb {P} (X \ geq b)} } = {\ frac {\ exp \ left (-{\ frac {(b- \ mu) ^{2}} {2 \ sigma ^{2}}} \ right)} {\ mathbb {P} (X \ geq b)}} = {\ frac {\ exp \ left (-{\ frac {(b- \ mu) ^{2}} {2 \ sigma ^{2}}} \ right)} {\ mathbb {P } \ venstre (\ mathrm {N} (0,1) \ geq {\ frac {b- \ mu} {\ sigma}} \ høyre)}}}$
Kriterium for prøvetaking av avslag: for , if ${\ displaystyle U \ sim \ mathrm {Unif} (0,1)}$ ${\ displaystyle U \ leq {\ frac {Z (x)} {M}} = e ^{-\ theta ^{*} (xb)} \ mathbb {I} (x \ geq b)}$ holder, aksepterer verdien av ; hvis ikke, fortsett prøvetaking av nytt og nytt inntil det er godtatt. ${\ displaystyle X}$ ${\ textstyle X \ sim _ {iid} \ mathrm {N} (\ mu +\ theta ^{*} \ sigma ^{2}, \ sigma ^{2})}$ ${\ textstyle U \ sim \ mathrm {Unif} (0,1)}$

For eksemplet ovenfor, som måling av effektiviteten, er det forventede antallet iterasjoner den NEF-baserte avvisningsmetoden for prøvetaking av rekkefølge b, det vil si , mens under den naive metoden er det forventede antallet iterasjoner , som er langt mer ineffektiv. ${\ displaystyle M (b) = O (b)}$ ${\ textstyle {\ frac {1} {\ mathbb {P} (X \ geq b)}} = O (b \ cdot e^{\ frac {(b- \ mu)^{2}} {2 \ sigma ^{2}}})}}$

Generelt løser eksponentiell vipping, en parametrisk klasse med forslagsdistribusjon, optimaliseringsproblemene enkelt, med sine nyttige egenskaper som direkte karakteriserer fordelingen av forslaget. For denne typen problemer, for å simulere betinget på , blant klassen med enkle distribusjoner, er trikset å bruke NEF -er, noe som bidrar til å få litt kontroll over kompleksiteten og øke hastigheten på beregningen betraktelig. Det er faktisk dype matematiske grunner for bruk av NEF. ${\ displaystyle X}$ ${\ displaystyle X \ i A}$

Ulemper

Avvisningsprøvetaking kan føre til at mange uønskede prøver tas hvis funksjonen som samples er svært konsentrert i et bestemt område, for eksempel en funksjon som har en pigg på et eller annet sted. For mange distribusjoner kan dette problemet løses ved hjelp av en adaptiv forlengelse (se adaptiv avvisningsprøvetaking ), eller med en passende endring av variabler med metoden for forholdet mellom uniformer . I tillegg, etter hvert som dimensjonene på problemet blir større, har forholdet mellom det innebygde volumet og "hjørnene" av innebyggingsvolumet en tendens til å være null, og dermed kan mange avslag finne sted før en nyttig prøve genereres, og dermed lage algoritmen ineffektiv og upraktisk. Se dimensjonalitetens forbannelse . I høye dimensjoner er det nødvendig å bruke en annen tilnærming, typisk en Markov -kjede Monte Carlo -metode som Metropolis -prøvetaking eller Gibbs -prøvetaking . (Imidlertid kan Gibbs-prøvetaking, som bryter ned et flerdimensjonalt prøvetakingsproblem til en serie lavdimensjonale prøver, bruke avvisningsprøvetaking som et av trinnene.)

Adaptiv avvisningsprøve

For mange distribusjoner er det vanskelig å finne en forslagsdistribusjon som inkluderer den gitte fordelingen uten mye bortkastet plass. En forlengelse av avvisningsprøvetaking som kan brukes til å overvinne denne vanskeligheten og effektivt prøve fra et bredt spekter av distribusjoner (forutsatt at de har log-konkav tetthetsfunksjoner, noe som faktisk er tilfelle for de fleste vanlige fordelingene-selv de hvis tetthet funksjoner er ikke konkav selv!) er kjent som adaptiv avvisningssampling (ARS) .

Det er tre grunnleggende ideer til denne teknikken som til slutt ble introdusert av Gilks i 1992:

Hvis det hjelper, kan du definere konvoluttfordelingen i loggområdet (f.eks. Logg-sannsynlighet eller loggtetthet) i stedet. Det vil si jobbe med i stedet for direkte. ${\ displaystyle h \ left (x \ right) = \ log g \ left (x \ right)}$ ${\ displaystyle h \ left (x \ right) = \ log g \ left (x \ right)}$ ${\ displaystyle g \ venstre (x \ høyre)}$ $g \ venstre (x \ høyre)$
- Ofte har distribusjoner som har algebraisk rotete tetthetsfunksjoner rimelig enklere loggtetthetsfunksjoner (dvs. når det er rotete, kan være lettere å jobbe med eller i det minste nærmere stykkevis lineær). ${\ displaystyle f \ venstre (x \ høyre)}$ ${\ displaystyle \ log f \ left (x \ right)}$
I stedet for en ensartet konvoluttetthetsfunksjon, bruk en stykkevis lineær tetthetsfunksjon som konvolutten din i stedet.
- Hver gang du må avvise en prøve, kan du bruke verdien av den du evaluerte, for å forbedre den tilnærmede tilnærmingen i stykker . Dette reduserer derfor sjansen for at ditt neste forsøk vil bli avvist. Asymptotisk bør sannsynligheten for å måtte avvise prøven konvergere til null, og i praksis ofte veldig raskt. ${\ displaystyle f \ venstre (x \ høyre)}$ ${\ displaystyle h \ left (x \ right)}$
- Som foreslått, hver gang vi velger et punkt som blir avvist, strammer vi konvolutten med et annet linjesegment som tangerer kurven på punktet med samme x-koordinat som det valgte punktet.
- En stykkevis lineær modell av forslagsloggfordelingen resulterer i et sett med stykkevis eksponentielle fordelinger (dvs. segmenter av en eller flere eksponensielle fordelinger, festet ende til ende). Eksponensielle fordelinger er veloppdragen og godt forstått. Logaritmen til en eksponentiell fordeling er en rett linje, og derfor innebærer denne metoden i hovedsak å omslutte logaritmen til tettheten i en serie linjesegmenter. Dette er kilden til den logk-konkave begrensningen: hvis en fordeling er log-konkav, er dens logaritme konkav (formet som en opp-ned-U), noe som betyr at et linjesegment som er tangent til kurven alltid vil passere over kurven.
- Hvis du ikke jobber i tømmerplass, kan en stykkevis lineær tetthetsfunksjon også samples via trekantfordelinger
Vi kan dra enda mer fordel av kravet til (logg) konkavitet, for å potensielt unngå kostnadene ved å evaluere når prøven din

blir akseptert.

{\ displaystyle f \ venstre (x \ høyre)}

Akkurat som vi kan konstruere en stykkevis lineær øvre grense ("konvolutten" -funksjonen) ved hjelp av verdiene vi måtte evaluere i den nåværende avvisningskjeden, kan vi også konstruere en stykkevis lineær nedre grense ("klem" -funksjonen) ved hjelp av også disse verdiene. ${\ displaystyle h \ left (x \ right)}$
Før vi evaluerer (den potensielt dyre) for å se om prøven din vil bli akseptert, kan vi

allerede vite om den vil bli akseptert ved å sammenligne den (ideelt sett billigere) (eller i dette tilfellet) klemmefunksjonen som er tilgjengelig.

{\ displaystyle f \ venstre (x \ høyre)}

{\ displaystyle g_ {l} \ venstre (x \ høyre)}

{\ displaystyle h_ {l} \ venstre (x \ høyre)}

Dette klemtrinnet er valgfritt, selv når det er foreslått av Gilks. I beste fall sparer det deg for bare en ekstra evaluering av din (rotete og/eller dyre) måltetthet. Imidlertid kan dette antagelig for spesielt dyre tetthetsfunksjoner (og forutsatt at konvergensen av avvisningsfrekvensen går mot null) gjøre en betydelig forskjell i den ultimate kjøretiden.

Metoden innebærer i hovedsak å bestemme en konvolutt av segmenter med rette linjer som tilnærmet logaritmen bedre og bedre mens den fortsatt er over kurven, med et fast antall segmenter (muligens bare en enkelt tangentlinje). Prøvetaking fra en avkortet eksponentiell tilfeldig variabel er grei. Bare ta loggen over en ensartet tilfeldig variabel (med passende intervall og tilsvarende avkortning).

Dessverre kan ARS bare brukes fra prøvetaking fra log-konkav måltetthet. Av denne grunn har flere utvidelser av ARS blitt foreslått i litteratur for å håndtere ikke-log-konkave målfordelinger. Videre har forskjellige kombinasjoner av ARS og Metropolis-Hastings-metoden blitt designet for å oppnå en universell prøvetaker som bygger en selvjusterende forslagstetthet (dvs. et forslag som er automatisk konstruert og tilpasset målet). Denne metorklassen kalles ofte som Adaptive Rejection Metropolis Sampling (ARMS) algoritmer . De resulterende adaptive teknikkene kan alltid brukes, men de genererte prøvene er korrelert i dette tilfellet (selv om korrelasjonen forsvinner raskt til null etter hvert som antallet iterasjoner vokser).

Se også

Referanser

Robert, CP og Casella, G. "Monte Carlo Statistical Methods" (andre utgave). New York: Springer-Verlag, 2004.
J. von Neumann, "Ulike teknikker brukt i forbindelse med tilfeldige sifre. Monte Carlo -metoder", Nat. Bureau Standards, 12 (1951), s. 36–38.

Languages

In other projects