Mintavétel szignifikancia szerint

A fontossági mintavétel ( továbbiakban OT) a valószínűségi változó varianciájának csökkentésére szolgáló egyik módszer , amellyel a Monte Carlo módszerrel bármilyen mennyiség modellezési folyamatának konvergenciáját javítják . A VZ ötlete azon a tényen alapul, hogy a modellezés során a valószínűségi változó egyes értékeinek nagyobb jelentősége (valószínűsége) van a kiértékelt függvény (paraméter) szempontjából, mint másoknak. Ha ezek a „valószínűbb” értékek gyakrabban jelennek meg egy valószínűségi változó kiválasztása során, akkor a becsült függvény szórása csökkenni fog. Ezért az EOI mögöttes módszertana olyan eloszlás kiválasztása, amely a valószínűségi változó "valószínűbb" értékeinek kiválasztását részesíti előnyben. Egy ilyen "elfogult" eloszlás megváltoztatja a becsült függvényt, ha közvetlenül alkalmazzák a számítási folyamatban. A számítás eredménye azonban ennek a torzított eloszlásnak megfelelően újrasúlyozásra kerül, és ez biztosítja, hogy az új becsült OT függvény ne legyen torzított. Magát a súlyt a valószínűségi arány adja meg , azaz a valódi kezdeti eloszlás Radon-Nikodym deriváltja a választott torzított eloszláshoz képest.

Az EOI megvalósításának alapvető feladata egy torzított eloszlás kiválasztása, amely azonosítja azokat a régiókat, amelyeknél a becsült függvény "valószínűbb" értékei vannak.

A VZ akkor hatékony, ha egy ilyen eloszlást választunk és sikeresen szerkesztünk, mivel jelentősen csökkenti a számítási időt. Szerencsétlen elfogult eloszlás esetén még a standard Monte Carlo-módszer is jobb eredményt adhat.

Matematikai alapok

Fontolja meg egy esemény valószínűségének modellezését , ahol egy valószínűségi változó eloszlású és valószínűségi sűrűséggel , ahol a prím a deriváltját jelenti . Eloszlása alapján állítsunk elő egy K hosszúságú statisztikát, K független és egyenletes eloszlású esemény sorozatát , és meg akarjuk becsülni, hogy a K-ben hány valószínűségi változók vannak, amelyek értéke valami felett van . A valószínűségi változót a binomiális eloszlás jellemzi $p_{t}$ ${ X \ge t\ }$ $x$ $F$ $f(x)=F'(x)$ $X_{i}$ $F$ $k_t$ $t$ $k_t$

P(k_t = k)={K\válasszon k}p_t^k(1-p_t)^{Kk},\,\quad \quad k=0,1,\pontok,K.

A szignifikancia-mintavétel egy másik sűrűségfüggvény (X-re) felépítésére és használatára vonatkozik, amelyet általában torzított sűrűségnek neveznek, egy számítási kísérletben (szimuláció). Az új sűrűség lehetővé teszi, hogy az esemény gyakrabban forduljon elő, így a szerkesztett statisztika varianciájának adott értékéhez tartozó sorozat hossza csökken. Más szóval, egy adott K-statisztikánál a torzított sűrűség használata kisebb szórást eredményez, mint a hagyományos Monte Carlo-becslés. A definícióból a következőképpen írhatjuk be : $f_{*}$ ${ X \ge t\ }$ $p_{t}$ $f_{*}$

p_t = {E}[X\ge t]

= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx

= {E_*} [(X \ge t) W(X)]

ahol

W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)}

a valószínűségi hányados, és súlyfüggvénynek nevezzük. Az utolsó egyenlőség a statisztikák figyelembevételéhez vezet

\hat p_t = \frac{1}{K}\,\sum_{i=1}^K (X_i \ge t) W(X_i),\,\quad \quad X_i \sim f_*

Ez egy OT statisztika, és használatakor nem utasítják el . Így a VZ szimulációs eljárása úgy fogalmazható meg, hogy független és egyenletes eloszlású események sorozatát készítjük el a sűrűséghez , amikor minden eseménynek megnövekedett súlya lesz, és a további eseményeket a korábbiak szerint fogadjuk el, ha nagyobbak, mint . Az eredmény az összes statisztika átlaga . Könnyen kimutatható, hogy az OT becslés szórása egyenlő lesz $p_{t}$ $f_{*}$ $f_{*}$ $W$ $t$ $K$

Var_{*}{\hat {p}}_{t}={\frac {1}{K}}Var_{*}[(X\geq t)W(X)]

= \frac{1}{K}\Big[{E_*}[(X \ge t)^2 W^2(X)] - p_t^2 \Big]

= \frac{1}{K}\Big[{E}[(X \ge t)^2 W(X)] - p_t^2 \Big]

Most az OT probléma úgy fogalmazható meg, hogy olyan valószínűségi sűrűséget találunk, hogy az új statisztika szórása kisebb lesz, mint a szokásos Monte Carlo módszerrel kapott. Ha a feladatban meg lehet alkotni egy torzított valószínűségi sűrűséget, amelyre a variancia 0, akkor azt optimális torzított valószínűségi sűrűségnek nevezzük. $f_{*}$

Módszerek torzított eloszlások létrehozására

Bár számos módszer létezik a torzított sűrűségek ábrázolására, a következő két módszer a legelterjedtebb EOI-k használatakor.

Méretezés

Valószínűségi mértéket helyezhet el egy régióba úgy, hogy egy valószínűségi változót egynél nagyobb számmal skáláz. Az ilyen skálázás a valószínűségi sűrűség farkának szignifikanciájának növekedéséhez vezet, és így növeli a „kívánt” események bekövetkezésének valószínűségét. Minden valószínűség szerint a méretezés volt az egyik első, a gyakorlatban széles körben alkalmazott torzítási módszer. Könnyen implementálható valódi algoritmusokba, és ez a módszer meglehetősen szerény javulást eredményez a szimulációs hatékonyságban a többi torzítási módszerhez képest. ${ X \ge t\ }$ $x$

A VZ-ben skálázáskor a szimuláció valószínűségi sűrűsége a skálázott valószínűségi változó eredeti sűrűségeként van definiálva . Ha fontos számunkra, hogy a valószínűségi sűrűség végét felfelé becsüljük, válassza a lehetőséget . Az új sűrűség- és súlyfüggvény az $aX$ $a>1$

{\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )))

és

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

Míg a skálázás a valószínűségi mértéket a "kívánt" események kívánt tartományába tolja, a valószínűséget is a régióba tolja el . Ha a valószínűségi változók összege , akkor a valószínűségi szórás a -edik térben történik. Következésképpen ez csökkenti az IO hatékonyságát, ahogy nő (dimenziós hatás). $X<t$ $x$ $n$ $n$ $n$

Adás

Egy másik egyszerű és hatékony torzítási technika a valószínűségi sűrűség (és így a valószínűségi változó) olyan tartományba történő fordításán alapul, ahol a valószínűség növekszik. A fordítások nem vezetnek dimenzióhatáshoz. Ezt a technikát sikeresen alkalmazták valós alkalmazásokban, például digitális kommunikációs rendszerek modellezésében . Gyakran ez a módszer hatékonyabb, mint a méretezés. Fordítási torzítás esetén az új valószínűségi sűrűséget a következőképpen határozzuk meg

f_{*}(x)=f(xc),\quad c>0

ahol az IS statisztika szórásának minimalizálásának feltételéből választott eltolási érték. $c$

Rendszerkomplexitási hatások

Az OT alapvető problémája a jó torzított eloszlás felépítésének nehézsége, ahogy a vizsgált rendszer bonyolultabbá válik. Ebben az értelemben a hosszú memóriával rendelkező rendszereket komplex rendszereknek nevezzük, mivel azoknál a rendszereknél, ahol kisszámú bemeneti paraméter komplex feldolgozása történik (vagyis kis dimenziójú problémák esetén), az OT felépítésének problémája egyszerűbb. Például a digitális jelzéselméletben a hosszú memória (vagy a kezdeti feltételek nagy dimenziója) háromféle problémához vezet:

hosszú memória (erős karakterek közötti interakció)
határozatlan hosszúságú memória (Viterbi dekóderek)
esetleg végtelen hosszúságú memória (adaptív hangszínszabályzók)

Az EO alapelvei elvileg nem változnak az ilyen jellegű problémákra alkalmazva, de a megvalósítás sokkal bonyolultabbá válik. A hosszú memóriaproblémák kezelésének sikeres stratégiája lehet az egész probléma több, jobban meghatározott részre bontása. Ezután az EOI-t az egyes részproblémákra külön-külön alkalmazzák.

Az OT számszerű becslései

A talált IO-sűrűség sikerességének meghatározásához hasznos számszerű becslést készíteni a számítások mennyiségének csökkentéséről annak alkalmazásakor. Egy ilyen becsléshez általában az arányt használják , amely olyan tényezőként értelmezhető, amely növeli azt a sebességet, amellyel az OT statisztika ugyanolyan pontosságot ér el, mint a szokásos Monte Carlo módszerrel kapott statisztikák. Az arány értékét csak empirikusan kaphatjuk meg, mivel a statisztikák szórásait szinte lehetetlen analitikusan levezetni. ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2))$

Variancia árfüggvénye

A variancia nem az egyetlen modellezhető árfüggvény , mivel vannak más típusú árfüggvények is, amelyeket különféle statisztikai alkalmazásokban használnak, például az átlagos abszolút eltérést. Az irodalomban azonban gyakran hivatkoznak a variancia szórására, valószínűleg a konfidenciaintervallumok számításánál és a hatékonyság mérésére szolgáló kifejezéseknél a variancia használatának köszönhetően . ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2))$

Az egyik probléma a variancia használatával, hogy az arány túlbecsüli a számítási erőfeszítések csökkenését az EOI használatakor, mivel ez a paraméter nem veszi figyelembe a súlyfüggvény kiszámításához szükséges további időt. Ezért egy valós alkalmazásban az EOI alkalmazásából adódó javulást más módszerekkel kell értékelni. A hatékonyság szempontjából talán komolyabb probléma az EOI-ban magának a technika kidolgozásának és megvalósításának ideje, valamint a szükséges súlyfüggvény analitikus felépítése (ha ez nem ismert előre). ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2))$

Lásd még

Monte Carlo módszer
Zónás mintavétel
Rekurzív zónás mintavétel
Szekvenciális Monte Carlo módszerek vagy részecskeszűrő

Irodalom

I. M. Sobol. Numerikus Monte Carlo-módszerek. M.: Nauka, 1973
PJSmith, M. Shafi és H. Gao, "Gyors szimuláció: A mintavételi technikák fontosságának áttekintése kommunikációs rendszerekben", IEEE J.Select.Areas Commun., vol. 15, pp. 597-613, 1997. május.
M. Ferrari, S. Bellini, "Importance Sampling simulation of turbo product codes", ICC2001, The IEEE International Conference on Communications, vol. 9, pp. 2773–2777, 2001. június.
Tommy Oberg, Moduláció, észlelés és kódolás, John Wiley & Sons, Inc., New York, 2001.
R. Srinivasan., Fontossági mintavétel. New York: Springer, 2002.

Továbbá

"Fontossági mintavétel – Alkalmazások a kommunikációban és az észlelésben", Rajan Srinivasan, Springer-Verlag, Berlin, 2002.
"Bevezetés a ritka események szimulációjába", James Antonio Bucklew, Springer-Verlag, New York, 2004.

Linkek

Szekvenciális Monte Carlo Methods (részecskeszűrés) honlapja a Cambridge-i Egyetemen
Bevezetés a mintavétel fontosságába 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ójához Téli szimulációs konferencia
Kuba – a többdimenziós numerikus integráció könyvtára