[Sampling] Importance Sampling

 

Motivation

여태 샘플링 기법을 배운 이유는, 기댓값을 계산(혹은 근사)하기 위한 단계였다.

\[ \mathbb{E}_{p(x)}[f(x)] \approx \cfrac{1}{m}\sum_{s=1}^{m} f(x_s), \quad x_1, \dots, x_m \overset{\text{i.i.d.}}{\sim} p(x) \]

 

그렇다면, 샘플링 없이 $p(x)$로부터 직접 기댓값을 구할 수 있는 방법은 없을까?

 

Importance Sampling (IS)

Method

$q(x)$는 proposal distribution으로 샘플링이 쉬운 분포라 하자.

그리고 $q(x)=0$이면 $p(x)=0$이고, $q(x) \neq 0$이면 역시 $p(x) \neq 0$라 하자. (비율을 정의하기 위함)

그러면 기댓값은 다음과 같이 계산할 수 있다.

\[ \mu := \mathbb{E}_{p(x)}[f(x)] = \int f(x)p(x) dx = \int f(x) \cfrac{p(x)}{q(x)} q(x) dx \]

 

Monte Carlo approximation에 의하여 다음이 성립한다.

\[ \mathbb{E}_{p(x)}[f(x)] \approx \cfrac{1}{m}\sum_{s=1}^{m} \omega(x_s)f(x_s) \]

이때 $x_1, \dots, x_m \overset{\text{i.i.d.}}{\sim} q(x), \quad \omega(x_s) := \cfrac{p(x_s)}{q(x_s)}$ 이다.

$\omega(x_s)$는 importance weight라고 부른다.

 

다시 원래 식으로 돌아와서, 이들의 계산 결과는 같지만 각 의미는 다르다.

\[ \mu := \mathbb{E}_{p(x)}[f(x)] = \int f(x)p(x) dx = \int f(x) \cfrac{p(x)}{q(x)} q(x) dx \]

시작은 기댓값의 정의로부터 $p(x)$의 표본의 기댓값이지만, $q(x)$로 나누는 조작을 통해 3번째 식의 의미는 $q(x)$로부터 추출된 확률변수 $\frac{p(x)}{q(x)}$의 기댓값이다.

Bias and Variance

importance sampling으로 얻은 기댓값을 $\mu_{\text{IS}}$라 하자. 즉

\[ \mu_{\text{IS}} := \cfrac{1}{m} \]

 

\[ \mathbb{E}[\mu_{\text{IS}}] = \cfrac{1}{m} \sum_{s=1}^{m} \mathbb{E}_{q(x_s)}[\omega(x_s)f(x_s)] = \mu \]

따라서 $\mu_{\text{IS}}$ 는 unbiased 이다.

 

또한 분산은 다음과 같다.

\[ \text{Var}(\mu_{\text{IS}}) = \cfrac{1}{m}\mathbb{E}_{q(x)}[(\omega(x)f(x) - \mu)^2] \]

 

Self-normalized Importance Sampling (SIS)

rejection sampling의 도입부처럼, 우리는 $p(x)$는 알지 못하고 대신에 정규화되지 않은 분포 $\tilde{p}(x)$만 알고 있는 경우에도 importance sampling을 적용해보자.

 

아이디어는 $Z$를 근사시키는 것이다.

\[ Z = \int \tilde{p}(x) dx = \int \cfrac{\tilde{p}(x)}{q(x)} q(x) dx \approx \cfrac{1}{m}\sum_{s=1}^{m} \omega(x_s) \]

이때 $x_1, \dots, x_m \overset{\text{i.i.d.}}{\sim} q(x)$이고, $\omega(x_s):= \cfrac{\tilde{p}(x_s)}{q(x_s)}$ 이다.

 

이렇게 얻은 $Z$를 이용하여 기댓값(의 근삿값)을 구하면 다음과 같다.

\[ \mathbb{E}_{p(x)}[f(x)] = \cfrac{1}{Z} \int f(x) \cfrac{\tilde{p}(x)}{q(x)}q(x) dx \approx \sum_{s=1}^{m} \bar{\omega}(x_s) f(x_s) \]

이때 $\bar{\omega}(x_s):= \cfrac{\omega(x_s)}{\sum_{t=1}^{m} \omega(x_t)}$ 이다.

 

$\mu_{\text{SIS}}$ is biased estimator

$\mu_{\text{SIS}} = \sum_{s=1}^{m} \bar{\omega}(x_s)f(x_s)$에서 

\[ \mathbb{E}[\mu_{\text{SIS}}] = \mathbb{E} \left[ \cfrac{\sum_{s=1}^{m} \omega(x_s)f(x_s) }{\sum_{s=1}^{m} \omega(x_s)} \right] \neq \cfrac{\mathbb{E}\left[ \sum_{s=1}^{m} \omega(x_s)f(x_s) \right]}{\mathbb{E} [\sum_{s=1}^{m}\omega(x_s)]} \]

이므로 biased estimator for $\mu$ 이다.

 

그렇지만 큰수의 법칙에 따라 $\mu_{\text{SIS}} \overset{p}{\to} \mu$ 이므로 consistent estimator이다.

Sampling importance resampling (SIR)

IS와 SIS 모두 샘플링을 $q(x)$에서 했다. 그래도 여전히 $p(x) = \tilde{p}(x) / Z$로부터 샘플링하고싶다면?

 

sampling importance resampling (SIR)은 $q(x)$로부터 $[\omega(x_1), \dots, \omega(x_m)]$의 확률로 resample하는 기법이다.

 

$s \sim \text{Cat}(\bar{\omega}(x_1), \dots, \bar{\omega}(x_m))$이고 $\hat{x} = x_s$라 하면

\[ F_{\hat{x}}(y) = \cfrac{\sum_{s=1}^{m} \mathbb{1}_{ \{ x_s \le y \} }\omega(s_x)}{\sum_{s=1}^{m} \omega(x_s)} = \cfrac{\int \mathbb{1}_{ \{ x_s \le y \} } \tilde{p}(x) dx}{\int \tilde{p}(x) dx} = F_x(y) \]