Rejection Sampling(기각 샘플링)

Rejection sampling이란?

---

Rejection sampling(기각 샘플링)은 어떠한 주어진 확률 분포에서 효율적으로 샘플을 생성하기 위해 많이 이용되는 알고리즘이다. Rejection sampling은 확률 밀도 함수를 알고는 있지만, 그 함수를 통해 샘플을 생성하기 어려울 때 활용할 수 있다.

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

 

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

Rejection sampling의 첫 번째 단계는 $q$에서 샘플 $x_{0}$를 생성하는 것이다.

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

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

Rejection sampling 예제 파이썬 코드 구현

2023.06.08 - [AI/파이썬] - Rejection Sampling을 통한 Beta 분포 확률변수 생성

 

 

참고 : https://untitledtblog.tistory.com/134