Vzorkování důležitosti - Importance sampling

v statistika, vzorkování důležitosti je obecná technika pro odhad vlastností konkrétního rozdělení, přičemž má pouze vzorky generované z jiné distribuce, než je zájmová distribuce. Souvisí to s vzorkování deštníku v výpočetní fyzika. V závislosti na aplikaci může termín odkazovat na proces vzorkování z této alternativní distribuce, proces odvození nebo obojí.

Základní teorie

Nechat ${ displaystyle X: Omega to mathbb {R}}$ být náhodná proměnná v některých pravděpodobnostní prostor ${ displaystyle ( Omega, { mathcal {F}}, P)}$. Chceme odhadnout očekávaná hodnota z X pod P, označeno E[X; P]. Pokud máme statisticky nezávislé náhodné vzorky ${ displaystyle x_ {1}, ldots, x_ {n}}$, generované podle P, pak empirický odhad E[X; P] je

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

a přesnost tohoto odhadu závisí na rozptylu X:

${ displaystyle operatorname {var} [{ widehat { mathbf {E}}} _ {n}; P] = { frac { operatorname {var} [X; P]} {n}}.}$

Základní myšlenkou vzorkování důležitosti je vzorkování stavů z jiného rozdělení, aby se snížila rozptyl odhadu E[X; P], nebo když je vzorkování z P obtížné. Toho je dosaženo nejprve výběrem náhodné proměnné ${ displaystyle L geq 0}$ takhle E[L;P] = 1 a to P-téměř všude ${ displaystyle L ( omega) neq 0}$. S variací L definujeme pravděpodobnost ${ displaystyle P ^ {(L)}}$ to uspokojuje

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

Proměnná X/L budou tedy odebrány vzorky pod P^(L) odhadovat E[X; P] jak je uvedeno výše a tento odhad je vylepšen, když${ displaystyle operatorname {var} left [{ frac {X} {L}}; P ^ {(L)} right] < operatorname {var} [X; P]}$.

Když X je konstantní znaménko nad Ω, nejlepší proměnná L by jasně byl ${ displaystyle L ^ {*} = { frac {X} { mathbf {E} [X; P]}} geq 0}$, aby X/L* je hledaná konstanta E[X; P] a jeden vzorek pod P^(L*) stačí dát svou hodnotu. Tuto volbu bohužel nemůžeme přijmout, protože E[X; P] je přesně ta hodnota, kterou hledáme! Tento teoretický nejlepší případ L * dává nám nahlédnout do toho, jak důležité je vzorkování:

${ 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) [6 bodů ] & = { frac {1} {E [X; P]}} ; a , P (X v [a; a + da]) end {zarovnáno}}}$

doprava, ${ displaystyle a , P (X v [a; a + da])}$ je jedním z nekonečně malých prvků, které dohromady tvoří E[X;P]:

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

proto dobrá změna pravděpodobnosti P^(L) v důležitosti vzorkování přerozdělí zákon z X tak, aby frekvence jeho vzorků byly tříděny přímo podle jejich hmotnosti v E[X;P]. Odtud název „vzorkování důležitosti“.

Vzorkování důležitosti se často používá jako a Integrátor Monte Carlo.Když ${ displaystyle P}$ je rovnoměrné rozdělení a ${ displaystyle Omega = mathbb {R}}$, E[X; P] odpovídá integrálu skutečné funkce ${ displaystyle X: mathbb {R} do mathbb {R}}$.

Aplikace na pravděpodobnostní závěr

Takové metody se často používají k odhadu zadních hustot nebo očekávání ve stavových a / nebo problémových odhadech parametrů v pravděpodobnostních modelech, které je příliš těžké analyticky zpracovat, například v Bayesovské sítě.

Aplikace na simulaci

Vzorkování důležitosti je redukce rozptylu technika, kterou lze použít v Metoda Monte Carlo. Myšlenkou vzorkování důležitosti je, že určité hodnoty vstupu náhodné proměnné v simulace mají větší dopad na odhadovaný parametr než ostatní. Pokud jsou tyto "důležité" hodnoty zdůrazněny častějším vzorkováním, pak odhadce rozptyl lze snížit. Základní metodikou vzorkování důležitosti je tedy výběr distribuce, která „podporuje“ důležité hodnoty. Toto použití „zkreslených“ distribucí bude mít za následek zkreslený odhad, pokud se použije přímo v simulaci. Simulační výstupy jsou však váženy tak, aby korigovaly použití předpjatého rozdělení, což zajišťuje, že nový odhad vzorkování důležitosti je nestranný. Hmotnost je dána míra pravděpodobnosti, toto je Derivát Radon – Nikodym skutečné podkladové distribuce s ohledem na distribuci simulovaného předpětí.

Základním problémem při implementaci simulace vzorkování důležitosti je volba předpjatého rozdělení, které podporuje důležité oblasti vstupních proměnných. Výběr nebo návrh dobré předpojaté distribuce je „uměním“ vzorkování důležitosti. Odměnou za dobrou distribuci mohou být obrovské úspory za běhu; pokutou za špatnou distribuci může být delší doba běhu než u obecné simulace Monte Carlo bez vzorkování důležitosti.

Zvážit ${ displaystyle X}$ být vzorkem a ${ displaystyle { frac {f (X)} {g (X)}}}$ být poměr pravděpodobnosti, kde ${ displaystyle f}$ je funkce hustoty (hmotnosti) pravděpodobnosti požadovaného rozdělení a ${ displaystyle g}$ je funkce hustoty (hmotnosti) pravděpodobnosti předpětí / návrh / rozdělení vzorku. Poté lze problém charakterizovat výběrem distribuce vzorku ${ displaystyle g}$ který minimalizuje rozptyl zmenšeného vzorku:

${ displaystyle g ^ {*} = min _ {g} operatorname {var} _ {g} left (X { frac {f (X)} {g (X)}} right).}$

Je možné ukázat, že následující distribuce minimalizuje výše uvedenou odchylku:^[1]

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

Všimněte si, že když ${ displaystyle X geq 0}$, tato varianta bude 0.

Matematický přístup

Zvažte odhad pravděpodobnosti pomocí simulace ${ displaystyle p_ {t} ,}$ události ${ displaystyle X geq t}$, kde ${ displaystyle X}$ je náhodná proměnná s rozdělení ${ displaystyle F}$ a funkce hustoty pravděpodobnosti ${ displaystyle f (x) = F '(x) ,}$, kde prvočíslo označuje derivát. A ${ displaystyle K}$-délka nezávislé a identicky distribuované (i.i.d.) sekvence ${ displaystyle X_ {i} ,}$ je generován z distribuce ${ displaystyle F}$a číslo ${ displaystyle k_ {t}}$ náhodných proměnných, které leží nad prahovou hodnotou ${ displaystyle t}$ se počítají. Náhodná proměnná ${ displaystyle k_ {t}}$ je charakterizován Binomická distribuce

${ displaystyle P (k_ {t} = k) = {K vybrat k} p_ {t} ^ {k} (1-p_ {t}) ^ {Kk}, , quad quad k = 0, 1, tečky, K.}$

Jeden to může ukázat ${ displaystyle operatorname {E} [k_ {t} / K] = p_ {t}}$, a ${ displaystyle operatorname {var} [k_ {t} / K] = p_ {t} (1-p_ {t}) / K}$, takže v limitu ${ displaystyle K do infty}$ jsme schopni získat ${ displaystyle p_ {t}}$. Rozptyl je nízký, pokud ${ displaystyle p_ {t} přibližně 1}$. Vzorkování důležitosti se týká stanovení a použití funkce alternativní hustoty ${ displaystyle f _ {*} ,}$(pro ${ displaystyle X}$), který se pro simulační experiment obvykle označuje jako hustota předpětí. Tato hustota umožňuje událost ${ displaystyle {X geq t }}$ se vyskytují častěji, takže délka sekvence ${ displaystyle K}$ se zmenšuje pro daný odhadce rozptyl. Alternativně pro daný ${ displaystyle K}$, použití hustoty předpětí má za následek menší rozptyl než u konvenčního odhadu Monte Carlo. Z definice ${ displaystyle p_ {t} ,}$, můžeme představit ${ displaystyle f _ {*} ,}$ jak je uvedeno níže.

${ 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 {zarovnáno }}}$

kde

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

je poměr pravděpodobnosti a označuje se jako váhová funkce. Poslední rovnost ve výše uvedené rovnici motivuje odhadce

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

Toto je odhad důležitosti vzorkování ${ displaystyle p_ {t} ,}$ a je nezaujatý. To znamená, že postup odhadu má generovat i.i.d. vzorky z ${ displaystyle f _ {*} ,}$ a pro každý vzorek, který přesahuje ${ displaystyle t ,}$, je odhad zvýšen o váhu ${ displaystyle W ,}$ hodnocena na hodnotě vzorku. Výsledky jsou zprůměrovány ${ displaystyle K ,}$ pokusy. Rozptyl odhadu vzorkování důležitosti se snadno ukazuje být

${ displaystyle { begin {aligned} operatorname {var} _ {*} { widehat {p}} _ {t} & = { frac {1} {K}} operatorname {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} right } end {zarovnáno}}}$

Nyní se problém vzorkování důležitosti zaměřuje na nalezení hustoty předpětí ${ displaystyle f _ {*} ,}$ taková, že rozptyl odhadu výběru důležitosti je menší než rozptyl obecného odhadu Monte Carlo. U některé funkce hustoty předpětí, která minimalizuje rozptyl a za určitých podmínek ji snižuje na nulu, se nazývá funkce optimální hustoty předpětí.

Konvenční metody předpětí

Ačkoli existuje mnoho druhů metod předpětí, v aplikacích vzorkování důležitosti se nejčastěji používají následující dvě metody.

Škálování

Přesouvání hmoty pravděpodobnosti do oblasti události ${ displaystyle {X geq t }}$ pozitivním měřítkem náhodné proměnné ${ displaystyle X ,}$ s číslem větším než jednota má za následek zvýšení rozptylu (střední hodnoty) funkce hustoty. To má za následek těžší ocas hustoty, což vede ke zvýšení pravděpodobnosti události. Škálování je pravděpodobně jednou z prvních známých metod předpětí, která se v praxi značně používá. Je jednoduché jej implementovat a obvykle poskytuje konzervativní zisky simulace ve srovnání s jinými metodami.

Při důležitém vzorkování pomocí škálování je jako hustotní funkce zvolené škálované náhodné proměnné zvolena hustota simulace ${ displaystyle aX ,}$, kde obvykle ${ displaystyle a> 1}$ pro odhad pravděpodobnosti ocasu. Transformací

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

a funkce vážení je

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

Zatímco škálování posune pravděpodobnostní hmotu do požadované oblasti události, také posune hmotu do doplňkové oblasti ${ displaystyle X$ což je nežádoucí. Li ${ displaystyle X ,}$ je součet ${ displaystyle n ,}$ náhodné veličiny, šíření hmoty probíhá v an ${ displaystyle n ,}$ dimenzionální prostor. Důsledkem toho je klesající důležitost zisku vzorkování pro zvýšení ${ displaystyle n ,}$a nazývá se efekt rozměrnosti. Moderní verzí vzorkování důležitosti pomocí škálování je např. takzvaný sigma-scaled sampling (SSS), který spouští více analýz Monte Carlo (MC) s různými měřítkovými faktory. Na rozdíl od mnoha jiných metod odhadu vysokého výtěžku (jako jsou nejhorší vzdálenosti WCD) SSS příliš netrpí problémem s dimenzionálností. Také adresování více MC výstupů nezpůsobuje žádné snížení účinnosti. Na druhou stranu, jako WCD, SSS je určen pouze pro gaussovské statistické proměnné a na rozdíl od WCD není metoda SSS navržena tak, aby poskytovala přesné statistické rohy. Další nevýhodou SSS je, že provoz MC s velkými měřítky může být obtížný, například G. kvůli problémům s konvergencí modelu a simulátoru. Navíc v SSS čelíme silnému kompromisu zkreslení odchylky: Pomocí faktorů velkého měřítka získáme docela stabilní výsledky výnosu, ale čím větší jsou faktory měřítka, tím větší je chyba zkreslení. Pokud na výhodách SSS při aplikaci zájmu příliš nezáleží, pak jsou často efektivnější jiné metody.

Překlad

Další jednoduchá a účinná technika předpětí využívá překlad funkce hustoty (a tedy náhodné proměnné) k umístění velké části své pravděpodobnostní hmoty do oblasti vzácných událostí. Překlad netrpí efektem rozměrnosti a byl úspěšně použit v několika aplikacích týkajících se simulace digitální komunikace systémy. Často poskytuje lepší simulační zisky než škálování. Při předpětí předpětí je hustota simulace dána vztahem

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

kde ${ displaystyle c ,}$ je míra posunu a je třeba ji zvolit, aby se minimalizovala odchylka odhadu výběru důležitosti.

Účinky složitosti systému

Zásadním problémem vzorkování důležitosti je, že navrhování dobrých předpjatých distribucí se s rostoucí složitostí systému komplikuje. Složité systémy jsou systémy s dlouhou pamětí, protože složitější zpracování několika vstupů je mnohem snazší. Tato rozměrnost nebo paměť může způsobit problémy třemi způsoby:

• dlouhá paměť (těžká interference mezi symboly (ISI))
• neznámá paměť (Dekodéry Viterbi )
• možná nekonečná paměť (adaptivní ekvalizéry)

V zásadě zůstávají myšlenky na vzorkování důležitosti v těchto situacích stejné, ale design se stává mnohem obtížnějším. Úspěšný přístup k boji proti tomuto problému spočívá v zásadním rozdělení simulace na několik menších, ostře definovaných dílčích problémů. Poté se používají strategie vzorkování důležitosti k cílení na každý z jednodušších dílčích problémů. Příkladem technik, jak tuto simulaci rozebrat, je kondicionování a simulace chybových událostí (EES) a regenerativní simulace.

Variační nákladová funkce

Rozptyl není jediný možný nákladová funkce pro simulaci a další nákladové funkce, jako je průměrná absolutní odchylka, se používají v různých statistických aplikacích. Varianta je nicméně primární nákladovou funkcí, kterou se v literatuře věnujeme, pravděpodobně kvůli použití odchylek v intervaly spolehlivosti a v měřítku výkonu ${ displaystyle sigma _ {MC} ^ {2} / sigma _ {IS} ^ {2} ,}$.

Přidruženým problémem je skutečnost, že poměr ${ displaystyle sigma _ {MC} ^ {2} / sigma _ {IS} ^ {2} ,}$ nadhodnocuje úspory za běhu kvůli vzorkování důležitosti, protože nezahrnuje další výpočetní čas potřebný k výpočtu funkce hmotnosti. Někteří lidé proto hodnotí zlepšení čistého běhu různými způsoby. Snad vážnějším režijním vzorkováním důležitosti je čas potřebný k vytvoření a naprogramování techniky a analytickému odvození požadované váhové funkce.

Viz také

• Metoda Monte Carlo
• Redukce odchylky
• Stratifikovaný odběr vzorků
• Rekurzivní stratifikovaný odběr vzorků
• Algoritmus VEGAS
• Filtr částic - postupná metoda Monte Carlo, která využívá vzorkování důležitosti
• Pomocné pole Monte Carlo
• Odmítnutí vzorkování
• Variabilní datový tok - společná zvuková aplikace vzorkování důležitosti

Poznámky

Reference

• Arouna, Bouhari (2004). „Adaptivní metoda Monte Carlo, technika snižování odchylek“. Metody Monte Carlo a jejich aplikace. 10 (1): 1–24. doi:10.1515/156939604323091180.
• Bucklew, James Antonio (2004). Úvod do simulace vzácných událostí. New York: Springer-Verlag.
• Doucet, A .; de Freitas, N .; Gordon, N. (2001). Postupné metody Monte Carlo v praxi. Springer. ISBN  978-0-387-95146-1.
• Ferrari, M .; Bellini, S. (2001). Simulace vzorkování důležitosti kódů produktů turbo. Mezinárodní konference o komunikacích IEEE. 9. 2773–2777. doi:10.1109 / ICC.2001.936655. ISBN  978-0-7803-7097-5.
• Mazonka, Oleg (2016). „Easy as Pi: The Importance Sampling Method“ (PDF). Referenční deník. 16.
• Oberg, Tommy (2001). Modulace, detekce a kódování. New York: John Wiley & Sons.
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Oddíl 7.9.1 Vzorkování důležitosti“. Numerické recepty: Umění vědecké práce na počítači (3. vyd.). New York: Cambridge University Press. ISBN  978-0-521-88068-8.
• Ripley, B. D. (1987). Stochastická simulace. Wiley & Sons.
• Smith, P. J .; Shafi, M .; Gao, H. (1997). "Rychlá simulace: Přehled technik vzorkování důležitosti v komunikačních systémech". IEEE Journal on Selected Areas in Communications. 15 (4): 597–613. doi:10.1109/49.585771.
• Srinivasan, R. (2002). Vzorkování důležitosti - Aplikace v komunikaci a detekci. Berlín: Springer-Verlag.

externí odkazy

• Postupné metody Monte Carlo (filtrování částic) domovská stránka University of Cambridge
• Úvod do vzorkování důležitosti v simulacích vzácných událostí Evropský časopis fyziky. PDF dokument.
• Adaptivní metody Monte Carlo pro simulaci vzácných událostí: Adaptivní metody Monte Carlo pro simulace vzácných událostí Konference o zimní simulaci