Vzorkování podle významnosti

Význam vzorkování ( dále OT) je jednou z metod snižování rozptylu náhodné veličiny, která se používá ke zlepšení konvergence procesu modelování libovolné veličiny metodou Monte Carlo . Myšlenka OT je založena na skutečnosti, že některé hodnoty jsou náhodné proměnné v procesu modelování mají pro hodnocenou funkci (parametr) větší význam (pravděpodobnost) než ostatní. Pokud se tyto „pravděpodobnější“ hodnoty objeví při výběru náhodné veličiny častěji, rozptyl odhadované funkce se sníží. Proto je základní metodologií EOI výběr distribuce, která upřednostňuje výběr „pravděpodobnějších“ hodnot náhodné proměnné. Takovéto „vychýlené“ rozdělení změní odhadovanou funkci, pokud se použije přímo v procesu výpočtu. Výsledek výpočtu je však převážen podle tohoto zkresleného rozdělení, což zajišťuje, že nová odhadovaná funkce OT nebude zkreslena. Samotná váha je dána poměrem pravděpodobnosti , tedy derivátem Radon-Nikodimskutečné počáteční rozdělení s ohledem na zvolené zkreslené rozdělení.

Základním úkolem při implementaci EOI je výběr zkreslené distribuce, která identifikuje regiony s „pravděpodobnějšími“ hodnotami odhadované funkce.

VZ je efektivní, pokud je takové rozdělení vybráno a zkonstruováno úspěšně, protože výrazně zkrátí dobu výpočtu. S nešťastnou zkreslenou distribucí může i standardní metoda Monte Carlo poskytnout lepší výsledky.

Matematické základy

Zvažte modelování pravděpodobnosti události , kde je náhodná veličina s rozdělením a hustotou pravděpodobnosti , kde prvočíslo znamená derivaci . Nechť se vygeneruje statistika délky K, posloupnost K nezávislých a rovnoměrně rozložených událostí na základě rozdělení , a chceme odhadnout počet náhodných proměnných v K, jejichž hodnoty leží nad některými . Náhodná veličina je charakterizována binomickým rozdělením $p_{t}$ ${ X \ge t\ }$ $X$ $F$ $f(x)=F'(x)$ $X_{i}$ $F$ $k_t$ $t$ $k_t$

P(k_t = k)={K\vyberte k}p_t^k(1-p_t)^{Kk},\,\quad \quad k=0,1,\tečky,K.

Vzorkování významnosti odkazuje na konstrukci a použití další funkce hustoty (pro X), běžně označované jako vychýlená hustota, ve výpočetním experimentu (simulaci). Nová hustota umožňuje, aby se událost vyskytovala častěji, čímž se zkrátí délka sekvence pro danou hodnotu rozptylu konstruované statistiky . Jinými slovy, pro danou statistiku K výsledkem použití vychýlené hustoty je menší rozptyl než konvenční odhad Monte Carlo. Z definice můžeme zadat následující: $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)]

kde

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

je pravděpodobnostní poměr a nazývá se váhová funkce. Poslední rovnost vede k zohlednění statistiky

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

Toto je statistika OT pro a není při použití odmítnuta . Simulační postup pro VZ lze tedy formulovat jako přípravu sekvence nezávislých a rovnoměrně rozložených událostí pro hustotu , kdy každá událost bude mít zvýšenou váhu a další události jsou akceptovány jako dříve, pokud jsou větší než . Výsledek je zprůměrován přes všechny statistiky . Je snadné ukázat, že rozptyl odhadu OT bude roven $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]

Nyní lze problém OT formulovat jako nalezení takové hustoty pravděpodobnosti , že rozptyl nové statistiky bude menší než rozptyl získaný obvyklou metodou Monte Carlo. Pokud je v úloze možné sestrojit zkreslenou hustotu pravděpodobnosti, pro kterou je rozptyl 0, pak se nazývá optimální zkreslená hustota pravděpodobnosti. $F_{*}$

Metody pro konstrukci zkreslených distribucí

Ačkoli existuje mnoho metod pro vykreslování vychýlených hustot, následující dvě metody jsou nejběžnější při použití EOI.

Měřítko

Posuňte míru pravděpodobnosti do oblasti změnou měřítka náhodné proměnné o číslo větší než jedna. Takové škálování vede ke zvýšení významnosti konce hustoty pravděpodobnosti a tím ke zvýšení pravděpodobnosti výskytu "požadovaných" událostí. S největší pravděpodobností bylo škálování jednou z prvních metod zkreslení široce používaných v praxi. Tato metoda, kterou lze snadno implementovat do skutečných algoritmů, poskytuje poměrně mírné zlepšení účinnosti simulace ve srovnání s jinými metodami zkreslení. ${ X \ge t\ }$ $X$

Ve VZ při škálování je hustota pravděpodobnosti pro simulaci definována jako původní hustota pro škálovanou náhodnou veličinu . Pokud je pro nás důležité odhadnout konec hustoty pravděpodobnosti směrem nahoru, zvolte . Nová hustota a hmotnostní funkce jsou $aX$ $a>1$

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

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

Zatímco škálování posouvá míru pravděpodobnosti do požadované oblasti „požadovaných“ událostí, posouvá také pravděpodobnost do oblasti . Pokud je součet náhodných proměnných, pravděpodobnost šíření se vyskytuje v -tém prostoru. V důsledku to snižuje účinnost IO, jak se zvyšuje (efekt rozměrnosti). $X<t$ $X$ $n$ $n$ $n$

Vysílání

Další jednoduchá a účinná technika zkreslení je založena na převodu hustoty pravděpodobnosti (a tedy náhodné proměnné) do oblasti, kde se pravděpodobnost zvyšuje. Překlady nevedou k rozměrovému efektu. Tato technika byla úspěšně aplikována v aplikacích reálného světa, jako je modelování digitálních komunikačních systémů . Často je tato metoda účinnější než škálování. Pod translačním zkreslením je nová hustota pravděpodobnosti definována jako

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

kde je hodnota posunu vybraná z podmínky minimalizace rozptylu statistik IS. $C$

Efekty složitosti systému

Základním problémem OT je obtížnost sestrojit dobrou zkreslenou distribuci, protože studovaný systém se stává složitějším. V tomto smyslu se systémy s dlouhou pamětí nazývají komplexní systémy, jelikož u systémů, kde probíhá složité zpracování malého počtu vstupních parametrů (tedy v problémech s malým rozměrem), je problém konstrukce OT jednodušší. Například v teorii digitální signalizace vede dlouhá paměť (nebo velká dimenzionalita počátečních podmínek) ke třem typům problémů:

dlouhá paměť (silná interakce mezi postavami)
paměť neurčité délky (dekodéry Viterbi)
paměť možná nekonečné délky (adaptivní ekvalizéry)

V zásadě se základní myšlenky EO při aplikaci na tyto druhy problémů nemění, ale implementace se stává mnohem komplikovanější. Úspěšnou strategií pro řešení problémů s dlouhou pamětí může být rozdělení celého problému na několik lépe definovaných částí. Poté se EOI aplikuje na každý z dílčích problémů nezávisle.

Numerické odhady SZ

Aby bylo možné určit úspěšnost nalezené hustoty IO, je užitečné mít numerický odhad snížení množství výpočtů, když je aplikována. Pro takový odhad se obvykle používá poměr , který lze interpretovat jako faktor zvyšující rychlost, se kterou bude OT statistika dosahovat stejné přesnosti jako statistika získaná obvyklou metodou Monte Carlo. Hodnotu poměru lze získat pouze empiricky, protože rozptyly statistik je téměř nemožné analyticky odvodit. $\sigma _{MC}^{2}/\sigma _{IS}^{2}$

Cenová funkce rozptylu

Rozptyl není jedinou cenovou funkcí k modelování, protože existují i jiné typy cenových funkcí, které se používají v různých statistických aplikacích, jako je střední absolutní odchylka. V literatuře se však běžně uvádí rozptyl, pravděpodobně kvůli použití rozptylu při výpočtu intervalů spolehlivosti a ve výrazu pro měření účinnosti . $\sigma _{MC}^{2}/\sigma _{IS}^{2}$

Jedním z problémů při použití rozptylu je, že poměr nadhodnocuje snížení výpočetního úsilí při použití EOI, protože tento parametr nebere v úvahu dodatečný čas potřebný k výpočtu váhové funkce. V reálné aplikaci proto musí být zlepšení vyplývající z aplikace EOI posouzeno jinými metodami. Možná závažnějším problémem z hlediska efektivity v EOI je čas na vývoj a implementaci samotné techniky a analytickou konstrukci potřebné váhové funkce (pokud není předem známa). $\sigma _{MC}^{2}/\sigma _{IS}^{2}$

Viz také

Metoda Monte Carlo
Zónové vzorkování
Rekurzivní zónové vzorkování
Sekvenční metody Monte Carlo nebo částicový filtr

Literatura

I. M. Sobol. Numerické metody Monte Carlo. M.: Nauka, 1973
PJSmith, M.Shafi a H. Gao, "Rychlá simulace: Přehled o důležitosti technik vzorkování v komunikačních systémech," IEEE J.Select.Areas Commun., sv. 15, str. 597-613, květen 1997.
M. Ferrari, S. Bellini, "Importance Sampling simulation of turbo product codes," ICC2001, The IEEE International Conference on Communications, sv. 9, str. 2773–2777, červen 2001.
Tommy Oberg, Modulation, Detection, and Coding, John Wiley & Sons, Inc., New York, 2001.
R. Srinivasan., Důležitost vzorkování. New York: Springer, 2002.

dodatečně

"Vzorkování důležitosti - Aplikace v komunikaci a detekci", Rajan Srinivasan, Springer-Verlag, Berlín, 2002.
„Úvod do simulace vzácných událostí“, James Antonio Bucklew, Springer-Verlag, New York, 2004.

Odkazy

Domovská stránka Sekvenční metody Monte Carlo (filtrování částic) na University of Cambridge
Úvod do významu vzorkování v simulacích vzácných událostí European Journal of Physics. PDF dokument.
Adaptivní metody monte carlo pro simulace vzácných událostí: adaptivní metody monte carlo pro simulace vzácných událostí Zimní simulační konference
Kuba - knihovna pro vícerozměrnou numerickou integraci