몬테 카를로 적분

PBR 공부한답시고 <Physically Based Rendering: From Theory To Implementation>를 종이책 + e북까지 사놓고 안 보고 있었는데 최근에 저자들이 온라인에 무료로 풀었다. 1, 2판도 아니고 내가 산 최신 3판 ㅜ.ㅜ 지금이라도 부랴부랴 읽고 있다.

13장(Monte Carlo Integration) 읽고 정리.

13.1절(Background and Probability Review)은 확률 기초니까 패스

13.2절(The Monte Carlo Estimator)은 예전에 배운 큰 수의 법칙이 떠오르는 알고리즘이다.

($ f(x) = 4(x-0.5)^2 $) 의 그래프. 확률 변수는 균일 분포를 가정하고 0 ~ 1 사이에서 무작위로 뽑는다. 확률 변수 샘플링 횟수를 N, 평균 내기 위한 총 시행 횟수를 M이라 한다. N = 100, M = 10으로 돌려보니 적분 범위가 클 수록 오차가 두드러진다.

왼쪽은 N = 100, M = 10이고 오른쪽은 N = 1000, M = 10일 때. 파란 선이 몬테 카를로, 녹색 선이 해석적으로 계산한 적분이다. N을 키우니 오차가 크게 줄었다.

확률 변수가 균일 분포가 아니라 임의의 PDF p(x)를 따르더라도 원문의 식 (13.3)에 따르면 여전히 적분을 계산할 수 있다. 어떤 PDF에서 확률변수를 샘플링하는 방법은 다음 절인 13.3절(Sampling Random Variables)에 나온다.

적당한 PDF를 만들어보면 정의역 [0, 1]에서 적분하면 1이고 항상 양수인 함수로 ($ p(x) = \frac{3}{4} (1 + x^2) $)이 있다. CDF는 ($ P(x) = \frac{3}{2} (\frac{1}{2} x + \frac{1}{6} x^3 ) $) 이고, CDF의 역함수는 울프램 알파에 돌려보니 ($ P^{-1}(x) = \frac{1}{\sqrt[3]{\sqrt{4 x^2 + 1} - 2x }} - \sqrt[3]{\sqrt{4 x^2 + 1} - 2x } $) 이다.

빨간 선이 ($ p(x) $), 파란 선이 ($ P(x) $), 초록 선이 ($ P^{-1}(x) $) 이다.

($ P^{-1} $)이 올바른지 검증을 해봐야 하는데... 샘플을 왕창 뽑아서 누적해본다.

대충 맞는다.

그런데 정의역 전체가 아니라 [a, b]에서만 적분할 때 확률 변수를 샘플링하기가 애매하다. 균일 확률 변수를 ($ P^{-1}(x) $)에 넣어서 나오는 확률 변수는 정의역 전체에 속하는데, 그 중에 [a, b]에 속하는 확률 변수만 써야 한다. 그러면 [a, b] 밖의 확률 변수가 뽑히면 버려야 하는데, N이 똑같아도 샘플 수가 적어져서 정밀도가 떨어진다. 위 그림은 N = 500, M = 10인데 커스텀 pdf 없이 N = 100, M = 10일 때보다 오차가 심하다.

책에는 적분 구간이 정의역보다 작을 때 어떻게 샘플링해야 하는 지가 안 나와있다. 소설을 써보면 ($ x_0 = P(a) $), ($ x_1 = P(b) $), ($ \xi $)는 균일 확률 변수라 할 때, ($ X_i = P^{-1}(x_0 + (x_1 - x_0) \xi) $) 는 항상 [a, b] 에 포함되는 확률 변수다. 하지만 샘플링을 이렇게 하면 원래 확률 분포에 따라 샘플링한 게 아니라, 더 높은 확률로 샘플링한 게 된다. [a, b] 영역에서 PDF의 넓이는 ($ x_1 - x_0 $)이므로 이만큼을 적분 결과에 곱하면 원래 확률대로 샘플링한 셈이 될 것이다. (근거 無)

왼쪽은 N = 100, M = 10이고 오른쪽은 N = 500, M = 10일 때. 일단 눈으로만 보면 가정이 맞은 것 같다.

13.4절(Metropolis Sampling)의 메트로폴리스 샘플링은 "음이 아닌 함수 f로부터, f의 값에 비례해서 분포된 샘플 집합을 생성하는 기법"이라고 한다. f(x)를 평가할 수만 있으면 적분을 정규화하거나 CDF를 구할 필요가 없다고 한다. 그리고 tentative transition, acceptance probability, stationary distribution 등 뭔지 모를 것들이 나온다. 쭉 읽어봤는데 군데군데 논리가 생략돼서 이해를 못하겠다. queueing theory 잠깐 배울 때 본 개념들 같기도 하고... 메트로폴리스는 제대로 이해하려면 확률 통계 책을 별도로 봐야겠다.

이해는 못했지만 일단 공식만 보고 코딩을 해본다.

• 확률 변수는 0.1 확률로 새 출발, 0.9 확률로 인접 샘플 선택 (최대 거리 0.001)
• acceptance probability는 공식 (13.8) 대로
• start-up bias는 뭐라뭐라 써있는데 그냥 [0, 1] 내에서 무작위 선택

??? 머임? 짱신기

13.5절(Transforming between Distributions)은 여기 내용만으론 딱히 코딩할 게 안 보여서 읽기만 하고 패스

지금까지는 ($ X = p(x) $) 꼴의 1D 확률 밀도 함수만 썼는데, 13.6절(2D Sampling with Multidimensional Transformations)은 2D joint density function ($ p(x,y) $) 로부터 ($ (X,Y) $)를 샘플링하는 방법을 다룬다. 예전에 배웠던 조건부 확률을 이용한다.

맨 먼저 반구를 샘플링하는 게 나오는데 3D는 코딩하기 귀찮으니 건너뛰고, 그 다음 단위원 샘플링이 나온다. 그런데 이 방식은 영역을 찌그러뜨리는 문제가 있어서 concentric mapping이라는 게 있다고 한다. 그리고 레이트레이싱에서 쓰기 위한 Cosine-Weighted Hemisphere Sampling과 Cone Sampling 등 여러가지가 나온다.

이 밑으로는 딱히 짧게 코딩해서 확인해볼 방법이 안 떠올라서 읽은 것만 정리...

13.7절(Russian Roulette and Splitting)은 estimator의 efficiency(효율)을 측정한다. 분산이 낮고 실행 시간이 짧을 수록 효율이 좋다는 상식적인 정의다. 몬테 카를로 estimator의 효율을 높이는 방법으로 러시안 룰렛과 splitting이 있는데, 러시안 룰렛은 계산은 비싼데 최종 결과에 기여는 적은 샘플을 버리고, splitting은 적분에서 중요한 부분에 샘플을 더 많이 배치한다.

러시안 룰렛에서는 각 항의 중요도를 고려해서 이 항을 버릴 확률 q를 도출한다. q의 값은 우리가 알아서 결정해야 하고, q의 확률로 그냥 이번 항을 계산하지 않고 작은 상수(보통은 0)으로 대체한다. 나머지 항들은 살짝 크게 만든다. 러시안 룰렛은 계산량은 줄여주는 대신 q를 결정하는 전략이 구리면 분산이 커진다.

splitting은 뭐 복잡하게 써있는데 그냥 다차원 적분에서 바깥 적분과 안쪽 적분의 샘플 수를 다르게 한다는 것 같다.

13.8절(Careful Sample Placement)은 분산을 줄이기 위해 샘플들을 잘 배치하는 기법을 다룬다. 여기까지 읽고 보니 13장을 읽으려면 7장(Sampling and Reconstruction)을 먼저 읽었어야 했던 것 같다. 13장이 독립적인 것 같아서 그냥 이거부터 읽었는데 ㅜ.ㅜ

stratified sampling은 공식은 뭐라고 복잡하게 써있는데 결국 적분 영역을 여러 개로 분할해서 각 부분의 밀도에 따라 샘플 수를 다르게 하는 기법이다. 분산이 절대 커지지 않지만 차원의 저주 문제가 있다.

나머지 내용은 7장을 읽어봐야 할 듯 -.- 패스

13.9절(Bias)은 또 분산을 줄이는 방법에 관한 내용인데, bias(편향)이 있으면 오히려 분산이 줄어들 수도 있다고 한다. bias는 통계학에서 정의하는 그 bias다. 그런데 bias가 있다는 건 계산 결과가 기대값과 다르다는 건데, 기대값이 정확한 결과 아닌가? 정답이랑 다른 값 주변에서 분산이 적은 게 무슨 소용이지...

13.10절(Importance Sampling)은 샘플들의 분포가 피적분 함수의 모양과 비슷하면 몬테 카를로 estimator가 더 빨리 수렴한다는 것에 착안한 분산 감소 기법이다. 극단적인 반례를 생각해보면 ($ f(X) $)의 값이 대체로 0 ~ 1인데 ($ p(x) $)가 아주 작은 부분에서만 ($ f(X) = 10^{10000} $) 인 경우는 오히려 수렴이 제대로 안 될 것 같다. 하지만 그래픽스에서 영역 적분은 보통 코사인 항을 포함하고 ($ f(x) $)의 치역이 그렇게 극단적인 경우가 없어서 별 문제 없을 것 같다.