📂머신러닝

중요도 샘플링

개요¹

중요도 샘플링은 몬테카를로 방법 중 하나로, 유한합으로 적분(기댓값)을 근사할 때 사용할 수 있는 일종의 샘플링 트릭이다.

빌드업

표준정규분포에서 $z$ 값이 $4$이상일 확륙은 약 $3.167 \times 10^{-5}$이다.

$$ \begin{equation} \int_{4}^{\infty} \dfrac{1}{\sqrt{2\pi}} e^{-z^{2}/2}dz \approx 3.167 \times 10^{-5} \end{equation} $$

이 적분을 몬테카를로적분으로 계산하는 줄리아 코드는 다음과 같다.

using Distributions

n = 50000                      # sample size
z₀ = 4.0

for i in 1:5
    z = rand(Normal(), n)      # n-samples drawn from a standard normal distribution 
    est_MC = sum(z .> z₀)/n    # estmiates using Monte Carlo
    println(est_MC)
end

4.0e-5
6.0e-5
0.0
4.0e-5
4.0e-5

다섯번 정도 해보면 계산된 값이 참값과 비슷하지 않고, 심지어는 $0$으로 계산될 때도 있다. 이런 부정확함은 표준정규분포의 꼬리가 너무 얇기 때문에 생긴다. 종이 위에서 적분할 때는 꼬리가 아무리 얇아도 그에 대한 계산이 적분에 포함되지만, 컴퓨터로 샘플링할 때는 유한한 샘플만을 다루기 때문에 너무 발생확률이 낮은 사건은 계산에 포함되지 않을 수 있다. 물론 $n$을 늘리면 더 정확해질테지만 이는 너무 당연한 말이고, 이런걸 해결방법이라고 부르지는 않는다.

$$ \int f(x)p(x) dx = \int f(x)\dfrac{p(x)}{q(x)} q(x) dx = \int \left[ f(x)\dfrac{p(x)}{q(x)} \right] q(x) dx $$

이제 확률밀도함수가 $p$인 확률변수 $X$에 대해서, $f(X)$의 기댓값을 계산하는 상황을 생각해보자. 이는 위 식의 좌변과 같이 계산할 수 있는데, 여기서 어떤 $q(x)$를 나눠주고 곱해줘도 여전히 같은 값이다. 식의 우변은 좌변과 같은 값을 갖지만, 의미는 '확률밀도함수가 $q$인 확률변수 $X$에 대해서 $f(X)\dfrac{p(X)}{q(X)}$의 기댓값'이 된다. 여기서 $q$를 $p$보다 꼬리가 두꺼운 확률밀함수로 선택한다면, 발생확률이 너무 낮은 사건에 의한 부정확함을 줄일 수 있다.

정의

$X$를 확률밀도함수가 $p$인 확률변수라고 하자. $q$를 다음을 만족하는 또 다른 확률밀도함수라고 하자.

$$ \supp p \subset \supp q \qquad (\iff q\ne 0 \text{ if } p \ne 0) $$

중요도 샘플링^{importance sampling}이란 $f(X)$의 기댓값 $E_{p}[f(X)]$를 $E_{q}[f(X)\frac{p(X)}{q(X)}]$로 계산하여 구하는 방법을 말한다. 이때 $\supp$는 함수의 서포트이다.

$$ E_{p}[f] = \int f(x)p(x) dx = \int \left[ f(x)\dfrac{p(x)}{q(x)} \right] q(x) dx = E_{q}[fp/q] $$

여기서 $q$를 제안 분포^{proposal distribution}, $w = \frac{p}{q}$를 중요도 가중치^{importance weight}라고 한다.

설명

다시말해 중요도 샘플링이란 몬테카를로 적분을 다음과 같이 계산하는 것이다.

$$ \dfrac{1}{n}\sum f(x_{i})\dfrac{p(x_{i})}{q(x_{i})}, X_{i} \sim q(x) \quad \left( \text{instead of } \dfrac{1}{n}\sum f(x_{i}), X_{i} \sim p(x) \right) $$

다음과 같이 사용하면 도움이 된다.

• 빌드업에서의 예제와 같이 $p(x)$의 꼬리가 너무 얇을 때 서포트가 더 큰 분포를 제안함수로 둔다.
• $p(x)$의 분포로 샘플링 하기 어려울 때 샘플링하기 쉬운 분포를 제안함수를 $q(x)$로 둔다.

$q$가 $p$의 분모로 곱해지기 때문에 $\supp q$는 $\supp p$를 포함해야한다.

빌드업의 적분 $(1)$을 코시분포를 제안분포로 두고 중요도 샘플링으로 다시 계산한 결과는 다음과 같다.

# Julia code

using Distributions

n = 50000                      # sample size
z₀ = 4.0

for i in 1:5
    z = rand(Cauchy(), n)                       # n-samples drawn from a Cauchy distribution 
    w = pdf.(Normal(), z) ./ pdf.(Cauchy(), z)
    est_IS = sum(w[z .> z₀])/n                  # estmiates using Importance Sampling
    println(est_IS)
end

3.0330744703037005e-5
3.1808448538011614e-5
3.049259883894785e-5
3.305423127141489e-5
3.1807695818207125e-5

성질

불편추정량

$\dfrac{1}{n}\sum\limits f(x_{i})\dfrac{p(x_{i})}{q(x_{i})}$는 $E_{p}[f(X)]$의 불편추정량이다.

증명

$$ \begin{align*} E_{q}\left[ \frac{1}{n}\sum_{i}^{n}f(X_{i})\dfrac{p(X_{i})}{q(X_{i})} \right] &= \frac{1}{n}\sum_{i}^{n} E_{q}\left[ f(X_{i})\dfrac{p(X_{i})}{q(X_{i})} \right] &\text{by linearity of $E$} \\ &= E_{q}\left[ f(X)\dfrac{p(X)}{q(X)} \right] \\ &= E_{p}\left[ f(X) \right] \end{align*} $$

■

분산

중요도샘플링에서의 분산은

$$ \begin{align} \Var \left[ \frac{fp}{q} \right] &= E_{q}\left[ \left( \frac{fp}{q} \right)^{2} \right] - \left( E_{q}\left[ \frac{fp}{q} \right] \right)^{2} \\ &= \int \frac{f(x)^{2}p(x)^{2}}{q(x)} dx - \left( \int f(x)p(x) dx \right)^{2} \nonumber \end{align} $$

이므로, 유한한 분산을 갖기 위해선 다음이 성립해야한다.

$$ \int \frac{f(x)^{2}p(x)^{2}}{q(x)} dx \lt \infty $$

이는 $p(x)/q(x)$가 유계여야한다는 말이고, 이는 다시 $q(x)$의 꼬리가 $p(x)$의 꼬리보다 두꺼워야한다는 말과 같다. 분산을 최소화하는 $q$는 다음과 같다.

$$ q^{\ast} = \argmin\limits_{q} \Var [fp/q] = \frac{ \left| f(x) \right| p(x)}{ \int \left| f(x) \right| p(x) dx} $$

증명

$(2)$에서 두번째 항은 $q$에 의존하는 것처럼 보여도, $E_{q}\left[ \frac{fp}{q} \right] = {\displaystyle \int} f(x)p(x)dx$이므로 $q$와는 무관한 값이다.

$$ \argmin\limits_{q} \Var [fp/q] = \argmin\limits_{q} E_{q}\left[ \left( \frac{fp}{q} \right)^{2} \right] $$

옌센 부등식

개구간 $I$ 에서 함수 $\phi$ 가 컨벡스하고 두 번 미분가능, 확률변수 $X$ 의 기댓값 $\mu$ 가 존재하며 $X \subset I $ 면 $$ \phi [ E(X) ] \le E [ \phi (X)] $$

그런데 이차함수는 컨벡스이므로,

$$ \begin{align*} && \left( E_{q}\left[ \frac{fp}{q} \right] \right)^{2} &\le E_{q}\left[ \left( \frac{fp}{q} \right)^{2} \right] \\ \implies && \left( \int f(x)p(x) dx \right)^{2} &\le \int \frac{f(x)^{2} p(x)^{2}}{q(x)} dx \end{align*} $$

여기서 $q(x) = \frac{ \left| f(x) \right| p(x)}{ \int \left| f(x) \right| p(x) dx}$이면 등호가 성립한다.

■