Light Transport Simulation의 기본이 되는 Monte Carlo Estimator와 분산을 효과적으로 줄이는 기법인 Importance Sampling에 대해 알아보자.
기댓값과 분산
기댓값 Expected Value
확률론에서 확률 변수의 기댓값이란 어떤 랜덤 프로세스를 반복했을 때 기대할 수 있는 값의 평균이다. 확률 변수 $X$의 기댓값은 $E[X]$로 쓴다. 이산 확률 변수의 기댓값은 다음과 같이,
\[E[X]_{X\sim{p}} = \sum_{i=1}^{n} {x_i} \cdot p(x_i)\]연속 활률 변수의 기댓값은 다음과 같이 정의된다.
\[E[X]_{X\sim{p}} = \int_{\Omega} x \cdot p(x) dx\]예시
주사위 던지기는 랜덤 프로세스다. 확률 변수 $X$ 가 주사위를 던져서 나온 숫자를 나타낸다고 생각해보자. 가능한 $X$ 는 $1, 2, 3, 4, 5, 6$ 이고 모든 값은 동일한 확률 $\frac{1}{6}$ 로 발생한다. 따라서 이 랜덤 프로세스의 기댓값은 다음과 같이 계산할 수 있다.
\[E[X] = \sum_{x=1}^{6} x \cdot \frac{1}{6} = 3.5\]분산 Variance
확률 변수의 분산은 각 변수들이 평균(기댓값)으로부터 얼마나 흩어져 있는지를 나타내는 지표다. 확률 변수 $X$의 분산은 $V[X]$로 쓰고 다음과 같이 정의된다.
\[V[X] = E[(X-E[X])^2]\]예시
주사위 던지기를 일반적인 주사위와 모든 면에 3.5가 적힌 주사위로 진행하면 두 경우 모두 기댓값은 3.5로 동일하겠으나 일반적인 주사위의 분산은
\[V[X] = \sum_{x=1}^{6} (x - 3.5)^2 \cdot \frac{1}{6} = \frac{17.5}{6} \approx 2.9167\]이고 모든 면이 3.5인 주사위는 0이다. 실제로 시행을 반복해 기댓값을 구하는 경우 분산이 작다면 몇번의 시행만으로 기댓값을 구할 수 있겠지만 반대로 분산이 아주 크다면 시행을 아주 많이 반복해야 기댓값에 수렴할 것이다.
특성들
기댓값과 분산의 정의에 따라 임의의 상수 $c$에 대해 다음이 만족한다.
\[\begin{aligned} E[c \, X] &= c \, E[X] \\ V[c \, X] &= c^2 \, V[X] \\ \end{aligned}\]기댓값과 분산의 선형성에 따라 다음 등식도 만족한다. (분산의 경우 $X_i$가 서로 독립이어야 한다.)
\[\begin{aligned} E \Big[ \sum_{i=1}^{N} X_i \Big] =& \sum_{i=1}^{N} E[X_i] \\ V \Big[ \sum_{i=1}^{N} X_i \Big] =& \sum_{i=1}^{N} V[X_i] \\ \end{aligned}\]위 특성들로 분산을 간단히 쓸 수 있다.
\[V[X] = E[(X-E[X])^2] = E[X^2] - E[X]^2\]Monte Carlo Estimator
우리는 적분값 $ I = \int_{\Omega} f(x) dx $ 을 수치적인 방법으로 구하고자 한다. 우선 고등학교때 배운 구분구적법(리만 합)을 적용한다면 다음과 같이 유한 합으로 적분 값을 추정할 수 있다. (x축 변이 균등하게 잘린 직사각형을 순서대로 모두 더하는 상황)
\[I \approx \frac{b-a}{N} \sum_{i=1}^{N} f(x_i)\]위 식을 균등 확률 변수(uniform random variable) $X_i \in [a,b]$로 우항의 식을 Evaluation하는 랜덤 프로세스라고 보고 기댓값을 구해보자.
\[F_N = \frac{b-a}{N} \sum_{i=1}^{N} f(X_i)\] \[\begin{aligned} E[F_N] &= E[\frac{b-a}{N} \sum_{i=1}^{N} f(X_i)] \\ &= \frac{b-a}{N} \sum_{i=1}^{N} E[f(X_i)] \\ &= \frac{b-a}{N} \sum_{i=1}^{N} \int_a^b f(x)p(x) dx \\ &= \frac{b-a}{N} \sum_{i=1}^{N} \int_a^b f(x) \frac{1}{b-a} dx \\ &= \frac{1}{N} \sum_{i=1}^{N} \int_a^b f(x) dx \\ &= \int_a^b f(x) dx \end{aligned}\]결과적으로 이 랜덤 프로세스의 기댓값은 적분값이 된다.
확률 분포 함수(pdf) $p(x)$ 가 uniform이라는 제약을 일반화 하면 Estimator를 다음과 같이 쓸 수 있다.
\[F_N = \frac{1}{N} \sum_{i=1}^{N} \frac{f(X_i)}{p(X_i)}\]단, $ | f(x) | > 0$ 인 부분에서 $p(x) > 0$ 이어야 한다. 이 식이 적분값이 되는지 간단히 확인해 보면,
\[\begin{aligned} E[F_N] &= E[\frac{1}{N} \sum_{i=1}^{N} \frac{f(X_i)}{p(X_i)}] \\ &= \frac{1}{N} \sum_{i=1}^{N} E[\frac{f(X_i)}{p(X_i)}] \\ &= \frac{1}{N} \sum_{i=1}^{N} \int_{\Omega} \frac{f(x)}{p(x)} p(x) dx \\ &= \frac{1}{N} \sum_{i=1}^{N} \int_{\Omega} f(x) dx \\ &= \int_{\Omega} f(x) dx \end{aligned}\]분산 감소 기법
Monte Carlo Estimator를 이용해 적분 값을 추정하는 과정은 시행을 반복해 기댓값을 수치적으로 구하는 과정이다. 우리는 이 랜덤 프로세스의 분산을 생각할 수 있다. Estimator의 분산은 이미지에 노이즈로 나타나게 되고 곧 렌더링 품질을 가른다. 따라서 렌더링에서 Estimator의 분산을 줄이는 작업은 매우 중요하고 렌더링 기법의 발전이 분산을 줄이는 과정이라고 말해도 과언이 아니다.
Monte Carlo Estimator의 분산을 분석하고 분산을 감소시키는 대표적인 기법인 Importance Sampling을 알아보자.
분산 분석
분산의 정의에 따라 Estimator의 분석을 계산해 보면
\[\begin{aligned} V[F_N] &= V[\frac{1}{N} \sum_{i=1}^{N} \frac{f(X_i)}{p(X_i)}] \\ &= \frac{1}{N^2} \sum_{i=1}^{N} V[\frac{f(X_i)}{p(X_i)}] \\ &= \frac{1}{N} V[\frac{f(X)}{p(X)}] \\ \end{aligned}\]위 식을 통해 $N$에 따라 선형적으로 분산이 감소한다는 것을 알 수 있고,
\[\sigma [F_N] = \frac{1}{\sqrt{N}} \sigma \Big[\frac{f(X)}{p(X)} \Big]\]표준편차로부터 RMS(Root Mean Square; 평균 제곱근) Error는 $O(N^{0.5})$ 의 속도로 수렴함을 알 수 있다. (absolute error의 수렴 속도를 분석하는 부분은 3번째 레퍼런스 2.4.1을 참고해 주세요. 이는 마찬가지로 $O(N^{0.5})$ 입니다. )
Monte Carlo Estimator의 유일한 약점(?)이 수렴 속도가 $O(N^{0.5})$ 으로 꽤 느리다는 것인데, 이 문제를 해결하기 위해 다양한 분산 감소 기법을 사용한다.
Importance Sampling
Importance Sampling을 통한 분산 감소의 핵심은 샘플을 생성하는 확률 분포 함수 $p$를 우리가 자유롭게 선택할 수 있다는 부분에 있다.
단적인 예시로 $p$를 피적분 함수 $f$ 에 비례하게 설정하는 경우를 생각해보자. $p \propto f,\, p(x) = cf(x)$. 확률 분포 함수는 정규화($\int_{\Omega} p(x) dx = 1$) 되어야 하기 때문에
\[c = \frac{1}{\int_{\Omega} f(x)dx}\]그러나 이러한 확률 분포 함수는 우리가 처음에 추정하려던 적분의 값을 알아야 한다. 결국 처음 풀고자 하는 문제로 돌아온 셈이다. 그럼에도 불구하고 만약 이런 확률 분포 함수로부터 샘플링하는 경우를 생각해 본다면,
\[\frac{f(X_i)}{p(X_i)} = \frac{1}{c} = \int f(x) dx\]언제나 한번의 evaluation 만으로 적분 값을 추정할 수 있게 될 것이다. 즉 분산이 0인 것이다.
\[\begin{aligned} V[F_N] &= \frac{1}{N} V[\frac{f(X)}{p(X)}] \\ &= \frac{1}{N} V[\frac{1}{c}] \\ &= 0 \end{aligned}\]물론 위 방식이 practical 하지는 않지만, $f$와 모양(Shape)이 비슷한 pdf $p$를 선택하면 Estimator의 분산은 감소한다.
정리하자면 Importance Sampling의 기본적인 아이디어는 피적분 함수값이 큰 부분에 샘플링을 많이 해서 분산을 줄이자는 내용이다. 당연히 피적분 함수값이 큰 부분은 결과에 크게 기여하고 함수값이 작은 부분은 적게 기여할 것이다.
일반적인 경우 피적분 함수 $f$의 특정 factor에 대해 Importance Sampling하는 식으로 많이 쓰인다. 예를 들어 렌더링 방정식의 경우 BRDF와 Geometry term에 대해 Importance Sampling해서 해당 항으로 부터 나오는 분산을 줄인다. 특정 factor에 대한 정확한 샘플링 루틴이 존재하는 경우 Evaluation 단계에서 해석적으로 해당 항을 약분할 수도 있다.
Supports
어떤 함수 $f$의 support, $supp(f)$ 는 $f(x) \ne 0$ 을 만족하는 $x$ 의 집합을 말한다. 확률 변수 $X$ 의 support, $supp(X)$ 는 $X$가 취할 수 있는 모든 값의 집합을 말한다.
확률 변수 $X$ 가 PDF $p$ 를 갖는다면, $supp(X) = supp(p)$ 이다.
Monte Carlo Estimator가 unbiased 하기 위해서 $supp(X)$ 가 적분 하고자 하는 함수 $f$ 의 support 전체를 포함해야 한다. Monte Carlo 적분은 X의 support 에서 일어나고 support 밖의 $f$ 값들은 무시된다. 전통적으로 논문에서 p(x) > 0 if f(x) > 0 이라는 조건으로 표현했다.
\[supp(f) \subseteq supp(X)\]정리
- 우리는 Monte Carlo Estimator를 이용해 어떠한 함수의 적분값도 랜덤 프로세스로 추정할 수 있다.
- Estimator의 분산을 줄이기 위해 Importance Sampling 같은 분산 감소 기법을 사용한다.
참조
[1] https://www.pbr-book.org/3ed-2018/Monte_Carlo_Integration/The_Monte_Carlo_Estimator
[2] https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1662&context=etd
[3] https://www.ime.usp.br/~jmstern/wp-content/uploads/2020/04/EricVeach2.pdf
[4] https://intro-to-restir.cwyman.org/