16. Rejection sampling (RS) a importance sampling (IS): důvody používání RS a IS, jejich základní principy a rozdíly, efektivita práce se vzorky. Stanovení vah v IS a možnosti jejich normování. (NI-BML)

---

Rejection sampling (RS)

Rejection sampling funguje na principu "navrhování" a "přijímání/odmítání" vzorků. Máme cílovou distribuci $f(x)$, ze které chceme vzorkovat, a proposal distribuci $g(x)$, ze které umíme snadno generovat vzorky.

Klíčové podmínky

1. Proposal distribuce $g(x)$ musí být nenulová všude, kde je nenulová $f(x)$
2. Musíme najít konstantu $M$, pro kterou platí $f(x) \leq Mg(x)$ pro všechna $x$

Algoritmus

1. Vygenerujeme vzorek $y$ z proposal distribuce $g(x)$
2. Vygenerujeme náhodné číslo $u$ z rovnoměrného rozdělení $U(0,1)$
3. Přijmeme vzorek $y$, pokud $u < \frac{f(y)}{Mg(y)}$
4. Pokud není podmínka splněna, vzorek odmítneme a opakujeme proces

Efektivita metody

Efektivita RS závisí především na dvou faktorech:

1. Volba proposal distribuce: Čím lépe $g(x)$ aproximuje tvar $f(x)$, tím vyšší je pravděpodobnost přijetí vzorku
2. Konstanta M: Průměrný počet pokusů potřebných k získání jednoho platného vzorku je roven $M$

Matematika

Základní teorém vzorkování říká: Vzorkování $x \sim f(x)$ je ekvivalentní k vzorkování $(x,u) \sim U\{(x,u): 0 < u < f(x)\}$

To znamená, že:

1. Cílovou distribuci $f(x)$ můžeme chápat jako marginální hustotu sdruženého rozdělení $(x,u)$
2. Toto sdružené rozdělení je rovnoměrné na oblasti pod křivkou $f(x)$

Praktické aspekty

Výhody

• Generuje nezávislé vzorky
• Není potřeba znát normalizační konstantu cílové distribuce
• Jednoduchá implementace

Nevýhody

• Nízká efektivita při velkém $M$
• Problémy s úzkými "věžemi" v distribuci (malý rozptyl)
• Neefektivní v oblastech s velmi nízkými hodnotami hustoty

Geometrická interpretace

RS lze představit jako házení šipek na graf:

1. Házíme šipky náhodně pod křivku $Mg(x)$
2. Přijímáme pouze ty šipky, které padnou pod křivku $f(x)$
3. X-ové souřadnice přijatých šipek tvoří vzorky z cílové distribuce

Pravděpodobnost přijetí vzorku

Pravděpodobnost přijetí vzorku je rovna $\frac{1}{M}$, proto:

• Čím menší je $M$, tím efektivnější je vzorkování
• Čím lépe proposal distribuce $g(x)$ aproximuje $f(x)$, tím menší $M$ můžeme použít
• Pro efektivní vzorkování je klíčové najít dobrou kombinaci $g(x)$ a $M$

Praktické použití

RS je vhodný především pro:

• Jednoduché distribuce v nízkých dimenzích
• Případy, kdy máme dobrou proposal distribuci
• Situace, kdy potřebujeme nezávislé vzorky
• Případy, kdy není možné přímo vzorkovat z cílové distribuce

Importance Sampling (IS)

Importance sampling je pokročilá metoda Monte Carlo simulací pro efektivnější výpočet očekávaných hodnot a vzorkování z komplexních rozdělení. Místo přímého vzorkování z cílové distribuce $f(x)$ vzorkujeme z jednodušší proposal distribuce $g(x)$ a výsledky vážíme tak, abychom kompenzovali rozdíl mezi distribucemi.

Matematický základ

Očekávaná hodnota vzhledem k distribuci $f(x)$ lze přepsat jako:

$$E_f[X] = \int xf(x)dx = \int x\frac{f(x)}{g(x)}g(x)dx = \int x \cdot w(x) g(x) dx$$

kde $\frac{f(x)}{g(x)}$ představuje importance weights (váhy důležitosti) $w(x)$.

Algoritmus v detailních krocích

1. Generování vzorků

   • Vygenerujeme $n$ nezávislých vzorků $x_1,...,x_n$ z proposal distribuce $g(x)$
   • Proposal distribuce musí mít nenulovou hustotu všude, kde má nenulovou hustotu $f(x)$

2. Výpočet hodnot v cílové hustotě

   • Pro každý vzorek $x_i$ spočítáme hodnotu $f(x_i)$
   • Není nutné znát normalizační konstantu $f(x)$

3. Výpočet hodnot v proposal hustotě

   • Pro každý vzorek $x_i$ spočítáme hodnotu $g(x_i)$
   • Proposal distribuce musí být plně specifikována

4. Výpočet vah

   • Pro každý vzorek spočítáme váhu: $$w_i = \frac{f(x_i)}{g(x_i)}$$

5. Normalizace vah (Optional)

   • Normalizujeme váhy, aby jejich součet byl 1: $$\tilde{w}_i = \frac{w_i}{\sum_{j=1}^n w_j}$$

6. Odhad očekávané hodnoty

   • Finální odhad očekávané hodnoty: $$\hat{E}_f[h(X)] = \sum_{i=1}^n \tilde{w}_i h(x_i)$$

Praktické aspekty

Výhody

• Využití všech vzorků (žádné zahazování)
• Možnost zaměření na důležité oblasti distribuce
• Vhodné pro řídké události
• Redukce variance oproti standardnímu Monte Carlo

Nevýhody

• Citlivost na volbu proposal distribuce
• Riziko degenerace vah (některé váhy mohou být příliš dominantní)
• Složitější implementace než u jednoduchého Monte Carlo

Aplikace

IS se nejčastěji používá v:

1. Bayesovské statistice pro výpočet posteriorních rozdělení
2. Finančním modelování pro odhad rizika
3. Strojovém učení pro trénování modelů
4. Fyzikálních simulacích pro výpočet složitých integrálů

Sequential Importance Sampling (SIS)

Sequential Importance Sampling je rozšíření IS pro sekvenční (časové) systémy. Metoda umožňuje sekvenční odhad stavů v dynamických systémech, kde se stav systému mění v čase.

Princip fungování

1. Začínáme se sadou částic reprezentujících počáteční stav
2. Pro každý časový krok:
   • Posuneme částice do nového stavu podle modelu systému
   • Když přijde nové pozorování, upravíme váhy částic
   • Váhy říkají, jak dobře částice odpovídají pozorování
3. Výsledný odhad stavu získáme jako vážený průměr částic

Sequential Importance Resampling (SIR)

SIR, známý také jako particle filter, je vylepšením SIS metody. Hlavní rozdíl spočívá v přidání kroku resamplingu, který vytvoří nove $x_i$

Princip fungování

1. Stejný základ jako SIS
2. Navíc periodicky kontrolujeme efektivitu částic
3. Když je efektivita nízká, provedeme resampling:
   • Částice s vysokými váhami se namnoží
   • Částice s nízkými váhami zaniknou
   • Všem novým částicím dáme stejné váhy
4. Pokračujeme standardním SIS algoritmem