Jak optymalnie rozłożyć losowania przy obliczaniu wielu oczekiwań

Załóżmy, że chcemy obliczyć pewne oczekiwania:

E_{Y} E_{X | Y} [f (X, Y)]

$E_YE_{X|Y}[f(X,Y)]$

Załóżmy, że chcemy to przybliżyć za pomocą symulacji Monte Carlo.

E_{Y} E_{X | Y} [f (X, Y)] \approx \frac{1}{R S} \sum_{r = 1}^{R} \sum_{s = 1}^{S} f (x^{r, s}, y^{r})

$E_YE_{X|Y}[f(X,Y)] \approx \frac1{RS}\sum_{r=1}^R\sum_{s=1}^Sf(x^{r,s},y^r)$

ALE załóżmy, że pobieranie próbek z obu rozkładów jest kosztowne, dlatego możemy sobie pozwolić tylko na narysowanie stałej liczby $K$ .

Jak powinniśmy przydzielić $K$ ? Przykłady obejmują $K/2$ losuje do każdego rozkładu, lub skrajnie, jedno losowanie na zewnętrznym i $K-1$ wciąga wnętrze, odwrotnie itd ...

Moja intuicja mówi mi, że będzie to miało związek z wariancją / entropią rozkładów względem siebie. Załóżmy, że zewnętrzny to punkt masy, a następnie podział $K$ , który minimalizuje błąd MC byłby losowanie 1 z $Y$ i narysuj $K-1$ z $X|Y$ .

Mam nadzieję, że było to jasne.

— wolfsatthedoor
źródło

Naprawiono to dla ciebie

— wolfsatthedoor

„Vice versa” i twój komentarz do odpowiedzi @ Xi'ans wydają się wskazywać, że uważasz, że można narysować zmienną zewnętrzną więcej razy niż zmienną wewnętrzną, ale jak to może mieć sens - nie wszystkie są zewnętrzne

0

$0$ rysunki wewnętrzne są zmarnowane?

— Juho Kokkala

W porządku, chyba jedno losowanie na zewnętrznym, tak myślę. Albo możesz pomyśleć o zaprogramowaniu go, aby uratować losowanie, jak sądzę

— wilcze piętro

@robertevansanders Potwierdź, czy interpretacja twojego pytania w pierwszych dwóch zdaniach odpowiedzi Xi'ans jest poprawna

— Juho Kokkala

Tak jak powiedziałeś, tak, ale zmień y i x

— wolfsatthedoor

To bardzo interesujące pytanie, z niewielką dokumentacją w literaturze Monte Carlo, z wyjątkiem powiązania ze stratyfikacją i Rao-Blackwellisation . Jest to prawdopodobnie spowodowane faktem, że obliczenia oczekiwanej wariancji warunkowej i wariancji oczekiwanej warunku są rzadko wykonalne.

Po pierwsze, załóżmy, że biegniesz $R$ symulacje z $\pi_X$ , $x_1,\ldots,x_R$ i dla każdego symulowanego $x_r$ biegniesz $S$ symulacje z $\pi_{Y|X=x_r}$ , $y_{1r},\ldots,y_{sr}$ . Twoje szacunki Monte Carlo są wtedy

δ (R, S.) = \frac{1}{R S.} \sum_{r = 1}^{R} \sum_{s = 1}^{S.} fa (x_{r}, y_{r s})

$\delta(R,S)=\frac{1}{RS}\sum_{r=1}^R\sum_{s=1}^S f(x_r,y_{rs})$ Wariancja tego oszacowania jest rozkładana w następujący sposób

\begin{aligned} var {δ (R, S.)} & = \frac{1}{R^{2)} {S.}^{2)}} R var {\sum_{s = 1}^{S.} fa (x_{r}, y_{r s})} \\ = \frac{1}{R {S.}^{2)}} {var}_{X} {mi}_{Y | X} {\sum_{s = 1}^{S.} fa (x_{r}, y_{r s}) | x_{r}} + \frac{1}{R {S.}^{2)}} {mi}_{X} {var}_{Y | X} {\sum_{s = 1}^{S.} fa (x_{r}, y_{r s}) | x_{r}} \\ = \frac{1}{R {S.}^{2)}} {var}_{X} {S. {mi}_{Y | X} [fa (x_{r}, Y) | x_{r}]} + \frac{1}{R {S.}^{2)}} {mi}_{X} [S. {var}_{Y | X} {fa (x_{r}, Y) | x_{r}}] \\ = \frac{1}{R} {var}_{X} {{mi}_{Y | X} [fa (x_{r}, Y) | x_{r}]} + \frac{1}{R S.} {mi}_{X} [{var}_{Y | X} {fa (x_{r}, Y) | x_{r}}] \\ \overset{K. = R S.}{=} \frac{1}{R} {var}_{X} {{mi}_{Y | X} [fa (x_{r}, Y) | x_{r}]} + \frac{1}{K.} {mi}_{X} [{var}_{Y | X} {fa (x_{r}, Y) | x_{r}}] \end{aligned}

$\begin{align*} \text{var} \{\delta(R,S)\} &= \frac{1}{R^2S^2} R\text{var} \left\{\sum_{s=1}^S f(x_r,y_{rs})\right\}\\ &= \frac{1}{RS^2} \text{var}_X\mathbb{E}_{Y|X}\left\{\sum_{s=1}^S f(x_r,y_{rs})\big|x_r\right\}+\frac{1}{RS^2}\mathbb{E}_{X}\text{var}_{Y|X} \left\{\sum_{s=1}^S f(x_r,y_{rs})\big|x_r\right\}\\ &=\frac{1}{RS^2} \text{var}_X\{ S \mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{RS^2} \mathbb{E}_{X}[S\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]\\ &=\frac{1}{R} \text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{RS} \mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]\\ &\stackrel{K=RS}{=}\frac{1}{R}\text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{K} \mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}] \end{align*}$ Dlatego jeśli chcemy zminimalizować tę wariancję, optymalnym wyborem jest

R = K

$R=K$ . Implikując to

S = 1

$S=1$ . Z wyjątkiem sytuacji, gdy pierwszy warunek wariancji jest zerowy, w którym to przypadku nie ma to znaczenia. Jednak, jak omówiono w komentarzach, założenie

K = R S

$K=RS$ jest nierealne, ponieważ nie uwzględnia produkcji jednego

x_{r}

$x_r$ [lub zakłada, że jest to bezpłatne].

Przyjmijmy teraz różne koszty symulacji i ograniczenie budżetowe $R+aRS=b$ , co oznacza, że $y_{rs}$ koszt $a$ razy więcej do symulacji niż $x_r$ „s. Tak więc powyższy rozkład wariancji

\frac{1}{R} {var}_{X} {E_{Y | X} [f (x_{r}, Y) | x_{r}]} + \frac{1}{R (b - R) / a R} E_{X} [{var}_{Y | X} {f (x_{r}, Y) | x_{r}}]

$\frac{1}{R}\text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}+ \frac{1}{R(b-R)/aR} \mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]$ które można zminimalizować w

R

$R$ tak jak

R^{*} = b / 1 + {a E_{X} [{var}_{Y | X} {f (x_{r}, Y) | x_{r}} / {var}_{X} {E_{Y | X} [f (x_{r}, Y) | x_{r}]}}^{1 / 2}

$R^*=b\big/1+\{a\mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}/\text{var}_X\{\mathbb{E}_{Y|X}[f(x_r,Y)|x_r]\}\}^{1/2}$ [najbliższa liczba całkowita pod ograniczeniami

R \geq 1

$R\ge 1$ i

S \geq 1

$S\ge 1$ ], z wyjątkiem sytuacji, gdy pierwsza wariancja jest równa zero, w którym to przypadku

R = 1

$R=1$ . Kiedy

E_{X} [{var}_{Y | X} {f (x_{r}, Y) | x_{r}}] = 0

$\mathbb{E}_{X}[\text{var}_{Y|X}\{f(x_r,Y)|x_r\}]=0$ , minimalna wariancja odpowiada maksimum

R

$R$ , który prowadzi do

S = 1

$S=1$ w obecnym formalizmie.

Należy również zauważyć, że to rozwiązanie należy porównać z rozwiązaniem symetrycznym, gdy jest wbudowana całka wewnętrzna $X$ dany $Y$ a całka zewnętrzna jest przeciwna do marginesu w $Y$ (zakładając, że symulacje są również wykonalne w tej kolejności).

Ciekawym rozszerzeniem tego pytania byłoby rozważenie innej liczby symulacji $S(x_r)$ dla każdego symulowanego $x_r$ , w zależności od wartości $\text{var}_{Y|X}\{f(x_r,Y)|x_r\}$ .

— Xi'an
źródło

Ostatecznie wydaje się, że zakładasz

K = R S

$K=RS$ ale w kontekście pytania

K = R S + R

$K=RS+R$ ponieważ należy również liczyć losowania zmiennej zewnętrznej. Wynik tutaj mówi, że jeśli próbkowanie zewnętrznej zmiennej było dowolne, oczywiście należy próbkować nową zewnętrzną dla każdego wewnętrznego. (Również rola

x

$x$ i

y

$y$ są tu zamieniane w porównaniu do pytania, ale to oczywiście nie ma znaczenia).

— Juho Kokkala,

Tak, ale możemy zdecydować o wartości

R

$R$ ... Rozważ zdegenerowane ustawienie, w którym zmienna zewnętrzna

X

$X$ jest tak samo stały. Lepiej próbkować stałą raz i

Y

$Y$

K - 1

$K-1$ razy zamiast stałej

K / 2

$K/2$ czasy i

Y

$Y$

K / 2

$K/2$ razy (co jest co

S = 1

$S=1$ to oznaczałoby)? Czy też całkowicie nie rozumiem pytania? (Dopiero teraz czytam drugie zdanie twojego komentarza - czy w pytaniu nie podano założenia, że mają one taki sam koszt)

— Juho Kokkala

@ Xi'an tak Kalkuta jest poprawna, twoje rozwiązanie ogólnie nie może się utrzymać. Załóżmy teraz, że zmienna wewnętrzna ma rozkład zdegenerowany, a zewnętrzna ma znaczącą wariancję, a następnie chcesz

— wypróbować

Myślę, że twoja odpowiedź nie może być poprawna. Załóżmy, że wewnętrzny rozkład jest zdegenerowany, a na zewnątrz duża wariancja, jak S może być 1

— wolfsatthedoor

@robertevansanders: jeśli rozkład wewnętrzny jest zdegenerowany,

{var}_{Y | X} {f (x_{r}, Y) | x_{r}} = 0

$\text{var}_{Y|X}\{f(x_r,Y)|x_r\}=0$ , W związku z tym

R^{*} = b

$R^*=b$ i wybieramy najbliższą liczbę całkowitą

R

$R$ pod ograniczeniami

S \geq 1

$S\ge 1$ i

R (1 + a S) \leq b

$R(1+aS)\le b$ , co oznacza branie

S = 1

$S=1$ robić

R

$R$ tak blisko, jak to możliwe

b

$b$ .

— Xi'an