13 Monte Carlo Integration

Monte Carlo Integration：只需要能够计算被积分函数，就可以靠采样的方法估算一个积分。

收敛的速度是$O(n^{-1/2})$，4倍采样数目带来2倍的质量提升。

13.1 Background and Probability Review

Probability Density Functoin (PDF): $p(x)$

性质： $p(x)>= 0$ 并且： $\int_D f(x) = 1$

Cumulative Distribution Function (CDF): $P(x)$

\[\int_a^b p(x) = P(b) - P(a)\]

13.1.2 Expected Values and Variance

Expected Value: $E[f(x)] = \int_D f(x)p(x)dx$ 性质： $\begin{align*} E[af(x)] &= aE[f(x)] \\ \\ E\left[\sum_i f(X_i)\right] &= \sum E[f(X_i)] \end{align*}$

Variance: $V[f(x)]=E[(f(x)-E[f(x)])^2]$ 性质： $\begin{align*} V[af(x)] &= a^2V[f(x)] \\ \\ V[f(x)] &= E[f(x)^2]-E[f(x)]^2 \\ \\ \end{align*}$

如果 $X_i$ 之间是 independent 的： $V\left[\sum_i V[f(X_i)\right] = \sum_i V[f(X_i)]$

13.2 The Monte Carlo Estimator

Monte Carlo Estimator:

$F_N=\frac{1}{N} \sum_{i=1}{N}\frac{f(X_i)}{p(X_i)}$ 且 $E[F_N]=\int_a^b f(x)dx$ 根据大数定律，当采样数 $N$ 无穷大时，$F_N=E[F_N]$。

13.3 Sampling Random Variables

13.3.1 The Inversion Method

获取一个按照某种PDF($p(x)$)分布的随机变量：

计算 CDF: $P(x)=\int_0^x p(x’)dx’$
计算 $P^{-1}(x)$
获取一个uniform随机变量 $\xi$
$X_i=P^{-1}(\xi)$

13.7 Russian Roulette and Splitting

Russian Roulette 用来处理计算sample很耗，但sample贡献又很小的情况。通过概率来减少sample的数量，但使计算结果的整体期望不变。

Russian Roulette：设定一个阈值 $q$，每次获取一个uniform随机变量 $\xi$, 若 $\xi > q$ 则继续递归计算 $F=F’$；否则认为 $F=c$，通常取 $c=0$: $F'= \left\{ \begin{align*} & \frac{F-cq}{1-q} \quad & \xi>q \\ & c \quad & otherwise \end{align*} \right.$

13.7.1 Splitting

Splitting takes multiple samples in some of the dimensions of integration for each sample taken in other dimensions.

对于一个有多个需要采样的变量的被积函数，某一些变量采样一次，其他一些变量取多个采样。

例如对于： $E=\int_A \int_{S^2} L_d(x,y,\omega) d\omega dA(x, y)$

基本的 Monte Carlo Esimator 为：

\[E=\sum_{i=1}^N \frac{L_d(X_i, Y_i, \omega_i)}{p(X_i, Y_i, \omega_i)}\]

采用Splitting方法： $E=\sum_{i=1}^N\sum_{j=1}^M \frac{L_d(X_i, Y_i, \omega_j)}{p(X_i, Y_i)p(\omega_j)}$

即对每一组采样 $(X_i, Y_i)$，对 $\omega$ 采样 $M$ 次。这样做的好处是，对于每个 $\omega_j$，和 $(X_i, Y_i)$ 相关的结构都是可以复用的，有些情况下可以减少计算量。

13.10 Importance Sampling

A powerful variance reduction technique that exploits the fact that Monte Carlo converges more quickly if the samples are taken from a distribution that is similiar to the function $f(x)$ in the integrand.

让采样的PDF和被积函数$f(x)$尽可能接近，使得 $f(X_i)$ 较小的 $X_i$ 被采样到的概率也较小，因此减少对最终结构贡献较小的采样。

$p(x)$ 选得不好，会增大 $V[f(x)]$。

13.10.1 Multiple Importance Sampling

对于被积函数是多个函数的乘积的情况，如：

\[L_o(p,\omega_o)=\int_{S^2}f(p,\omega_o,\omega_i)L(p,\omega_i)|cos\theta_i|d\omega_i\]

Importance sample其中一个函数（例如 $f(p,\omega_o,\omega_i)$），采样得到的变量可能会在另一个函数（例如 $L(p,\omega_i)$）上计算得到很小的值，使得整体计算的方差很大。

Multiple Importance Sample (MIS): $L_o(p,\omega_o) \approx \frac{1}{n_f} \sum_{i=1}^{n_f}\frac{f(X_i)g(X_i)w_f(X_i)}{p_f(X_i)} + \frac{1}{n_g} \sum_{j=1}^{n_g}\frac{f(X_j)g(X_j)w_g(X_j)}{p_g(X_j)}$ 其中 $w_f(X)$ 和 $w_g(X)$ 是权重函数，用于保证期望不变。

权重函数可以取 balance heuristic: $w_s(x)=\frac{n_s p_s(x)}{\sum_i n_i p_i(x)}$ 或者取 power heuristic: $w_s(x)=\frac{(n_s p_s(x))^\beta}{\sum_i (n_i p_i(x))^\beta}$ $\beta=2$ 是个通常的做法。

PBRT中 balance heuristic 和 power heuristic 的实现都是 $n_f$ 和 $n_g$ 都取 1。