Montecarlo integration & importance sampling

참고1 참고2

결론

• pdf에서 draw가 쉽고, 적분도 쉬우면 -> 그냥 적분한다.
• pdf에서 draw는 쉬운데 적분이 어려우면 -> MC Integration
• pdf에서 draw도 어려우면 -> importance sampling

Law of Large Numbers(LLN 또는 큰 수의 법칙)

어떤 Random Variable에서 샘플한 $Y_1, Y_2, … , Y_n$이 존재하며, $\bar{Y}_n=\frac{1}{n}\sum_{i=1}^{n}Y_i$ $E(Y_i)=\mu$ 라고 하면, 모든 $\epsilon > 0$에 대해

Monte Carlo Integration

Monte Carlo 방법은 확률적 적분의 형태이며, 큰 수의 법칙을 이용해 기대값의 근사치를 얻는데 쓰인다. 쉽게보면 잘 모르겠으면 무작정 샘플링해서 경험적으로 확률을 추출하겠다는 것이지만, 계산을 위한 트릭들이 들어간다. 다음은 그런 트릭에 관한 설명이다.

• 여기서 $f(y)$는 uniform(a, b) pdf를 의미한다.
• 큰 수의 법칙에 따라, 우리가 U(a,b)에서 N개의 iid sample를 갖는다면, I를 다음처럼 추정할 수 있다. $\hat{I} = \frac{1}{N}\sum_{i=1}^{N}w(Y_i) \rightarrow E(w(Y))\ =\ I$

###예제 문제: $F_Y(y) = P(Y \le y)=E[I_{(-\infty, y)}(Y)]$이며 $Y \sim N(0, 1)$ 일 때 $F_Y(y)$를 추정하라.

풀이법: (1) 이렇게 식을 바꾸자!

아무래도 문제의 $E[I_{(-\infty, y)}(Y)]$는 어떤 말인지 모르겠다…

(2) 이제 N개의 샘플을 $N(0, 1)$에서 막 뽑는다!

(3) 끄읕.

내 생각

MC Integration의 실용적인 경우는 pdf는 알 수 있으나, 적분이 힘든 경우일 것 같다. 인데 바로 다음 챕터에 나오네..

Importance Sampling

동기

MC Integration은 target distribution에서 sample이 가능할 경우 굉장히 유용하다. 근데 심지어 target에서 sample이 불가능하면 어떻게 하나?

Idea

그냥 어떤 distribution을 제안하고, integral을 importance weight를 사용해 reweight한다.

그냥 $g(y)$로 나누는걸 말하는 듯 하다..

• h 는 어떤 함수이며, f는 Y의 pdf이다.
• f에서 sampling하기 힘들면, Importance sampling을 쓸 수 있다.
• f에서 뽑지 말고, 다른 pdf g를 가지고 뽑자

요렇게 되면 이제 다음처럼 $g$에서 샘플링 가능하다.

주의사항 : 추정치 $\hat{I}$의 standard eror $E_g\left [\left (\frac{h(Y)f(Y)}{g(Y)}\right )^2\right ]$는 무한대가 될 수 있다. $\int \left (\frac{h(y)f(y)}{g(y)}\right )^2g(y)dy$에서 $f(y) \ne 0, g(y) = 0$인 $y$가 존재한다면… 따라서 $g$를 $f$와 비슷한 형태로 선택하되 tail이 더 긴 녀석으로 선택해야함!

예제

$N(0, 1)$에서 $[2, 3]$부분만 truncate한 pdf를 만들고 그것의 평균값을 simulation하고 싶다고 가정하자. 즉 구하고 싶은 것은

$N(0, 1)$의 pdf를 $\phi$로 쓴다.

1. 무작정 draw: $x_i$를 $N(0, 1)$에서 계속 draw를 하고, $\frac{\sum_i x_i \cdot \mathbb{1}(x_i \in [2, 3])}{\sum_i \mathbb{1}(x_i \in [2, 3])}$ 를 구한다. $[2, 3]$구간에서 draw될 확률이 적기 때문에, 대부분의 sample을 버려야한다.

2. Importance sampling:

   • (1)을 다음처럼 바꾼다.
     $\int_2^3 x\frac{\phi(x)}{\int_2^3\phi(y)dy}dx = \int_2^3 x\frac{\phi(x)}{\int_2^3\phi(y)dy\cdot h(x)} \cdot h(x)\ dx\ \ \ \ \ \ \ (2)$
     
     $h(x)=\left\{\begin{matrix} 1& 2 < x < 3\\ 0& otherwise \end{matrix}\right.$

     $h(t)$는 $U[2,3]$의 pdf이며, 따라서 식 (2)의 중간에 있는 분수꼴이 importance weight가 된다.

• $U[2, 3]$에서 draw한다. importance weight는 $w_i=f(w_i)=\frac{\phi(x_i)}{\int_2^3 \phi(y)dy}$ 이며, simulated mean은 $\frac{1}{N}\sum_{i=1}^N x_i \cdot w_i$ 이며 버려지는 sample은 하나도 없다!