안경잡이개발자

728x90
반응형

  Rejection Sampling은 특정한 확률 분포에서 데이터를 샘플링하기 위해(표본을 뽑기 위해) 효과적으로 사용할 수 있는 알고리즘 중 하나다. 단, Rejection Sampling을 하기 위해서는 특정한 확률 분포의 확률 밀도 함수(PDF)를 알고 있어야 한다. 예를 들어 우리가 주사위를 굴린다고 하면, 각 경우에 대하여 확률이 다음과 같이 구성된다는 것을 알 수 있다.

 

  1) 눈금 1이 나올 확률 = 1/6

  2) 눈금 2가 나올 확률 = 1/6

  3) 눈금 3이 나올 확률 = 1/6

  4) 눈금 4가 나올 확률 = 1/6

  5) 눈금 5가 나올 확률 = 1/6

  6) 눈금 6이 나올 확률 = 1/6

 

  하지만 우리가 "주사위"를 갖고 있지 않아서, 확률 분포에서 샘플링(sampling)을 진행할 수 없는 상황이라고 가정해보자. 반면에 우리에게 주사위 대신 "동전"이 있다고 해보자. 우리가 동전을 던지면, 각 경우에 대하여 확률이 다음과 같이 구성된다.

 

  1) 앞면이 나올 확률 = 1/2

  2) 뒷면이 나올 확률 = 1/2

 

  이때 "동전"을 가지고 "주사위"를 던지는 것과 동일한 시행을 할 수 있을까? 즉, 우리는 확률 분포 p(주사위 굴리기)에서는 샘플링을 수행할 수 없고, 확률 분포 q(동전 던지기)에서는 직접적으로 샘플링을 수행할 수 있는 상황이다. 이때 사용할 수 있는 것이 바로 Rejection Sampling이다. Rejection Sampling을 이용한 방식은 다음과 같다.

 

  1. 동전을 세 번  던져서 [0, 7] 사이의 값을 만든다.

    1) 만약 값이 6 혹은 7이라면, reject하고 다시 sampling한다.

    2) 만약 값이 [0, 5] 사이의 값이라면 거기에 1을 더해 반환하면 된다.

 

  이를 코드로 옮긴 것은 다음과 같다. 동전 던지기를 수행하는 coin() 메서드를 이용해, 결과적으로 100번의 주사위 굴리기를 수행하여 결과를 출력한다.

 

import random


def coin():
    return random.randint(0, 1)


def three():
    out = coin()
    out = out * 2 + coin()
    out = out * 2 + coin()
    return out


def dice():
    res = three()
    while res >= 6:
        res = three()
    return res + 1


for i in range(100):
    print('Dice:', dice())
728x90
반응형