기각표본추출

통계 수치해석 마지막 수정: 2026-08-01 04:06:41

1. 개요[편집]

기각표본추출 Rejection sampling
별칭	수락-기각법(accept–reject), 폰 노이만 방법
필요 조건	포락선 $Mq(x) \ge \pi(x)$
수락률	$1/M$ (정규화된 목표 기준)
산출	완전히 독립인 표본
최대 약점	차원이 오르면 $M$ 이 지수적으로 폭발

일단 아무 데나 던지고, 곡선 아래 떨어진 것만 줍는다. 끝.

기각표본추출(rejection sampling)은 뽑기 쉬운 제안분포 $q$ 에서 후보를 뽑은 뒤 그중 일부를 확률적으로 버려서, 살아남은 표본이 정확히 목표분포 $\pi$ 를 따르도록 만드는 방법이다. 1951년 폰 노이만이 정리한 형태가 원형이며, 난수 생성기 라이브러리 밑바닥에 지금도 그대로 깔려 있다.

이 문서는 몬테카를로 방법 계열 중 표본을 만들어내는 단계에 한정한다. 뽑은 표본으로 적분을 하는 이야기는 몬테카를로 방법, 표본을 연쇄로 이어 붙이는 이야기는 마르코프 연쇄 몬테카를로, 버리는 대신 가중치로 보정하는 이야기는 중요도 표본추출, 격자점을 규칙적으로 깔아 오차를 줄이는 이야기는 소볼 수열·라틴 하이퍼큐브 표본추출에 있다.

2. 알고리즘[편집]

목표 밀도 $\pi$ 와 제안 밀도 $q$ 에 대해, 모든 $x$ 에서

\pi(x) \le M\,q(x), \qquad M < \infty

를 만족하는 상수 $M$ 을 하나 잡는다. 그러면 절차는 세 줄이다.

$x \sim q$ 를 뽑는다.
$u \sim \mathcal{U}(0,1)$ 을 독립으로 뽑는다.
$u \le \dfrac{\pi(x)}{M q(x)}$ 이면 $x$ 를 채택하고, 아니면 통째로 버리고 1번으로 돌아간다.

정당성은 한 줄 계산으로 끝난다. 임의의 집합 $A$ 에 대해

\Pr(x \in A,\ \text{수락}) = \int_A q(x)\,\frac{\pi(x)}{M q(x)}\,dx = \frac{1}{M}\int_A \pi(x)\,dx

이고, $A$ 를 전체 공간으로 두면 수락 확률이 정확히 $1/M$ 이다. 둘을 나누면 수락된 표본의 조건부 밀도가 $\pi$ 그 자체다. 기하학적으로는 곡선 $Mq$ 아래 영역에 점을 균일하게 뿌린 뒤 $\pi$ 아래에 떨어진 점만 남기는 것과 같고, 그래서 남은 점의 가로좌표 분포가 $\pi$ 가 된다.

핵심은 수락된 표본이 서로 완전히 독립이라는 것이다. MCMC 표본은 자기상관 때문에 개수만큼의 값어치를 못 하지만(유효표본크기 참고), 기각표본추출은 $N$ 개를 뽑으면 유효표본도 정확히 $N$ 개다. 버림받는 대가로 얻는 것이 바로 이 독립성이다.

정규화 상수를 몰라도 된다는 점도 같다. $\tilde\pi = Z\pi$ 만 계산 가능하고 $M q \ge \tilde\pi$ 로 잡았다면 알고리즘은 그대로 굴러가며, 이때 실측 수락률이 $Z/M$ 이므로 덤으로 $Z$ 의 불편추정량이 나온다. MCMC가 원리적으로 못 주는 그 값을 기각표본추출은 공짜로 준다.¹

이봉 표적 π(x) 위에 제안 포락선 M·q(x)를 씌우고 그 아래로 점을 던진다. 밝은 점이 수락, 어두운 점이 기각이고 두 색의 면적비가 곧 수락률 1/M이다. 포락선 배율을 최소 유효값 M* 아래로 내리면 Mq < π인 구간이 붉게 뜨면서 실측 수락률이 1/M 밑으로 내려앉고, 아래 히스토그램에서 뾰족한 봉우리가 깎이는 편향이 나타난다. 표적·제안 모두 정규화 상수를 아는 해석적 밀도이며 M*는 격자 탐색으로 매번 다시 계산한다.

3. 수락률과 차원의 저주[편집]

$M$ 은 그냥 상수가 아니라 비용이다. 후보 하나를 채택하기까지 필요한 시도 횟수는 성공확률 $1/M$ 의 기하분포를 따르므로 평균 $M$ 번이다. $M = 1.2$ 면 우아하고, $M = 10^4$ 면 사실상 못 쓴다.

문제는 $M$ 이 차원에 대해 어떻게 자라느냐다. 목표가 $\mathcal{N}(0, I_d)$ , 제안이 $\mathcal{N}(0, \sigma^2 I_d)$ 로 조금 더 넓은( $\sigma > 1$ ) 가우시안인 아주 착한 상황을 보자. 밀도비는 원점에서 최대이고

M = \sup_x \frac{\pi(x)}{q(x)} = \sigma^{d}

이다. $\sigma = 1.1$ 이라는, 폭을 겨우 10% 틀린 제안분포로 $d = 100$ 차원을 노리면 $M = 1.1^{100} \approx 1.4\times 10^4$ — 표본 하나당 후보 1만 4천 개다. $d = 400$ 이면 $M \approx 4\times 10^{16}$ 이고 이 시점에서 얘기는 끝난다. 제안분포를 완벽에 가깝게 맞춰도 미세한 어긋남이 차원 제곱이 아니라 지수로 벌을 받는 것이 기각표본추출의 근본 한계이며, 고차원에서 MCMC가 판을 가져간 이유가 이것이다.²

반대로 저차원(대략 $d \lesssim 5$ )에서는 여전히 최강이다. 독립 표본이 나오고, 진단할 것도 없고, 번인도 없고, 수렴 논쟁도 없다.

4. 스퀴즈와 적응 기각 표본추출[편집]

포락선을 잘 깎는 것이 이 바닥의 기술이다. 두 가지 표준 개선책이 있다.

스퀴즈 함수(squeeze). 아래에서 목표를 받쳐 주는 값싼 함수 $s(x) \le \pi(x)$ 를 하나 더 준비해 두고, $u \le s(x)/(Mq(x))$ 이면 $\pi(x)$ 를 계산하지도 않고 바로 수락한다. $\pi$ 한 번 평가가 비싼 경우(예: 분자 하나의 퍼텐셜 계산) 전체 시간의 대부분을 절약한다. 수락률은 그대로고 계산량만 줄어드는 순이득이다.

적응 기각 표본추출(adaptive rejection sampling, ARS). 길크스와 와일드(1992)의 방법으로, $\log \pi$ 가 오목(log-concave)하다는 조건만 있으면 포락선을 자동으로 만들어 준다. 지지점 몇 개에서 $\log\pi$ 의 접선을 그으면 오목성 때문에 접선들은 항상 위에 있으므로 그 상위 포락선(구간별 지수함수)이 곧 $Mq$ 가 되고, 지지점을 잇는 현(chord)은 항상 아래에 있으므로 그대로 스퀴즈가 된다. 결정적인 부분은 기각된 점을 버리지 않고 지지점 목록에 추가한다는 것 — 포락선이 실패한 자리마다 자동으로 조여들어서, 표본을 뽑을수록 수락률이 1에 접근한다. 정규·감마·베타·포아송의 완전조건부분포가 대부분 로그오목이라 깁스 표본추출의 내부 엔진으로 널리 쓰였다.

로그오목이 아니면 ARS가 깨지는데, 여기에 메트로폴리스 수락 단계를 덧대 포락선이 목표를 뚫어도 정답을 유지하게 만든 ARMS(adaptive rejection Metropolis sampling)가 흔한 대안이다. 다만 이 순간부터 표본은 더 이상 독립이 아니다 — 사실상 MCMC가 된다.

5. 다른 표본추출법과의 위치[편집]

방법	필요한 것	산출	걸림돌
역변환 표본추출	누적분포의 역함수	독립	역함수가 닫힌 형태로 나오는 분포가 드묾
박스-뮐러 변환	좌표변환 항등식	독립	정규분포 전용, 초월함수 호출 비쌈
기각표본추출	포락선 상수 $M$	독립	$M$ 이 차원에 지수적
중요도 표본추출	제안분포만	가중 표본	무게 퇴화, 분산 발산
마르코프 연쇄 몬테카를로	밀도의 비율	상관 표본	자기상관, 수렴 판정 불가

실제 난수 라이브러리를 뜯어보면 기각법의 지분이 압도적이다. 정규분포의 지구라트 알고리즘은 밀도를 같은 면적의 직사각형 층으로 덮고 층 안에서 균일하게 뽑는 기각법이라 수락률이 99%를 넘고, 마살리아 극좌표법은 단위원 안에 떨어질 때까지 정사각형에서 다시 뽑는 순수한 기각법이다(수락률 $\pi/4 \approx 0.785$ ). 감마분포는 마살리아–창(2000)의 기각법이 사실상 표준이며 수락률이 0.99 부근이다.³ 이산분포의 별칭법(alias method)이 상수 시간을 달성한 것도 “직사각형을 채우고 남은 부분을 재배치한다”는 같은 기하학에서 나왔다.

시뮬레이션 쪽에서는 직접 시뮬레이션 몬테카를로의 충돌 후보 선정(no-time-counter의 수락-기각 판정), 양자 몬테카를로의 시행 파동함수 표본, 렌더링에서 물리 기반 렌더링 BRDF 표본추출의 폴백 경로가 전부 이 알고리즘이다. 맥스웰-볼츠만 분포에서 속도를 뽑는 초기화 루틴도 마찬가지.

6. 실무에서 자주 밟는 지뢰[편집]

$M$ 을 눈대중으로 잡으면 조용히 틀린다. 어딘가 한 점에서라도 $Mq < \pi$ 면 그 영역이 체계적으로 과소표본되는데, 알고리즘은 아무 경고 없이 그럴듯한 히스토그램을 뱉는다. 최적 $M = \sup \pi/q$ 는 최적화 문제이므로, 안 풀리면 여유를 주되 그만큼 수락률을 헌납해야 한다.
꼬리가 문제다. $q$ 의 꼬리가 $\pi$ 보다 얇으면 $\sup \pi/q = \infty$ 라 $M$ 이 아예 존재하지 않는다. 가우시안 제안으로 코시 목표를 덮으려는 시도가 대표적인 실패. 꼬리는 항상 제안분포가 더 두꺼워야 한다는 이 원칙은 중요도 표본추출에서도 똑같이 반복된다.
수락률을 로그로 남겨라. 수락률이 곧 $1/M$ 의 실측치라 코드가 맞는지, 포락선이 얼마나 헐거운지를 한 숫자로 알려주는 무료 진단이다. 이론 수락률과 실측이 어긋나면 십중팔구 $M$ 계산이 틀린 것이다.
버려지는 것이 아깝다고 재활용하지 마라. 기각된 후보를 어떻게든 살려 쓰고 싶은 유혹이 늘 있는데, 그러는 순간 표본은 $\pi$ 를 따르지 않는다. 굳이 살리고 싶으면 처음부터 가중치를 붙이는 중요도 표본추출로 갈아타는 것이 정직하다.⁴

7. 관련 문서[편집]

그래서 베이즈 인자처럼 정규화 상수 자체가 필요한 문제에서는 기각표본추출이 은근히 매력적이다. 문제는 그런 문제일수록 차원이 높아서 $M$ 이 우주를 초과한다는 것. 세상은 공평하다. ↩
이 계산을 처음 해 보면 “제안분포 폭 10% 틀린 게 뭐 어때서”라는 감각이 산산조각 난다. 고차원 가우시안의 질량은 반지름 $\sqrt{d}$ 짜리 얇은 껍질에 몰려 있고, 폭이 10% 다르면 그 껍질 위치가 통째로 어긋난다. 고차원에서 직관은 대체로 킹받는 방식으로 배신한다. ↩
마살리아–창 감마 표본기는 $\alpha \ge 1$ 에서 $d = \alpha - 1/3$ , $c = 1/\sqrt{9d}$ 로 두고 정규 표본 하나를 세제곱 변환한 뒤 기각 판정을 하는데, 수락률이 $\alpha$ 에 거의 무관하게 0.99 언저리다. 논문 본문보다 코드가 짧은 드문 사례. ↩
“아까워서 재활용”은 시뮬레이션 전반의 만악의 근원이다. 발산한 케이스의 마지막 스텝을 초기값으로 재시작하는 것, 수렴 안 된 잔차에서 양력계수를 읽는 것과 같은 부류. 통계에서는 특히 티가 안 나서 더 위험하다. ↩