[Sampling] Rejection Sampling

 

Rejection Sampling

Introduction

이제 샘플링 할 분포가 간단한 분포함수가 아니고 매우 복잡한 분포라고 하자. 심지어 적분도 쉽지 않다면 정규화 상수도 구할 수 없다.

베이지안으로 예를 들면, posterior를 계산할 때 이런일이 발생한다.

\[ p(\theta | X) = \cfrac{p(X | \theta) p(\theta)}{p(X)} \]

이때 분모의 $p(X)$는 marginal을 구하는 것인데 $p(X) = \int p(X, \theta) d \theta$를 구하는 것은 많은 경우에 불가능하다.

 

일반적인 notation으로, 우리가 알고 있는 분포(PDF가 아니어도 된다.)를 $\tilde{p}(x)$라 하고, 적분값이 $1$이 되도록하는 정규화상수를 $Z$라 한다. 이때 target distribution으로 $p(x)$라 한다.

\[ p(x) = \cfrac{\tilde{p}(x)}{Z}, \quad Z = \int \tilde{p}(x) dx \]

※ $\tilde{p}(x)$ 를 unnormalized target distribution이라고도 한다.

 Setting

proposal distribution(제안 분포) $q(x)$를 도입하여 해결할 것이다. 이때 $q(x)$는 $p(x)$보다 상대적으로 샘플링이 쉬운 분포여야 하며 어떤 양의 상수 $M$에 대하여 다음을 만족해야한다.

\[ Mq(x) \ge \tilde{p}(x) \]

Schematic illustration of rejection sampling (Machine Learning A Probabilistic Perspective)

Rejection Sampling Algorithm

while True do
    $x \sim q(x)$ and $u \sim \text{Unif}(0, 1)$
    if $u < \frac{\tilde{p}(x)}{Mq(x)}$ then
        Reutrn $x$
    end if
end while

\begin{align} \mathbb{P}(\text{accept}) &= \int \cfrac{\tilde{p}(x)}{Mq(x)}q(x) dx = \cfrac{Z}{M} \\ F_x(y|\text{accept}) &= \int_{-\infty}^{y} \cfrac{\tilde{p}(x) / M}{Z / M} dx \\ &= \int_{-\infty}^{y} \cfrac{\tilde{p}(x)}{Z} dx \end{align}

 

acceptance probability는 $Z/M$이므로, $Mq(x)$가 $\tilde{p}(x)$에 가까워질 수록 $Z/M$ 역시 $1$에 가까워진다.

Truncated random variables

특정 구간 $(a,b)$에 속한 경우에만 샘플링하는 방법을 살펴보자.

\[ p(x) = \cfrac{p_0(x)}{\int_a^b p_0(y) dy} \mathbb{1}_{ \{ x \in (a,b) \} } \]

($p_0$는 샘플링하기 쉬운 분포이다.)

일반적으로 $x \in (a,b)$가 될때까지 반복하여 $p_0(x)$에서 샘플링한다. 

이 방법도 rejection sampling으로 해결할 수 있다.

 

$q(x) = p_0(x)$라 하자. 그려면 $M$은 다음과 같다.

\[ M = \cfrac{1}{\int_a^b p_0(y)dy}, \quad Mq(x) \ge p(x) \]

rejection procedure는 다음과 같다: $x \in (a,b)$이면 항상 accept한다.

\[  \cfrac{p(x)}{Mq(x)} = \mathbb{1}_{ \{ x \in (a,b) \} } \]

acceptance probability는 다음과 같다.

\[  \cfrac{1}{M} = \int_a^b p_0(y)dy \]

 

Exponentially tilted random variables

\[ p(x) = \cfrac{p_0(x) e^{-tx}}{Z} \]

이고, $p_0(x)$는 상대적으로 샘플링이 쉬운 분포일 때, 지수적으로 감소하는 확률변수를 샘플링해보자.

 

$q(x)=p_0(x)$라 하고, accept확률을 $e^{-tx}$라 하면 다음과 같다.

\[ M=1,\ Mq(x)=p_0(x) \ge p_0(x)e^{-tx},\ \cfrac{\tilde{p}(x)}{Mq(x)} = e^{-tx} \]

 

Summary

proposal distribution을 도입하고, 원래 target distribution과 tigher할 수록 acceptance probability가 커진다.

그러나 대부분의 경우 proposal distribution을 디자인 하는 것이 어렵다.

Adaptive rejection sampling 역시 있지만, 실제로 자주 사용되는 기법은 아니라고 한다.