[머신 러닝] 기각 샘플링 (Rejection Sampling)

Rejection sampling (또는 acceptance-rejection method)은 어떠한 주어진 확률 분포에서 효율적으로 샘플을 생성하기 위해 많이 이용되는 알고리즘이다. 우리가 샘플을 추출하고자 하는 확률 분포 $p$에 대해 아래의 조건이 만족될 때,  rejection sampling은 매우 효율적으로 이용될 수 있다.

• 주어진 확률 분포 $p$의 확률 밀도 함수 (probability density function, PDF)를 알고 있어야 한다.
• 그러나 $p$에서 직접 샘플을 생성하는 것은 매우 어렵거나 불가능하다.

따라서, rejection sampling은 확률 밀도 함수를 알고는 있지만, 그 함수를 통해 샘플을 생성하기가 어려울 때 활용할 수 있는 알고리즘이다.

1. 제안 분포 (Proposal distribution)

Rejection sampling의 기본적인 동작은 쉽게 샘플을 생성할 수 있는 $q$에서 샘플들을 생성한 뒤에 이 샘플들의 분포가 $p$를 따르도록 수정하는 것이다. 이를 통해 실제로는 $q$에서 샘플이 생성되었지만, 그 결과는 $p$에서 생성된 것처럼 만드는 것이다. 이때 쉽게 샘플을 생성할 수 있도록 임의로 설정한 $q$를 제안 분포 (proposal distribution)이라고 한다. 제안 분포는 uniform distribution, normal distribution 등이 이용될 수 있으며, 가능하면 $p$와 비슷한 형태의 확률 분포를 사용하는 것이 좋다.

[그림 1] 확률 분포 $p$와 $q, M$의 관계

제안 분포를 설정한 다음에는 상수 $M$을 설정한다. 이때 $M$은 [그림 1]과 같이 모든 $x$에 대해 $p(x) \le Mq(x)$가 되도록 설정해야 한다.

2. 샘플링 과정

Rejection sampling의 첫 번째 단계는 [그림 2]와 같이 $q$에서 샘플 $x_0$를 생성하는 것이다.

[그림 2] 확률 분포 $q$로부터 샘플 생성

그다음, [0, $Mq(x_0)$] 사이의 uniform distribution에서 $u$를 생성하여 $u$가 [그림 3]의 A 영역에 존재한다면 $x_0$를 기각 (rejection)하고, B 영역에 존재한다면 $x_0$를 샘플로 이용한다. 이 과정을 통해 $q$에서 생성된 샘플들은 $p$를 따르게 된다.

[그림 3] 샘플의 기각 및 수용

$q$에서 샘플을 생성하여 [0, $Mq(x_0)$] 사이의 난수에 따라 샘플을 기각-수용하는 과정을 무한히 반복하면, rejection sampling을 통해 얻은 샘플들은 결국 [그림 4]와 같이 $p$에서 생성된 샘플처럼 보이게 된다.

[그림 4] Rejection sampling을 통해 얻은 샘플들의 분포

아래의 [알고리즘 1]은 rejection sampling을 통해 $N$개의 샘플을 생성하는 코드를 나타낸다.

3. 채택률과 $M$ 값의 설정

좋은 샘플링 알고리즘의 조건은 원하는 분포에서 빠르게 샘플을 생성하는 것이다. 그러나 rejection sampling은 샘플을 생성한 뒤에 랜덤하게 생성된 샘플을 기각-수용하기 때문에 일정 시간 내에 원하는 수의 샘플을 생성한다는 보장을 할 수 없다. 이것은 rejection sampling의 채택률과 관련이 있는데, 채택률 $p(accept)$는 [식 1]과 같이 정의된다.

따라서, 채택률은 $M$에 반비례한다. 즉, 채택률을 최대화하여 rejection sampling의 실행 속도를 빠르게 만들기 위해서는 $p(x) \le Mq(x)$를 만족하면서 가능한 작은 $M$을 선택해야 한다.