다중 중요도 표본추출

1. 개요[편집]

어떤 표본추출 전략이 이길지 모르겠으면, 전부 돌리고 각 표본이 어느 전략에서 나왔는지를 보고 무게를 나눠 주면 된다.

다중 중요도 표본추출(multiple importance sampling, MIS)은 하나의 적분에 대해 서로 다른 제안분포 $q_1,\dots,q_n$ 으로 뽑은 표본들을, 각 표본마다 가중치 함수 $w_i(x)$ 를 곱해 하나의 불편추정량으로 결합하는 기법이다. 1995년 베치와 기바스(E. Veach & L. Guibas)가 렌더링 문제를 풀려고 정식화했고, 지금은 물리 기반 렌더링의 사실상 표준 부품이자 통계 쪽 혼합 중요도 표본추출의 표준 도구다.¹

동기가 명확한 기법이다. 실제 문제의 피적분함수는 대개 여러 개의 곱이고(빛 × 반사율, 사전분포 × 우도, 밀도 × 지시함수), 각 인자를 잘 따라가는 제안분포는 서로 다르다. 어느 하나만 골라 쓰면 다른 인자가 지배적인 상황에서 분산이 폭발하는데, 문제는 어느 상황인지 미리 알 수 없다는 것이다. MIS는 “고르지 않는다”를 정식 해법으로 만든다.

단일 제안분포 이론(항등식 $w = \pi/q$, 최적 제안분포, 얇은 꼬리에서의 무한 분산, 무게 퇴화와 유효표본크기)은 중요도 표본추출 문서가 다룬다. 이 문서는 여러 제안분포를 어떻게 결합하는가만 본다.

2. 추정량과 불편 조건[편집]

$I = \int f(x)\,dx$ 를 추정한다고 하자. 전략 $i$ 에서 $n_i$ 개, 총 $N = \sum_i n_i$ 개를 뽑는다. MIS 추정량은

$$\hat{I}_{\rm MIS} = \sum_{i=1}^{n}\frac{1}{n_i}\sum_{j=1}^{n_i} w_i(X_{ij})\,\frac{f(X_{ij})}{q_i(X_{ij})}, \qquad X_{ij}\sim q_i$$

이다. 겉보기엔 그냥 IS 추정량 $n$ 개를 더한 것인데, 결정적인 차이가 가중치 $w_i$ 다. 이 추정량이 불편이 될 필요충분에 가까운 조건은 놀랄 만큼 약하다.

$$\sum_{i=1}^{n} w_i(x) = 1 \quad \text{(단, } f(x)\ne 0 \text{인 모든 } x\text{)}, \qquad q_i(x)=0 \Rightarrow w_i(x)=0$$

즉 각 점에서 무게의 합이 1이고, 못 뽑는 곳에는 무게를 주지 않는다는 것뿐이다. 확인은 한 줄이면 된다 — 각 항의 기댓값이 $\int w_i f \,dx$ 이므로 다 더하면 $\int (\sum_i w_i) f\,dx = I$ 다. 이 조건은 엄청나게 헐거워서, $w_i$ 를 $x$ 에 따라 마음대로 바꿔도 되고 심지어 음수여도 된다. MIS의 설계 공간 전체가 이 자유도 안에 있다.

두 번째 조건이 실은 이 기법의 심장이다. 어떤 전략이 도달할 수 없는 영역에 무게를 주면 그 기여는 영원히 안 들어오는데, 반대로 말하면 각 전략은 자기가 잘하는 영역에서만 책임을 지면 된다. 어느 한 전략이 전 영역을 커버할 필요가 없다는 것이 MIS가 주는 실질적 해방이다.

3. 균형 휴리스틱[편집]

가장 유명한 선택은 균형 휴리스틱(balance heuristic)이다.

$$w_i(x) = \frac{n_i\,q_i(x)}{\sum_{k=1}^{n} n_k\,q_k(x)}$$

“이 점에서 표본을 뽑았을 법한 정도”에 비례해 책임을 나눈다는 뜻이다. 대입해서 정리하면 추정량이

$$\hat{I}_{\rm bal} = \frac{1}{N}\sum_{\text{모든 표본}} \frac{f(X)}{\bar q(X)}, \qquad \bar q(x) = \sum_k \frac{n_k}{N} q_k(x)$$

로 접힌다. 즉 균형 휴리스틱 MIS는 혼합분포 $\bar q$ 하나에서 표본추출한 보통 IS와 정확히 같은 추정량이다. 이 동치성이 이 휴리스틱의 정체를 설명한다 — 여러 전략을 섞는 것은 결국 하나의 두툼한 제안분포를 만드는 일이고, 그 혼합의 꼬리는 성분 중 가장 두꺼운 것을 따라간다. 어느 한 성분이 얇아서 생길 무한 분산 사고가 구조적으로 막힌다는 뜻이며, 방어적 혼합이 성분 둘짜리 MIS로 읽히는 이유도 여기 있다.

베치가 증명한 준최적성 정리가 이 선택을 정당화한다. 같은 표본 배분을 쓰는 어떤 불편 결합 전략 $\tilde I$ 에 대해서도

$$\mathrm{Var}[\hat I_{\rm bal}] \;\le\; \mathrm{Var}[\tilde I] + \left(\frac{1}{\min_i n_i} - \frac{1}{N}\right) I^2$$

이 성립한다. 해석하면 균형 휴리스틱은 최적 결합보다 결코 크게 나쁘지 않다는 보장이다. 가산항이 $I^2$ 에 비례하므로, 전략마다 표본을 넉넉히 뽑는 한 이 여유분은 작다. “잘 모르겠으면 균형 휴리스틱을 쓰라”가 이 분야의 국룰이 된 근거가 이 부등식 하나다.

4. 다른 휴리스틱들[편집]

균형 휴리스틱이 지는 상황도 있다. 어떤 전략이 이미 그 영역에서 압도적으로 좋을 때, 균형 휴리스틱은 나쁜 전략의 표본에도 여전히 작지 않은 무게를 남긴다. 그래서 무게를 더 뾰족하게 만드는 변형들이 있다.

이름	무게	성격
균형	$n_iq_i \big/ \sum_k n_kq_k$	기본값. 준최적 보장
거듭제곱	$(n_iq_i)^\beta \big/ \sum_k (n_kq_k)^\beta$	$\beta=2$ 가 경험적 표준
절단	$q_i < \alpha\,q_{\max}$ 이면 0, 아니면 균형식	약한 전략을 잘라냄
최대	최대 $n_kq_k$ 를 갖는 전략만 1	거듭제곱의 $\beta\to\infty$ 극한

거듭제곱 휴리스틱은 $\beta=1$ 이 정확히 균형 휴리스틱이고, $\beta$ 를 올릴수록 우세한 전략에 무게가 몰린다. 베치가 실험적으로 $\beta=2$ 를 권했고 지금도 렌더러들의 기본값인 경우가 많은데, 이건 정리가 아니라 경험칙이라는 점을 기억해 두는 게 좋다. 무게를 뾰족하게 만들면 우세 전략이 확실한 곳에서는 이득이지만, 두 전략이 비등한 경계 영역에서는 오히려 분산이 커질 수 있다.

이 자유도의 끝까지 간 것이 분산 최적 MIS다. 제약이 $\sum_i w_i = 1$ 뿐이므로, 분산을 목적함수로 놓고 변분을 취하면 최적 무게가 작은 선형계의 해로 결정된다. 이때 나오는 최적 무게는 음수가 될 수 있고, 실제로 균형·거듭제곱 휴리스틱보다 유의미하게 낮은 분산을 준다. 대가는 선형계를 위한 통계량을 표본에서 추정해야 한다는 것이고, 그래서 실무 렌더러보다는 연구 코드에서 먼저 자리를 잡았다.

5. 표본 배분과 단일표본 MIS[편집]

가중치만큼 중요한 것이 $n_i$ 를 어떻게 나누느냐다. 위 정리의 가산항이 $1/\min_i n_i$ 를 포함한다는 것 자체가 경고다 — 어떤 전략에 표본을 하나만 배정하면 보장이 그만큼 헐거워진다.

실무에서 더 흔한 것은 아예 단일표본 모델(one-sample MIS)이다. 매번 확률 $c_i$ 로 전략 하나를 골라 표본 하나만 뽑는다.

$$\hat I_{\rm 1s} = \frac{w_I(X)}{c_I}\,\frac{f(X)}{q_I(X)}, \qquad I \sim \mathrm{Cat}(c_1,\dots,c_n),\; X \sim q_I$$

여기에 균형 휴리스틱 $w_i = c_iq_i/\sum_k c_kq_k$ 를 넣으면 다시 $f(X)/\sum_k c_kq_k(X)$ 로 접힌다. 앞서와 똑같이 혼합분포 IS다. 이 형태의 실질적 이점은 전략 수가 많아도 표본당 비용이 일정하다는 것이다. 다만 대가가 있다 — 무게를 계산하려면 뽑지 않은 전략들의 밀도 $q_k(X)$ 를 전부 평가해야 하므로, 전략 수 $n$ 에 비례하는 밀도 평가 비용이 남는다. 전략이 수백 개인 상황(광원이 수천 개인 장면)에서는 이 비용 때문에 후보를 먼저 걸러내는 별도의 장치를 얹는다.

6. 렌더링에서 — 어느 쪽이 언제 이기나[편집]

MIS가 태어난 문제로 가 보자. 한 점에서의 직접광 적분은

$$L_o(\omega_o) = \int_{\mathcal{H}^2} L_i(\omega)\,f_r(\omega,\omega_o)\,\cos\theta\;d\omega$$

이고, 여기에 쓸 수 있는 자연스러운 전략이 정확히 두 개다.

• 광원 표본추출. 광원 표면에서 점을 하나 뽑아 입체각 밀도로 환산한다. $L_i$ 를 잘 따라간다.
• BSDF 표본추출. 재질의 반사 로브에서 방향을 뽑는다. $f_r\cos\theta$ 를 잘 따라간다.

어느 쪽이 이기는지는 상황이 뒤집는다.

광원	재질	이기는 쪽	지는 쪽이 망하는 이유
작다	확산(거칠다)	광원 표본추출	BSDF 방향이 작은 광원을 거의 못 맞힘
크다	거의 거울(매끈하다)	BSDF 표본추출	광원 위 대부분의 점이 좁은 로브 밖이라 기여 0
크다	확산	둘 다 무난	—
작다	거의 거울	둘 다 힘듦	두 밀도가 거의 안 겹침

특히 잔인한 것은 두 번째 줄과 첫 번째 줄이 같은 화면 안에 동시에 존재한다는 점이다. 베치의 유명한 테스트 장면 — 거칠기가 다른 금속판 네 장 위에 크기가 다른 구형 광원 네 개를 놓은 그림 — 이 정확히 이 상황을 만들어 놓고, 광원 표본추출만 쓰면 매끈한 판에서 노이즈가, BSDF 표본추출만 쓰면 작은 광원 아래에서 반딧불이(firefly)가 터지는 것을 보여 준다. MIS를 켜면 양쪽 다 조용해진다. 여기서 잡히는 반딧불이의 정체는 작은 광원을 BSDF 표본추출이 우연히 맞혔을 때 생기는 거대한 $f/q$ 무게인데, 균형 휴리스틱이 그 점에서 광원 표본추출 쪽 밀도가 크다는 것을 알고 무게를 깎아 주는 것이다.

같은 구조가 렌더링 곳곳에서 반복된다.

• 양방향 경로추적. 정점이 $k+1$ 개인 경로 하나는 광원 쪽 부분경로 $s$ 개와 카메라 쪽 부분경로 $t$ 개를 이어 만들 수 있고($s+t=k+1$), 그런 조합이 $k+2$ 가지다. 이 전부를 MIS로 결합하는 것이 BDPT의 본체이며, 사실 베치의 원 논문이 노린 진짜 목표가 이것이었다. 커스틱(caustics)처럼 특정 전략만 잡을 수 있는 경로가 섞여 있어도 하나의 불편추정량이 나온다.
• 체적 산란. 참여 매질 안의 단일 산란에서 거리 표본추출(투과율을 따라감)과 등각 표본추출(광원까지의 거리 제곱을 따라감)은 각각 광원이 멀 때와 가까울 때 이긴다. 둘을 MIS로 섞는 것이 표준이다.
• 스펙트럼. 파장 하나를 뽑고 이웃 파장 몇 개를 함께 평가한 뒤 파장에 대해 MIS로 결합하는 히어로 파장 표본추출은, 분산 매질에서 파장별로 경로가 갈라지는 문제를 색 노이즈 없이 처리한다.

7. 실무에서 밟는 지뢰[편집]

• 측도를 섞으면 조용히 틀린다. 광원 표본추출은 면적 측도 밀도를, BSDF 표본추출은 입체각 측도 밀도를 자연스럽게 준다. 무게 식에 넣기 전에 같은 측도로 환산하지 않으면 결과는 여전히 그럴듯한 그림이고, 다만 밝기가 틀린다. MIS 버그의 압도적 다수가 이것이다.²
• 밀도 평가 함수와 표본추출 함수가 어긋난다. $q_i$ 로 뽑는 코드와 $q_i(x)$ 를 계산하는 코드가 따로 있으면 둘이 갈라지기 시작한다. 값을 확인하는 가장 값싼 방법은 $f\equiv 1$ 로 두고 적분값이 정확히 나오는지 보는 백색 퍼니처(white furnace) 검사다.
• 무게를 못 계산하는 전략을 섞으면 안 된다. MIS는 $x$ 를 보고 모든 $q_k(x)$ 를 계산할 수 있어야 성립한다. 밀도를 명시적으로 못 쓰는 표본추출기(적응형·재표본추출 기반)를 그냥 끼워 넣으면 불편성이 깨진다. 이런 경우를 다루려고 재표본추출 IS 계열의 확률적 무게 이론이 따로 발달했다.
• 전략이 많다고 좋아지지 않는다. 쓸모없는 전략을 하나 추가하면 그쪽에 배정된 표본이 통째로 낭비되고, 균형 휴리스틱의 분모만 커진다. 준최적성 보장은 “추가해도 크게 안 나빠진다”이지 “추가하면 좋아진다”가 아니다.³

8. 렌더링 밖에서[편집]

통계 쪽에서는 같은 물건이 결정론적 혼합 중요도 표본추출이라는 이름으로 독립적으로 정리됐다. 성분 $q_k$ 에서 표본을 뽑아 놓고 무게를 개별 성분이 아니라 혼합밀도 $\bar q$ 로 계산하는 것이 균형 휴리스틱과 정확히 같은 조작이며, 순진하게 성분별 밀도로 나누는 것보다 분산이 낮다는 결과가 잘 알려져 있다.⁴ 여기서 파생되는 쓰임새는 다음과 같다.

• 적응형 IS. 제안분포를 반복적으로 갱신할 때, 과거 반복에서 나온 표본을 버리지 않고 전부 재사용하려면 “여러 제안분포에서 나온 표본의 결합”이 필요하다. 인구 몬테카를로 계열이 이 구조다. 교차 엔트로피 방법의 반복도 같은 문제를 만난다.
• 희귀사건·신뢰성 해석. 파괴면이 여러 갈래(다중 설계점)면 제안분포도 여러 개 놓아야 하고, 그 결합이 곧 MIS다. 봉우리 하나만 노린 IS는 나머지 갈래의 기여를 통째로 놓치면서도 작은 표준오차를 보고한다.
• 베이즈 계산. 서로 다른 근사 사후분포(라플라스 근사, 변분 추론 결과, 과거 체인)를 성분으로 묶어 하나의 제안분포를 만드는 조합이 흔하다.

9. 관련 문서[편집]

• 중요도 표본추출 — 단일 제안분포 이론은 이쪽
• 몬테카를로 방법 · 기각표본추출 · 준몬테카를로
• 분산 감소 기법 · 유효표본크기
• 물리 기반 렌더링 · 레이 트레이싱 · 양방향 경로추적 · 복사 전달 방정식
• 신뢰성 해석 · 교차 엔트로피 방법 · 부분집합 시뮬레이션
• 입자 필터 · 변분 추론

10. Footnotes[편집]

1. Veach & Guibas, Optimally Combining Sampling Techniques for Monte Carlo Rendering, SIGGRAPH 1995. 그래픽스 논문인데 통계 문헌에서 인용되는 드문 사례다. 베치의 1997년 박사논문은 아예 몬테카를로 렌더링의 측도론적 기초를 새로 깔아 놓았고, 20년 넘게 이 바닥 필독서 자리를 지키고 있다. 참고로 그는 학위 후 렌더링을 떠나 구글에서 검색 광고 시스템을 만들었다. ↩

2. 면적 측도에서 입체각 측도로 넘어갈 때 붙는 야코비안이 $r^2/\cos\theta_l$ 이다. 이걸 빼먹으면 광원에서 먼 픽셀이 체계적으로 어두워지는데, 문제는 그림이 “약간 어두운 그럴듯한 그림”이라 리뷰를 통과해 버린다는 것이다. 렌더러 코드에서 pdf 변수 이름 옆에 측도를 안 적어 두는 습관은 언젠가 반드시 대가를 치른다. ↩

3. MIS를 처음 배우면 “그럼 전략을 잔뜩 넣으면 되겠네”라는 생각이 드는데, 실제로 해 보면 프레임 시간만 늘고 노이즈는 그대로인 경험을 하게 된다. MIS는 서로 다른 곳에서 잘하는 전략들을 합칠 때만 값을 한다. 비슷비슷한 전략 다섯 개는 그냥 하나짜리에 표본을 다섯 배 준 것과 다를 바 없고, 밀도 평가 비용만 다섯 배다. ↩

4. Owen & Zhou(2000)가 이 조합을 정리하면서 방어적 혼합과 함께 “안전하고 효과적인 IS”라는 제목을 달았다. 요지는 「무게를 혼합밀도로 계산하라, 그리고 성분 하나는 목표분포 자체로 두라」는 두 줄이고, 20년이 지나도 이보다 나은 기본 처방이 없다. ↩