Fontossági mintavétel - Importance sampling

A statisztikák , fontossági mintavétel általános technika becslésére tulajdonságait egy adott eloszlás , míg csak az, hogy mintákat generált különböző eloszlású, mint a forgalmazás az érdeklődés. A módszert elsőként bevezetett Teun Kloek és Herman K. van Dijk , 1978-ban, és kapcsolatban van esernyő mintavétel a számítógépes fizika . Az alkalmazástól függően a kifejezés utalhat az alternatív elosztásból származó mintavételi folyamatra, a következtetés folyamatára vagy mindkettőre.

Alapelmélet

Hadd legyen egy véletlen változó bizonyos valószínűségi mező . Kívánunk megbecsülni a várható érték az X alatti P , jelöljük E [ X; P ]. Ha statisztikailag független véletlen mintáink vannak , P szerint generálva , akkor E [ X; P ] empirikus becslése${\ displaystyle X: \ Omega \ to \ mathbb {R}}$ ${\ displaystyle (\ Omega, {\ mathcal {F}}, P)}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

${\ displaystyle {\ widehat {\ mathbf {E}}} _ {n} [X; P] = {\ frac {1} {n}} \ sum _ {i = 1}^{n} x_ {i} }$

és ennek a becslésnek a pontossága X varianciájától függ :

${\ displaystyle \ operatornév {var} [{\ widehat {\ mathbf {E}}} _ {n}; P] = {\ frac {\ operatornév {var} [X; P]} {n}}.}$

A fontossági mintavétel alapgondolata, hogy az állapotok mintavételezése más eloszlásból történik, hogy csökkentse az E [ X; P ] becslésének szórását , vagy amikor a mintavétel P -ből nehéz. Ez úgy érhető el, hogy először egy véletlenszerű változót választunk, így E [ L ; P ] = 1 és ez a P - szinte mindenhol . Az L változóval megadunk egy valószínűséget, amely kielégíti ${\ displaystyle L \ geq 0}$ ${\ displaystyle L (\ omega) \ neq 0}$${\ displaystyle P^{(L)}}$

${\ displaystyle \ mathbf {E} [X; P] = \ mathbf {E} \ left [{\ frac {X} {L}}; P^{(L)} \ right].}$

Az X / L változóból így mintát veszünk P ^{( L ) alatt,} hogy megbecsüljük az E [ X; P ] értékeket a fentiek szerint, és ez a becslés akkor javul, ha . ${\ displaystyle \ operatornév {var} \ left [{\ frac {X} {L}}; P^{(L)} \ right] <\ operatorname {var} [X; P]}$

Ha X állandó előjelű Ω felett, akkor a legjobb L változó egyértelműen az lenne , így X / L * a keresett konstans E [ X; P ], és egyetlen minta P ^{( L *) alatt} elegendő az érték megadásához. Sajnos nem választhatjuk ezt a választást, mert E [ X; P ] pontosan ez az érték, amit keresünk! Ez az elméleti legjobb eset azonban L* betekintést ad abba, hogy milyen fontos a mintavétel: ${\ displaystyle L^{*} = {\ frac {X} {\ mathbf {E} [X; P]}} \ geq 0}$

${\ displaystyle {\ begin {aligned} \ forall a \ in \ mathbb {R}, \; P^{(L^{*})} (X \ in [a; a+da]) & = \ int _ {\ omega \ in \ {X \ in [a; a+da] \}} {\ frac {X (\ omega)} {E [X; P]}} \, dP (\ omega) \\ [6pt ] & = {\ frac {1} {E [X; P]}} \; a \, P (X \ in [a; a+da]) \ end {aligned}}}$

jobbra az egyik végtelen kicsi elem, amely E [ X ; P ]: ${\ displaystyle a \, P (X \ in [a; a+da])}$

${\ displaystyle E [X; P] = \ int _ {a =-\ infty}^{+\ infty} a \, P (X \ in [a; a+da])}$

ezért egy jó valószínűségváltozás P ^{( L )} a fontossági mintavételben újra elosztja X törvényét, így mintáinak frekvenciái közvetlenül az E [ X súlyuk szerint vannak rendezve ; P ]. Innen ered a "fontossági mintavétel" elnevezés.

A fontossági mintavételt gyakran használják Monte Carlo integrátorként . Mikor az egyenletes eloszlás és , E [ X; P ] megfelel a valós függvény integráljának . ${\ displaystyle P}$${\ displaystyle \ Omega = \ mathbb {R}}$${\ displaystyle X: \ mathbb {R} \ to \ mathbb {R}}$

Alkalmazás valószínűségi következtetésre

Az ilyen módszereket gyakran használják az állapot- és/vagy paraméterbecslési problémák utólagos sűrűségének vagy elvárásainak becslésére valószínűségi modellekben, amelyeket túl nehéz analitikusan kezelni, például Bayes -hálózatokban .

Alkalmazás szimulációhoz

A fontossági mintavétel egy varianciacsökkentési technika, amely a Monte Carlo módszerben alkalmazható . A fontossági mintavétel mögött az az elképzelés áll, hogy a szimulációban a bemeneti véletlen változók bizonyos értékei nagyobb hatással vannak a becsült paraméterre, mint mások. Ha ezeket a "fontos" értékeket gyakrabban mintavételezéssel hangsúlyozzuk, akkor a becslési variancia csökkenthető. Ezért a fontossági mintavétel alapvető módszere az, hogy olyan eloszlást válasszunk, amely "ösztönzi" a fontos értékeket. Az "elfogult" eloszlások ilyen használata torzított becslést eredményez, ha közvetlenül alkalmazzák a szimulációban. Mindazonáltal a szimulációs kimenetek súlyozva vannak a torzított eloszlás használatához, és ez biztosítja, hogy az új fontossági mintavételi becslő elfogulatlan legyen. A súlyt a valószínűségi arány adja meg , vagyis a valódi alapeloszlás Radon – Nikodym -származéka az elfogult szimulációs eloszlás tekintetében.

A fontossági mintavételi szimuláció végrehajtásának alapvető kérdése az elfogult eloszlás megválasztása, amely ösztönzi a bemeneti változók fontos régióit. A jó elfogult eloszlás kiválasztása vagy megtervezése a fontossági mintavétel "művészete". A jó elosztásért járó jutalom óriási futási idő megtakarítás lehet; a rossz elosztásért járó büntetés hosszabb futási idő lehet, mint egy általános Monte Carlo szimuláció esetében, fontossági mintavétel nélkül.

Tekintsük a mintának és a valószínűségi aránynak, ahol a kívánt eloszlás valószínűségi sűrűség (tömeg) függvénye és az elfogult/javaslat/mintaeloszlás valószínűségi sűrűség (tömeg) függvénye. Ezután a probléma jellemezhető a mintaeloszlás kiválasztásával, amely minimalizálja a skálázott minta szórását: ${\ displaystyle X}$${\ displaystyle {\ frac {f (X)} {g (X)}}}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle g}$

${\ displaystyle g^{*} = \ min _ {g} \ operatornév {var} _ {g} \ bal (X {\ frac {f (X)} {g (X)}} \ jobb).}$

Kimutatható, hogy a következő eloszlás minimalizálja a fenti szórást:

${\ displaystyle g^{*} (X) = {\ frac {| X | f (X)} {\ int | x | f (x) \, dx}}.}$

Vegye figyelembe, hogy amikor ez a szórás 0 lesz. ${\ displaystyle X \ geq 0}$

Matematikai megközelítés

Fontolja meg, hogy szimulációval becsülje meg egy esemény valószínűségét , ahol van egy véletlen változó eloszlási és valószínűségi sűrűségfüggvénnyel , ahol a prím derivált . Az eloszlásból A hosszúságú független és azonos eloszlású (iid) szekvencia jön létre , és a küszöbérték feletti véletlen változók száma megszámlálásra kerül. A véletlen változót a Binomiális eloszlás jellemzi${\ displaystyle p_ {t} \,}$${\ displaystyle X \ geq t}$${\ displaystyle X}$ ${\ displaystyle F}$ ${\ displaystyle f (x) = F '(x) \,}$${\ displaystyle K}$${\ displaystyle X_ {i} \,}$${\ displaystyle F}$${\ displaystyle k_ {t}}$${\ displaystyle t}$${\ displaystyle k_ {t}}$

${\ displaystyle P (k_ {t} = k) = {K \ select k} p_ {t}^{k} (1-p_ {t})^{Kk}, \, \ quad \ quad k = 0, 1, \ pont, K.}$

Ezt meg lehet mutatni , és ebben a korlátban, amit meg tudunk szerezni . Vegye figyelembe, hogy a szórás alacsony, ha . A fontossági mintavétel egy alternatív sűrűségfüggvény (for ) meghatározására és alkalmazására vonatkozik , amelyet általában szimulációs kísérletnek nevezünk. Ez a sűrűség lehetővé teszi az esemény gyakoribb előfordulását, így a szekvencia hossza kisebb lesz egy adott becslő variancia esetén. Alternatív megoldásként adott esetben az előfeszítési sűrűség használata kisebb varianciát eredményez, mint a hagyományos Monte Carlo becslés. A definíciójából az alábbiak szerint vezethetjük be . ${\ displaystyle \ operatornév {E} [k_ {t}/K] = p_ {t}}$${\ displaystyle \ operatornév {var} [k_ {t}/K] = p_ {t} (1-p_ {t})/K}$${\ displaystyle K \ to \ infty}$${\ displaystyle p_ {t}}$${\ displaystyle p_ {t} \ kb 1}$${\ displaystyle f _ {*} \,}$${\ displaystyle X}$${\ displaystyle {X \ geq t \}}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle p_ {t} \,}$${\ displaystyle f _ {*} \,}$

${\ displaystyle {\ begin {aligned} p_ {t} & = {E} [1 (X \ geq t)] \\ [6pt] & = \ int 1 (x \ geq t) {\ frac {f (x )} {f _ {*} (x)}} f _ {*} (x) \, dx \\ [6pt] & = E _ {*} [1 (X \ geq t) W (X)] \ end {igazítva }}}$

ahol

${\ displaystyle W (\ cdot) \ equiv {\ frac {f (\ cdot)} {f _ {*} (\ cdot)}}}$

valószínűségi arány, és súlyozási függvénynek nevezzük. A fenti egyenlet utolsó egyenlősége motiválja a becslőt

${\ displaystyle {\ hat {p}} _ {t} = {\ frac {1} {K}} \, \ sum _ {i = 1}^{K} 1 (X_ {i} \ geq t) W (X_ {i}), \, \ quad \ quad X_ {i} \ sim f _ {*}}$

Ez a fontossági mintavételi becslő és elfogulatlan. Vagyis a becslési eljárás során iid mintákat kell előállítani, és minden egyes minta esetén, amely meghaladja a becslést, növeli a mintaértékkel értékelt súly . Az eredményeket átlagolják a kísérletekhez képest. A fontossági mintavételi becslő szórása könnyen kimutatható ${\ displaystyle p_ {t} \,}$${\ displaystyle f _ {*} \,}$${\ displaystyle t \,}$${\ displaystyle W \}}$${\ displaystyle K \}}$

${\ displaystyle {\ begin {aligned} \ operatornév {var} _ {*} {\ widehat {p}} _ {t} & = {\ frac {1} {K}} \ operatornév {var} _ {*} [1 (X \ geq t) W (X)] \\ [5pt] & = {\ frac {1} {K}} \ left \ {{E _ {*}} [1 (X \ geq t)^{ 2} W^{2} (X)]-p_ {t}^{2} \ right \} \\ [5pt] & = {\ frac {1} {K}} \ left \ {{E} [1 (X \ geq t) W (X)]-p_ {t}^{2} \ jobb \} \ vége {igazított}}}$

Most a fontossági mintavételi probléma összpontosít egy olyan torzítási sűrűség megtalálására , hogy a fontossági mintavételi becslő szórása kisebb legyen, mint az általános Monte Carlo becslés szórása. Bizonyos előfeszítési sűrűségfüggvény esetében, amely minimalizálja a szórást, és bizonyos körülmények között nullára csökkenti, optimális előfeszítési sűrűségfüggvénynek nevezzük. ${\ displaystyle f _ {*} \,}$

Hagyományos torzítási módszerek

Bár sokféle elfogultsági módszer létezik, a fontossági mintavétel alkalmazásában a következő két módszert használják a legszélesebb körben.

Méretezés

Ha a valószínűségi tömeget az eseményrégióba eltoljuk a véletlen változó egységnél nagyobb számmal történő pozitív skálázásával, az növeli a sűrűségfüggvény szórását (átlagát is). Ennek eredményeként a sűrűség nehezebb farka, ami az esemény valószínűségének növekedéséhez vezet. A skálázás valószínűleg az egyik legkorábbi ismert torzítási módszer, amelyet széles körben alkalmaznak a gyakorlatban. Ez egyszerűen megvalósítható, és általában konzervatív szimulációs nyereséget biztosít más módszerekhez képest. ${\ displaystyle {X \ geq t \}}$${\ displaystyle X \,}$

A skálázással végzett mintavétel során a szimulációs sűrűséget választják a skálázott véletlen változó sűrűségfüggvényeként , ahol általában a farok valószínűségének becslésére szolgál. Átalakítással, ${\ displaystyle aX \,}$${\ displaystyle a> 1}$

${\ displaystyle f _ {*} (x) = {\ frac {1} {a}} f {\ bigg (} {\ frac {x} {a}} {\ bigg)} \,}$

és a súlyozási funkció az

${\ displaystyle W (x) = a {\ frac {f (x)} {f (x/a)}} \,}$

Míg a méretezés a valószínűségi tömeget a kívánt eseményrégióba tolja, a tömeget a komplementer régióba is tolja, ami nem kívánatos. Ha a véletlen változók összege , a tömeg terjedése dimenziós térben megy végbe . Ennek következménye a növekvő mintavételi jelentőség csökkenése , és ezt dimenzióhatásnak nevezik. A skálázással végzett mintavétel modern változata például az úgynevezett szigma-skálázott mintavétel (SSS), amely többszörös Monte Carlo (MC) elemzést futtat különböző skálázási tényezőkkel. Sok más nagy hozamú becslési módszerrel (például a legrosszabb esetek WCD-vel) szemben az SSS nem sokat szenved a dimenziós problémától. A több MC kimenet kezelése szintén nem csökkenti a hatékonyságot. Másrészt, mint WCD, az SSS -t csak a Gauss -féle statisztikai változókhoz tervezték, és a WCD -vel ellentétben az SSS -módszert nem arra tervezték, hogy pontos statisztikai sarkokat biztosítson. Az SSS másik hátránya, hogy az MC -k nagyméretű tényezőkkel történő futtatása nehézzé válhat, pl. A modell és a szimulátor konvergenciaproblémái miatt. Ezenkívül az SSS-ben erős torzítás-variancia kompromisszummal kell szembenéznünk: nagy léptékű tényezők használatával meglehetősen stabil hozameredményeket kapunk, de minél nagyobbak a skála-tényezők, annál nagyobb az elfogultsági hiba. Ha az SSS előnyei nem sokat számítanak az érdeklődés alkalmazásában, akkor gyakran más módszerek hatékonyabbak. ${\ displaystyle X <t \,}$${\ displaystyle X \,}$${\ displaystyle n \,}$${\ displaystyle n \,}$${\ displaystyle n \,}$

Fordítás

Egy másik egyszerű és hatékony elfogultsági technika a sűrűségfüggvény (és ebből adódóan véletlenszerű változó) fordítását alkalmazza annak valószínűségi tömege nagy részének a ritka események régiójában való elhelyezésére. A fordítás nem szenved dimenzióhatástól, és sikeresen alkalmazták a digitális kommunikációs rendszerek szimulációjával kapcsolatos számos alkalmazásban . Gyakran jobb szimulációs nyereséget biztosít, mint a méretezés. A fordítással történő torzításnál a szimulációs sűrűséget a

${\ displaystyle f _ {*} (x) = f (xc), \ quad c> 0 \,}$

hol van az eltolódás mértéke, és a fontossági mintavételi becslő szórásának minimalizálása érdekében kell kiválasztani. ${\ displaystyle c \,}$

A rendszer összetettségének hatásai

A fontossági mintavétel alapvető problémája, hogy a jó elfogult eloszlások tervezése a rendszer összetettségének növekedésével bonyolultabbá válik. A komplex rendszerek hosszú memóriájú rendszerek, mivel néhány bemenet összetett feldolgozása sokkal könnyebben kezelhető. Ez a dimenzió vagy memória háromféleképpen okozhat problémát:

• hosszú memória (súlyos szimbólumközi interferencia (ISI))
• ismeretlen memória ( Viterbi dekóderek )
• esetleg végtelen memória (adaptív hangszínszabályzó)

Elvileg a fontossági mintavételi ötletek változatlanok maradnak ezekben a helyzetekben, de a tervezés sokkal nehezebb lesz. A probléma leküzdésének sikeres megközelítése lényegében a szimuláció több kisebb, élesebben meghatározott alproblémára bontása. Ezután fontossági mintavételi stratégiákat alkalmaznak az egyes egyszerűbb alproblémák célzására. A szimuláció lebontásának technikái például a kondicionálás és hiba-esemény szimuláció (EES), valamint a regeneratív szimuláció.

A fontossági mintavétel értékelése

A sikeres fontossági mintavételi technikák azonosítása érdekében hasznos, ha számszerűsíteni tudjuk a fontossági mintavételi módszer alkalmazásának köszönhetően a futási idő megtakarítását. Az általánosan használt teljesítménymérés az , és ez úgy értelmezhető, mint a gyorsítási tényező, amellyel a fontossági mintavételi becslő ugyanazt a pontosságot éri el, mint az MC becslő. Ezt empirikusan kell kiszámítani, mivel a becslési eltérések analitikai szempontból nem valószínűek, ha az átlaguk kezelhetetlen. A fontossági mintavétel becslőjének számszerűsítésében további hasznos fogalmak a varianciahatárok és az aszimptotikus hatékonyság fogalma. Az egyik kapcsolódó mérce az úgynevezett effektív minta mérete (ESS) . ${\ displaystyle \ sigma _ {MC}^{2}/\ sigma _ {IS}^{2} \,}$

Varianciaköltség függvény

A szórás nem az egyetlen lehetséges költségfüggvény egy szimulációhoz, és más költségfüggvényeket, például az átlagos abszolút eltérést, különböző statisztikai alkalmazásokban használnak. Ennek ellenére a szórás az elsődleges költségfüggvény, amelyet a szakirodalom vizsgált, valószínűleg a konfidenciaintervallumok és a teljesítménymérés eltéréseinek köszönhetően . ${\ displaystyle \ sigma _ {MC}^{2}/\ sigma _ {IS}^{2} \,}$

Egy kapcsolódó probléma az a tény, hogy az arány túlbecsüli a futási idő megtakarítását a fontossági mintavétel miatt, mivel nem tartalmazza a súlyfüggvény kiszámításához szükséges többlet számítási időt. Ezért egyesek különböző módszerekkel értékelik a futásidejű nettó javulást. A komolyabb mintavétel talán komolyabb költsége a technika kidolgozásához és programozásához, valamint a kívánt súlyfüggvény elemzéséhez szükséges idő. ${\ displaystyle \ sigma _ {MC}^{2}/\ sigma _ {IS}^{2} \,}$

Többszörös és adaptív fontosságú mintavétel

Amikor különböző javaslat disztribúció , közösen használt rajz minták különböző megfelelő súlyfüggvények lehet alkalmazni (lásd például). Az adaptív környezetben, a javaslat disztribúció , és frissítjük minden iterációs az adaptív fontossági mintavétel algoritmus. Ezért, mivel javaslatsűrűséget használunk, a mintavételi és súlyozási sémák több megfelelő kombinációja is alkalmazható. ${\ displaystyle g_ {n} (x)}$${\ displaystyle n = 1, \ ldots, N,}$${\ displaystyle x_ {1}, \ ldots, x_ {N},}$${\ displaystyle g_ {n, t} (x)}$${\ displaystyle n = 1, \ ldots, N,}$${\ displaystyle t = 1, \ ldots, T,}$${\ displaystyle t}$

Lásd még

• Monte Carlo módszer
• Variancia csökkentés
• Rétegelt mintavétel
• Rekurzív rétegzett mintavétel
• VEGAS algoritmus
• Részecske szűrő - szekvenciális Monte Carlo módszer, amely fontossági mintavételt használ
• Segédpálya Monte Carlo
• Elutasító mintavétel
• Változó bitráta - a fontos mintavétel gyakori audio alkalmazása

Megjegyzések

Hivatkozások

• Arouna, Bouhari (2004). "Adaptív Monte Carlo módszer, varianciacsökkentési technika". Monte Carlo módszerek és alkalmazásuk . 10. (1): 1–24. doi : 10.1515/156939604323091180 .
• Bucklew, James Antonio (2004). Bevezetés a ritka eseményszimulációba . New York: Springer-Verlag.
• Doucet, A .; de Freitas, N .; Gordon, N. (2001). Sorozatos Monte Carlo módszerek a gyakorlatban . Springer. ISBN 978-0-387-95146-1.
• Ferrari, M .; Bellini, S. (2001). Fontosság A turbó termékkódok mintavételezési szimulációja . Az IEEE nemzetközi konferenciája a kommunikációról . 9 . 2773–2777. doi : 10.1109/ICC.2001.936655 . ISBN 978-0-7803-7097-5.
• Mazonka, Oleg (2016). "Könnyű, mint Pi: A fontos mintavételi módszer" (PDF) . Journal of Reference . 16 .
• Oberg, Tommy (2001). Moduláció, észlelés és kódolás . New York: John Wiley & Sons.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "7.9.1 . Szakasz Fontossági mintavétel" . Numerikus receptek: A tudományos számítástechnika művészete (3. kiadás). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Ripley, BD (1987). Sztochasztikus szimuláció . Wiley & Sons.
• Smith, PJ; Shafi, M .; Gao, H. (1997). "Gyors szimuláció: A kommunikációs rendszerek mintavételi technikáinak áttekintése". IEEE folyóirat a kommunikáció kiválasztott területeiről . 15 (4): 597–613. doi : 10.1109/49.585771 .
• Srinivasan, R. (2002). Fontossági mintavétel - Alkalmazások kommunikációban és észlelésben . Berlin: Springer-Verlag.

Külső linkek

• Sorozatos Monte Carlo módszerek (részecskeszűrés) honlap a Cambridge -i Egyetemen
• Bevezetés a fontossági mintavételbe ritka események szimulációiban European Journal of Physics. PDF dokumentum.
• Adaptív monte carlo módszerek ritka események szimulációjához: adaptív monte carlo módszerek ritka események szimulációihoz Téli szimulációs konferencia