Prøve for omvendt transformasjon - Inverse transform sampling

Inverse transform sampling (også kjent som inversjons sampling , den inverse sannsynlighetsintegrale transformasjonen , den inverse transformasjonsmetoden , Smirnov- transformasjonen eller den gyldne regelen ) er en grunnleggende metode for sampling av pseudo-tilfeldig tall , dvs. for å generere utvalgstall tilfeldig fra hvilken som helst sannsynlighetsfordeling gitt sin kumulative fordelingsfunksjon .

Invers transformasjon sampling tar ensartede prøver av et tall mellom 0 og 1, tolket som en sannsynlighet, og returnerer deretter det største tallet fra distribusjonsdomenet slik at . Tenk deg for eksempel at det er standard normalfordeling med gjennomsnitt null og standardavvik en. Tabellen nedenfor viser prøver tatt fra den ensartede fordelingen og deres representasjon på standard normalfordeling. ${\ displaystyle u}$ ${\ displaystyle x}$ ${\ displaystyle P (X)}$ ${\ displaystyle P (- \ infty <X <x) \ leq u}$ ${\ displaystyle P (X)}$

Transformasjon fra uniform prøve til normal
${\ displaystyle u}$	${\ displaystyle F ^ {- 1} (u)}$
.5	0
.975	1.95996
.995	2,5758
.999999	4,75342
1-2 ^-52	8.12589

Invers transformasjonsprøving for normalfordeling

Vi velger tilfeldig en andel av arealet under kurven og returnerer tallet i domenet slik at nøyaktig denne andelen av området kommer til venstre for det tallet. Intuitivt er det usannsynlig at vi velger et tall i den ytterste enden av halene, fordi det er veldig lite område i dem som vil kreve å velge et tall som er veldig nær null eller ett.

Beregningsmessig innebærer denne metoden å beregne fordelingenes kvantile funksjon - med andre ord, beregne den kumulative fordelingsfunksjonen (CDF) til fordelingen (som kartlegger et tall i domenet med en sannsynlighet mellom 0 og 1) og deretter invertere den funksjonen. Dette er kilden til begrepet "invers" eller "inversjon" i de fleste navnene på denne metoden. Merk at for en diskret distribusjon er det generelt ikke for vanskelig å beregne CDF: vi legger ganske enkelt sammen de individuelle sannsynlighetene for de forskjellige fordelingspunktene. For en kontinuerlig fordeling må vi imidlertid integrere distribusjonens sannsynlighetstetthetsfunksjon (PDF), som er umulig å gjøre analytisk for de fleste distribusjoner (inkludert normalfordeling ). Som et resultat kan denne metoden være beregningsmessig ineffektiv for mange distribusjoner og andre metoder foretrekkes; det er imidlertid en nyttig metode for å bygge mer generelt anvendelige prøvetakere som de som er basert på avvisningssampling .

For normalfordelingen betyr mangel på et analytisk uttrykk for den tilsvarende kvantile funksjonen at andre metoder (f.eks. Box – Muller-transformasjonen ) kan foretrekkes beregningsmessig. Det er ofte slik at, selv for enkle distribusjoner, kan metoden for invers transformasjon sampling forbedres på: se for eksempel ziggurat-algoritmen og avvisningssampling . På den annen side er det mulig å tilnærme kvantilfunksjonen til normalfordelingen ekstremt nøyaktig ved bruk av polynomer med moderat grad, og faktisk er metoden for å gjøre dette rask nok til at inversjonsprøvetaking nå er standardmetoden for prøvetaking fra en normalfordeling i statistisk pakke R .

Definisjon

Den Sannsynligheten integrerende trans sier at hvis er en kontinuerlig stokastisk variabel med kumulativ fordelingsfunksjon , da den tilfeldige variable har en jevn fordeling på [0, 1]. Den inverse sannsynlighetsintegrale transformasjonen er bare den inverse av dette: spesifikt, hvis har en jevn fordeling på [0, 1] og hvis har en kumulativ fordeling , så har den tilfeldige variabelen samme fordeling som . ${\ displaystyle X}$ ${\ displaystyle F_ {X}}$ ${\ displaystyle Y = F_ {X} (X)}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle F_ {X}}$ ${\ displaystyle F_ {X} ^ {- 1} (Y)}$ ${\ displaystyle X}$

Graf over inversjonsteknikken fra til . Nederst til høyre ser vi den vanlige funksjonen og øverst til venstre dens inversjon.

{\ displaystyle x}

{\ displaystyle F (x)}

Intuisjon

Fra , vi ønsker å generere med CDF Vi antar å være en streng økende funksjon, som gir god intuisjon. ${\ displaystyle U \ sim \ mathrm {Unif} [0,1]}$ ${\ displaystyle X}$ ${\ displaystyle F_ {X} (x).}$ ${\ displaystyle F_ {X} (x)}$

Vi ønsker å se om vi kan finne noen streng monotontransformasjon , slik at . Vi vil ha ${\ displaystyle T: [0,1] \ mapsto \ mathbb {R}}$ ${\ displaystyle T (U) {\ overset {d} {=}} X}$

${\ displaystyle F_ {X} (x) = \ Pr (X \ leq x) = \ Pr (T (U) \ leq x) = \ Pr (U \ leq T ^ {- 1} (x)) = T ^ {- 1} (x), {\ text {for}} x \ i \ mathbb {R},}$

hvor det siste trinnet brukte den når er uniform på . ${\ displaystyle \ Pr (U \ leq y) = y}$ ${\ displaystyle U}$ ${\ displaystyle (0,1)}$

Så vi måtte være den omvendte funksjonen til , eller, ekvivalent ${\ displaystyle F_ {X}}$ ${\ displaystyle T}$ ${\ displaystyle T (u) = F_ {X} ^ {- 1} (u), u \ i [0,1].}$

Derfor kan vi generere fra ${\ displaystyle X}$ ${\ displaystyle F_ {X} ^ {- 1} (U).}$

Metoden

Skjematisk oversikt over den omvendte transformasjonsprøvetaking. Den omvendte funksjonen av kan defineres av .

{\ displaystyle y = F_ {X} (x)}

{\ displaystyle F_ {X} ^ {- 1} (y) = \ mathrm {inf} \ {x | F_ {X} (x) \ geq y \}}

En animasjon av hvordan invers transformasjonssampling genererer normalt fordelte tilfeldige verdier fra jevnt fordelte tilfeldige verdier

Problemet som metoden for invers transformasjonssampling løser er som følger:

La være en tilfeldig variabel hvis fordeling kan beskrives av den kumulative fordelingsfunksjonen . ${\ displaystyle X}$ ${\ displaystyle F_ {X}}$
Vi ønsker å generere verdier som fordeles i henhold til denne fordelingen. ${\ displaystyle X}$

Den omvendte transformasjons prøvetakingsmetoden fungerer som følger:

Generer et tilfeldig tall fra standard uniformfordeling i intervallet , f.eks. Fra ${\ displaystyle u}$ ${\ displaystyle [0,1]}$ ${\ displaystyle U \ sim \ mathrm {Unif} [0,1].}$
Finn det omvendte av ønsket CDF, f.eks . ${\ displaystyle F_ {X} ^ {- 1} (x)}$
Beregn . Den beregnede tilfeldige variabelen har fordeling . ${\ displaystyle X = F_ {X} ^ {- 1} (u)}$ ${\ displaystyle X}$ ${\ displaystyle F_ {X} (x)}$

Uttrykt annerledes, gitt en kontinuerlig ensartet variabel i og en inverterbar kumulativ fordelingsfunksjon , har den tilfeldige variabelen fordeling (eller blir distribuert ). ${\ displaystyle U}$ ${\ displaystyle [0,1]}$ ${\ displaystyle F_ {X}}$ ${\ displaystyle X = F_ {X} ^ {- 1} (U)}$ ${\ displaystyle F_ {X}}$ ${\ displaystyle X}$ ${\ displaystyle F_ {X}}$

En behandling av slike inverse funksjoner som objekter som tilfredsstiller differensiallikninger, kan gis. Noen slike differensiallikninger tillater eksplisitte kraftserieløsninger, til tross for deres ikke-linearitet.

Eksempler

Anta at vi har en tilfeldig variabel og en kumulativ fordelingsfunksjon ${\ displaystyle U \ sim \ mathrm {Unif} (0,1)}$

{\ displaystyle {\ begin {align} F (x) = 1- \ exp (- {\ sqrt {x}}) \ end {align}}}

For å utføre en inversjon vi ønsker å løse for

{\ displaystyle F (F ^ {- 1} (u)) = u}

{\ displaystyle {\ begin {justert} F (F ^ {- 1} (u)) & = u \\ 1- \ exp \ left (- {\ sqrt {F ^ {- 1} (u)}} \ høyre) & = u \\ F ^ {- 1} (u) & = (- \ log (1-u)) ^ {2} \\ & = (\ log (1-u)) ^ {2} \ slutt {justert}}}

Herfra ville vi utføre trinn ett, to og tre.

Som et annet eksempel bruker vi den eksponensielle fordelingen med for x ≥ 0 (og ellers 0). Ved å løse y = F (x) får vi den inverse funksjonen ${\ displaystyle F_ {X} (x) = 1-e ^ {- \ lambda x}}$

{\ displaystyle x = F ^ {- 1} (y) = - {\ frac {1} {\ lambda}} \ ln (1-y).}

Det betyr at hvis vi trekker noe fra a og beregner Dette har eksponensiell fordeling.

{\ displaystyle y_ {0}}

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

{\ displaystyle x_ {0} = F_ {X} ^ {- 1} (y_ {0}) = - {\ frac {1} {\ lambda}} \ ln (1-y_ {0}),}

{\ displaystyle x_ {0}}

Ideen er illustrert i følgende graf:

Tilfeldige tall y _i genereres fra en jevn fordeling mellom 0 og 1, dvs. Y ~ U (0, 1). De er tegnet som fargede punkter på y-aksen. Hvert av punktene er kartlagt i henhold til x = F ⁻¹ (y), som er vist med grå piler for to eksempler. I dette eksemplet har vi brukt en eksponentiell fordeling. Derfor er sannsynlighetstettheten for x ≥ 0 og den kumulative fordelingsfunksjonen er . Derfor . Vi kan se at ved bruk av denne metoden ender mange poeng nær 0 og bare få poeng har høye x-verdier - akkurat som det forventes for en eksponentiell fordeling.

{\ displaystyle \ varrho _ {X} (x) = \ lambda e ^ {- \ lambda \, x}}

{\ displaystyle F (x) = 1-e ^ {- \ lambda \, x}}

{\ displaystyle x = F ^ {- 1} (y) = - {\ frac {\ ln (1-y)} {\ lambda}}}

Merk at fordelingen ikke endres hvis vi starter med 1-y i stedet for y. For beregningsformål er det tilstrekkelig å generere tilfeldige tall y i [0, 1] og deretter bare beregne

{\ displaystyle x = F ^ {- 1} (y) = - {\ frac {1} {\ lambda}} \ ln (y).}

Bevis på korrekthet

La F være en kontinuerlig kumulativ fordelingsfunksjon , og la F ⁻¹ være dens omvendte funksjon (ved hjelp av infimumet fordi CDF er svakt monotont og høyre-kontinuerlig ):

{\ displaystyle F ^ {- 1} (u) = \ inf \; \ {x \ mid F (x) \ geq u \} \ qquad (0 <u <1).}

Krav: Hvis U er en jevn tilfeldig variabel på (0, 1), har F som CDF. ${\ displaystyle F ^ {- 1} (U)}$

Bevis:

{\ displaystyle {\ begin {align} & \ Pr (F ^ {- 1} (U) \ leq x) \\ & {} = \ Pr (U \ leq F (x)) \ quad & ({\ text {søker}} F, {\ text {til begge sider}}) \\ & {} = F (x) \ quad & ({\ text {fordi}} \ Pr (U \ leq y) = y, {\ tekst {når U er ensartet på}} (0,1)) \\\ slutt {justert}}}

Avkortet fordeling

Inverse transform-sampling kan ganske enkelt utvides til tilfeller av avkortede distribusjoner i intervallet uten kostnadene ved avvisningssampling: den samme algoritmen kan følges, men i stedet for å generere et tilfeldig tall jevnt fordelt mellom 0 og 1, generere jevnt fordelt mellom og , og så igjen ta . ${\ displaystyle (a, b]}$ ${\ displaystyle u}$ ${\ displaystyle u}$ ${\ displaystyle F (a)}$ ${\ displaystyle F (b)}$ ${\ displaystyle F ^ {- 1} (u)}$

Reduksjon av antall inversjoner

For å få et stort antall prøver, må man utføre samme antall inversjoner av distribusjonen. En mulig måte å redusere antall inversjoner mens man oppnår et stort antall prøver, er anvendelse av den såkalte Stochastic Collocation Monte Carlo sampler (SCMC sampler) innenfor et polynomisk kaos utvidelsesrammeverk. Dette lar oss generere et hvilket som helst antall Monte Carlo-prøver med bare noen få inversjoner av den opprinnelige distribusjonen med uavhengige eksempler på en variabel som inversjonene er analytisk tilgjengelige for, for eksempel standard normalvariabelen.

Se også

Sannsynlighet integrert transformasjon
Copula , definert ved hjelp av sannsynlighet integrert transformasjon.
Kvantilfunksjon , for eksplisitt konstruksjon av inverse CDFer.
Invers fordelingsfunksjon for en presis matematisk definisjon for distribusjoner med diskrete komponenter.

Referanser

^ Aalto University, N. Hyvönen, Computational methods in inverse problems. Tolfte forelesning https://noppa.tkk.fi/noppa/kurssi/mat-1.3626/luennot/Mat-1_3626_lecture12.pdf
^ Luc Devroye (1986). Ikke-enhetlig generasjon av tilfeldige varianter (PDF) . New York: Springer-Verlag.
^ https://stat.ethz.ch/R-manual/R-devel/library/base/html/Random.html
^ Steinbrecher, G., Shaw, WT (2008). Kvantemekanikk. European Journal of Applied Mathematics 19 (2): 87–112.
^ Luc Devroye (1986). "Avsnitt 2.2. Inversjon ved numerisk løsning av F ( X ) = U " (PDF) . Ikke-enhetlig tilfeldig variasjonsgenerering . New York: Springer-Verlag.
^ LA Grzelak, JAS Witteveen, M. Suarez og CW Oosterlee. Den stokastiske samlokaliseringen av Monte Carlo-sampleren: Svært effektiv prøvetaking fra “dyre” distribusjoner. https://ssrn.com/abstrakt=2529691

[aalto-1] Aalto University, N. Hyvönen, Computational methods in inverse problems. Tolfte forelesning https://noppa.tkk.fi/noppa/kurssi/mat-1.3626/luennot/Mat-1_3626_lecture12.pdf

[2] Luc Devroye (1986). Ikke-enhetlig generasjon av tilfeldige varianter (PDF) . New York: Springer-Verlag.

[3] ttps://stat.ethz.ch/R-manual/R-devel/library/base/html/Random.html

[4] Steinbrecher, G., Shaw, WT (2008). Kvantemekanikk. European Journal of Applied Mathematics 19 (2): 87–112.

[5] Luc Devroye (1986). "Avsnitt 2.2. Inversjon ved numerisk løsning av F ( X ) = U " (PDF) . Ikke-enhetlig tilfeldig variasjonsgenerering . New York: Springer-Verlag.

[6] LA Grzelak, JAS Witteveen, M. Suarez og CW Oosterlee. Den stokastiske samlokaliseringen av Monte Carlo-sampleren: Svært effektiv prøvetaking fra “dyre” distribusjoner. https://ssrn.com/abstrakt=2529691

Languages

In other projects