Resampled Importance Samplingについて

知識のアップデートという事で、2020年に書いたImportance Resamplingの記事を書き直します。Siggraph2023で行われた、「A Gentle Introduction to ReSTIR」というコースが包括的にRISやReSTIRについて説明してくれています。コースノートも参照可能ですので本格的に学びたい方は、ぜひこちらの方を皮切りに勉強することをお勧めします。ここでは、Weighted Reservoir Samplingの手法やReSTIRのフレームワークについては説明しません。RISについてのみ説明します。

参考文献リスト

Wyman, C., Kettunen, M., Lin, D., Bitterli, B., Yuksel, C., Jarosz, W., & Kozlowski, P. (2023). A Gentle Introduction to ReSTIR Path Reuse in Real-Time. ACM SIGGRAPH 2023 Courses.
Bitterli et al. (2020), ‘Spatiotemporal Reservoir Resampling for Real-Time Ray Tracing with Dynamic Direct Lighting’
Lin et al. (2022), ‘Generalized Resampled Importance Sampling’
Veach (1997), ‘Robust Monte Carlo Methods for Light Transport Simulation’

モンテカルロ積分

レンダリングの話はひとまず置いておいて、ある関数(被積分関数):$f(x)$を、領域(ドメイン):$\Omega$で積分したものを$I$とします。

$$ I = \int_{\Omega} f(x) dx $$

上記の積分がClosed Form(簡単な算術形式)で表せない場合は、モンテカルロ法による推定が有効な手法となります。モンテカルロ法による積分の推定を、モンテカルロ積分と呼びます。 また、モンテカルロ法で推定値を計算する行為そのものをモンテカルロ推定、MC推定などと呼びます。 モンテカルロ法で推定した積分の値を$\langle I \rangle$とするならば、ドメイン:$\Omega$内の、$M$個の一様分布で生成したサンプル:$S$を用いて、以下のように計算できます。
この式は、ドメイン:$\Omega$における関数:$f(x)$の平均値にドメインの大きさを乗じたものと解釈することもできます。

$$ \begin{gather} \text{with} \quad S=\{X_1​,X_2​,\: …\:,X_M \} \quad \text{where}\quad X_i \sim Uniform(\Omega), \newline I \approx \langle I \rangle = |\Omega|\frac{1}{M}\sum^{M}_{i=1} f(X_i) \end{gather} $$

有限個のサンプルでは、計算結果は必ずしも積分の真の値と一致しませんが、サンプル:$S$の分布が、ドメイン:$\Omega$と一致する限り、このモンテカルロ推定の期待値は、積分の値に等しくなります。推定の期待値が真値に一致する状態を、Unbiasedもしくは不偏であるといいます。

$$ E[\langle I \rangle] = I $$

また、$f(x)$のサポート (関数の非ゼロ領域）がドメイン:$\Omega$全体より小さい場合は、$\Omega$で積分しても、$f(x)$のサポート:$supp(f)$で積分しても同じ値なります。

$$ \begin{gather} \text{with}\quad supp(f) \subseteq \Omega \quad \text{where}\quad supp(f)=\{x ∣ f(x) \neq 0\},\quad \newline I = \int_{supp(f)} f(x) dx \end{gather} $$

同様に、サンプル:$S$の一様分布が、$f(x)$のサポートを覆う限りは、ドメイン：$\Omega$全域を覆ってなくても、モンテカルロ法による積分の推定は可能です。

$$ \begin{gather} \text{with}\quad S=\{X_1​,X_2​,\: … \: ,X_M\} \quad \text{where}\quad X_i \sim Uniform(supp(f)) \quad \text{and}\quad supp(f) \subseteq \Omega, \newline I \approx \langle I \rangle = |supp(f)|\frac{1}{M}\sum^{M}_{i=1} f(X_i) \end{gather} $$

Importance Sampling

M個のサンプル:$S$が、確率密度関数:$p(x)$に基づく分布で与えられるとき、被積分関数:$f(x)$のドメイン：$\Omega$による積分をモンテカルロ法で推定:$\langle I \rangle$する場合、以下のようになります。先ほどの式で乗算されていた、ドメインの大きさ：$|\Omega|$や、サンプル分布領域の大きさ$|supp(f)|$の役割は、確率密度関数:$p(x)$が担います。

$$ \begin{gather} \text{with}\quad S=\{X_1, X_2,\: … \:, X_M\} \quad \text{where} \quad X_i \sim p(x) \quad \text{and} \quad X_i \in \Omega, \newline \langle I \rangle = \frac{1}{M}\sum^{M}_{i=1} \frac{f(X_i)}{p(X_i)} \end{gather} $$

ドメイン:$\Omega$全域において$f(x)$が非ゼロであるならば、確率密度関数:$p(x)$がドメイン全域において$>0$であれば、この推定の期待値はドメイン:$\Omega$における関数:$f(x)$の積分の値に等しくなります。

$$ \begin{gather} \text{with} \quad \Omega \subseteq supp(f) \quad \text{and} \quad \Omega = supp(p),\newline \qquad E[\langle I \rangle] = I  \end{gather} $$

$f(x)$のサポートがドメイン:$\Omega$全体より小さい場合は、$f(x)$のサポートにおいて$p(x)$が$>0$ならば、この推定の期待値は積分の値に等しくなります。

$$ \begin{gather} \text{with} \quad supp(f) \subseteq \Omega \quad \text{and} \quad supp(f) \subseteq supp(p),\newline E[\langle I \rangle] = I  \end{gather} $$

ここから先は、被積分関数:$f(x)$のサポートは積分のドメインに含まれる: $supp(f) \subseteq \Omega$として説明します。

1サンプルのImportance Sampling

ここで、サンプルが一つだけのImportance Samplingを考えてみます。
直感的に、このMC推定は分散が大きいと考えられますが、もしも、確率密度関数:$p(x)$が被積分関数:$f(x)$に完全に比例している場合、この推定値は、$supp(f)$全域において一定の値を返します。そして、その値は積分の真の値と一致するはずです。しかし、実際には$f(x)$に完全に比例する$p(x)$を用意するには、事前に$f(x)$の積分が解析的に解ける必要があり、これは、モンテカルロ積分の適用と矛盾します。しかし、たとえサンプルが１つだけのモンテカルロ積分でも有効な推定で、上記で説明した、確率分布関数のサポートの条件を満たせば、その期待値は積分の値と一致します。ただし、推定値の分散は、一般的に著しく大きいと考えられます。

$$ \langle I \rangle = \frac{f(X)}{p(X)} $$

Multiple Importance Samling : MIS

次に、サンプル:$X_i$ごとに異なる確率密度関数:$p_i(x)$を用いてサンプリングして、被積分関数:$f(x)$の積分をモンテカルロ法で推定:$\langle I \rangle$する場合を考えます。
M個のサンプル:$S$が、それぞれの要素に対応する確率密度関数: $\{p_1(x), p_2(x), … , p_m(x)\}$ に基づく分布で与えられるとき、MC推定は最もシンプルな形では以下のように書けます。

$$ \begin{gather} \text{with} \quad S =\{X_1,\: … \:, X_M\}, \quad \text{where} \quad X_i \sim p_i(x) \: (\text{for}\: i=1,\: … \:,M) \quad \text{and} \quad X_i \in \Omega \newline \langle I \rangle = \frac{1}{M}\sum^{M}_{i=1} \frac{f(X_i)}{p_i(X_i)} \end{gather} $$

この式は、複数の確率密度関数を用いた、1サンプルのImportance SamplingのMC推定の平均をとったものと解釈できます。このように複数の確率密度関数を用いてサンプリングして行うMC推定をMultiple Importance Sampling:MISと言います。この時、それぞれの確率密度関数の事を、サンプリング戦略と呼びます。個々の戦略は違えど、目的は同じなので、複数のサンプリング戦略という言葉は、複数の確率密度関数よりも直感的で分かりやすいかもしれません。

MISでは、サンプリング戦略ごとに重みづけをすることができます。上式のように、$1/M$と一定の値を乗算していた部分に、サンプリング戦略ごとに異なる$x$の関数による係数:$m_i(x)$を導入します。 通称MISウエイトと呼ばれるこの関数によって、サンプリング戦略の重要度を、サンプル値に応じて変化させます。MISウエイトは、サンプリング戦略ごとに異なる関数なので、同じサンプル値:$x$でも、異なるサンプリング戦略の$m_i(x)$は、異なる値を返す点に注意が必要です。MISウエイトは、サンプリング戦略ごとに得意な範囲（$f(x)$と比例した形近い形の範囲）で、大きなウエイトを返すように設計することで、MC推定の分散の低減を目指します。

一般的には、サンプリング戦略の数とサンプリング戦略ごとに生成するサンプル数は、それぞれ独立の変数で、MISは複数サンプリング戦略の加重平均という解釈が正しいです。ここでは、$M$個のサンプリングを$M$種類のサンプリング戦略でサンプリングしているので混乱しやすいですが、あくまで、複数サンプルの加重平均という解釈ではなく、複数サンプリング戦略による1サンプルImportance Samplingの加重平均と解釈した方が良いと思います。

$$ \langle I \rangle = \sum^{M}_{i=1} m_i(X_i) \frac{f(X_i)}{p_i(X_i)} $$

上記のMC推定の期待値が積分の値と一致するためには、以下の条件を満たす必要があります。

1. どのサンプル値:$x$においても、$f(x)$のサポート内は、すべてのサンプリング戦略のMISウエイト関数の合計は1である必要があります。

$$ \sum^{M}_{i=1} m_i(x) = 1 \qquad \text{if}\quad x \subseteq supp(f) $$

2. ある確率密度関数:$p_i(x)$が、あるサンプル値:$x$を生成しない場合（つまり$p_i(x)=0$）、$m_i(x)$はゼロである必要があります。

$$ m_i(x) = 0 \qquad \text{if} \quad x \notin supp(p_i) $$

3. すべての$p_i(x)$のサポートの和集合が、$supp(f)$を包含する必要があります。

$$ supp(f) \subseteq \bigcup_{i=1}^{M} supp(p_i) $$

Balance Heuristic

MISウエイト関数として、$m_i(x)$を以下のように計算するものが、Balance Heuristicとして提案されており、良いMISウエイトとして一般的に使われています。 この式は、一見して、$m_i(x)$の総和が1になることが分かります。加えて、サンプリング戦略ごとに確率が高い範囲で、大きなウエイトを返すよう設計されています。言い換えれば、いくつかの確率密度関数が、それぞれ高確率になる領域で、$f(x)$に比例する形に近くなっていれば、このMISウエイトは良い選択になると言えると思います。

$$ m_i(x) = \frac{p_i(x)}{\sum_{j}p_j(x)} $$

MISウエイトの総和が１であることの意味

MISウエイトの総和が1であることが、MC推定が不偏であることの条件になっていることについて、少し考えてみたいと思います。
MISウエイトの総和が1であるならば、$M$個の、MISウエイトと被積分関数の乗算:$m_i(x)f(x)$の総和をドメインで積分した値は、 $f(x)$の積分に等しくなるのは直感的にわかるかと思います。これは、ドメイン全域、サンプリング戦略全てを対象とした積分です。

$$ \int_{\Omega}f(x)dx = \int_{\Omega} \sum_{i=1}^{M}m_i(x)f(x) dx = \sum_{i=1}^{M} \int_{\Omega} m_i(x)f(x) dx $$

一方で、MISによる推定では、各サンプルは、それぞれ別のサンプリング戦略から生成され、それらサンプルの値は異なると考えるべきです。 そして、異なるサンプルの値のMISウエイト関数同士には総和の条件がありません。

MISウエイトを用いたMC推定の式は、上式における$m_i(x)f(x)$の積分の総和に対応していると考えられます。そのため、各サンプリング戦略は等しく用いられる必要があります。 $M$個のサンプリング戦略が、それぞれ1サンプルのImportance Samplingで、$m_i(x)f(x)$の積分を推定している見ることができ、 その総和は$f(x)$の積分の推定になると解釈できます。

$$ \langle I \rangle = \sum^{M}_{i=1} m_i(X_i) \frac{f(X_i)}{p_i(X_i)} $$

Unbiased Contribution Weight: UCW

これまでサンプルの生成において、確率密度関数が閉形式もしくはclosed formとして計算可能な場合について説明してきましたが、そうでない場合について考えてみます。

あるサンプル$X$が複雑な過程を経て生成された場合に、その生成における確率密度関数を計算することが困難な場合でも、期待値が、そのサンプルの生成確率の逆数になる値:$W_{X}$が分かれば、不偏なモンテカルロ積分を行うことができます。この$W_X$のことを、Unbiased Contribution Weight: UCWもしくは、不偏寄与重みと呼びます。

$$ E[W_{X} | X] = \frac{1}{p(X)} $$

条件付き期待値の書式で書かれている理由は、あるサンプル$X$が与えられた後に、$W_{X}$を計算するからです。 UCWが分かれば、1サンプルのMC推定を以下のように定義することができ、その期待値は被積分関数:$f(x)$の積分の値となります。

$$ E[f(X) W_{X}] = E[f(X) / p(X)] = E[\langle I \rangle] = I $$

UCWは、ここでは、単純な確率密度関数の逆数の言い換えのように感じますが、サンプル:$X$が生成された後で計算できればよく、また、値が確率密度関数の逆数に一致しなくても、その期待値が一致することで、MC推定の不偏性が保てるという点で⁠重要な意味を持ちます。

Resampled Importance Sampling: RIS

Importance Samplingにおいて、サンプルの生成確率は、確率密度関数:$p(x)$に基づいています。確率密度関数は、全体を積分すると1である必要があるため、少なくとも積分可能な関数でなくてはなりません。そのため、モンテカルロ積分のサンプリングを、ある別の重みづけで行いたいとして、勝手なサンプリング関数や分布を用意しても、直接Importance Samplingすることはできません。

少々雑な言い方をすれば、RISは、MC推定の期待値を変えることなく、サンプルの分布を、任意の重みづけ関数:$\hat{p}(x)$に基づくようにするためのものです。 簡単に手順を説明すれば、まず、多数のサンプルを、ある確率密度関数:$p(x)$に基づいて事前に生成して、次に、サンプルそれぞれに、任意の重みづけ関数:$\hat{p}(x)$で重みづけをして、その重みに比例する形でサンプルを選択することで、積分の対象の関数:$f(x)$と乗算するサンプルである、選択サンプルの分布を$\hat{p}(x)$に比例した形に近づけます。

もし、$\hat{p}(x)$が$p(x)$よりも$f(x)$に比例した形に近ければ、$\hat{p}(x)$を用いたRISによる推定は、$p(x)$を用いたImportance Samplingよりも、分散が低減されるはずです。これがRISを使う動機になります。では、$\hat{p}(x)$に$f(x)$そのものを用いれば、理想的で良いのかという事になりますが、$\hat{p}(x)$はRISで推定値を計算する過程で何度も評価されるので、$\hat{p}(x)$は$f(x)$に比べて計算コストがかなり低いことが、RISを合理的に使うための前提条件になります。まとめると、RISを合理的に使う条件は以下の通りになります。

• $p(x)$に比べて$\hat{p}(x)$が$f(x)$に対して比例した形に近い
• $f(x)$に比べて$\hat{p}(x)$の評価コストが大きく低い

この二つの条件を満たす$\hat{p}(x)$が事前に分かるときは、RISを効果的に使用できます。

Resampled Importance Sampling: RIS（Identically distributed samples）

RISの一番簡単な例として、生成されるサンプルが同一の確率密度関数:$p(x)$に基づく場合について説明します。はじめに、ある確率密度関数:$p(x)$に基づいてM個のサンプル候補を生成します。

$$ S=\{X_1, X_2,\: … \: , X_M \} \quad \text{where} \quad X_i \sim p(x) \quad \text{and} \quad X_i \in \Omega $$

次に、各生成サンプルに、リサンプリング重み:$w_i$を計算します。リサンプリング重みを制御する関数:$\hat{p}(x)$は、サンプルの生成確率と関係ない任意の関数で、確率密度関数である必要もありません。 直感的に、サンプルの生成率:$p(x)$が小さく$\hat{p}(x)$が大きい値を取る領域では、$w_i$は大きな値になるのが分かります。

$$ w_i = \frac{1}{M} \frac{\hat{p}(X_i)}{p(X_i)} \quad (\text{for}\: i=1,\: … \:,M) $$

そして、計算されたリサンプリング重み:$w_i$に比例する形で、サンプルを選択します。 リサンプリング重みは、$\hat{p}(X_i)$と$p(X_i)$の比で計算されているので、全体的なサンプルの選択確率は、$\hat{p}(x)$に比例する形に近づくようになっています。 以降は、選択されたサンプルを$Y$と表記します。そして、選択されたサンプルのUnbiased Contribution Weights: UCW:$W_Y$を計算します。

$$ W_Y = \frac{1}{\hat{p}(Y)} \sum_{i=1}^{M}w_i $$

最後に、被積分関数:$f(Y)$とUCW:$W_Y$を乗算することで、RISによるMC推定となります。

$$ \langle I \rangle = f(Y)W_{Y} $$

この、RISによるMC推定の不偏性を保つためには、$f(x)$のサポートにおいて、以下の条件を満たす必要があります。

$$ \begin{gather} \text{with} \quad supp(f) \subseteq supp(\hat{p}) \subseteq supp(p), \newline \quad E[\langle I \rangle] = I \end{gather} $$

RISの理解について

RISの理解として、まず、$W_Y$の$\sum_M w_i$の部分は、確率密度関数:$p(x)$に基づく$M$個のサンプルで、リサンプリング重み関数:$\hat{p}(x)$をImportance Samplingしていると考えることができます。 したがって、その推定値は、ドメイン:$\Omega$における、$\hat{p}(x)$の積分と考えることができます。この推定値を$\langle I_{\hat{p}} \rangle$とします。 $p(x)$のサポートが、$\hat{p}(x)$のサポートを内包すれば、$\langle I_{\hat{p}} \rangle$の期待値は、$\hat{p}(x)$の積分に一致します。 $$ \begin{gather} \text{with} \quad supp(\hat{p}) \subseteq supp(p) \subseteq \Omega, \newline \qquad E[\langle I_{\hat{p}} \rangle]＝\int_{\Omega} \hat{p}(x)dx \end{gather} $$

UCW: $W_Y$は、$\hat{p}(Y) / \langle I_{\hat{p}} \rangle$の逆数となっているので、$\hat{p}(x)$を正規化して確率密度関数にした関数:$\bar{p}(x)$に、サンプル$Y$を渡した値の逆数と考えることができます。

$$ W_Y = \frac{1}{\hat{p}(Y)} \sum_{i=1}^{M}w_i \approx \frac{|\hat{p}|}{\hat{p}(Y)} = \frac {1}{\bar{p}(Y)} $$

そして、$\langle I \rangle = f(Y)W_{Y}$は、被積分関数:$f(x)$の確率密度関数:$\bar{p}(x)$による、1サンプルのImportance Samplingと考えることができます。 このようにRISを理解すると、RISによるMC推定の不偏性は、

• $supp(\hat{p}) \subseteq supp(p)$であることで、$E[\langle I_{\hat{p}} \rangle]$の不偏性が保てる。
• $supp(f) \subseteq supp(\hat{p})$であることで、$E[\langle I \rangle]$の不偏性が保てる。

と考えることができます。

リサンプリングMISウエイト

上記の解釈では、$W_Y$は、$\bar{p}(x)$の逆数でした。特に$\langle I_{\hat{p}} \rangle$の部分は、実質的にImportance Samplingになっています。 この部分は、$\int \hat{p}$の推定が出来れば良いわけで、Multiple Importance Samplingに変更しても問題ありません。 したがって、$w_i$の式にある、$1/M$という係数は、MISウエイトと考えることができます。これをリサンプリングMISウエイト:$m_i(x)$とします。 $$ w_i = m_i(X_i) \frac{\hat{p}(X_i)}{p(X_i)} $$ 今のところ、同一の確率密度関数から全てのサンプルを生成しているので、リサンプリングMISウエイトは$1/M$が適切です。 $$ m_i(x) = \frac{1}{M} $$

RIS手順の一般化

RISでは、RISで選択されたサンプルを、次のRISのサンプル候補として扱い、再帰的にRISを適用することができます。 そのために、RISの計算手順の一般化をします。先ほどの説明とは少し順序が入れ替わります。

1. $M$個のサンプル:$S$をドメイン:$\Omega$で用意します。ついで、各サンプルのUCWを用意します。$Ｗ_{X_i}$はサンプル$X_i$のUCWで、サンプルの生成確率:$p(X_i)$がわかる場合は、単に$1/p(X_i)$になります。 $$ \begin{gather} S=\{X_1, X_2,\: … \: , X_M \} \in \Omega \newline \{W_{X_1}, W_{X_2},\: … \: , W_{X_M}\} \end{gather} $$

2. 各サンプルのリサンプリングMISウエイト:$m_i(X_i)$を計算します。すべてのサンプルが同一の確率密度関数から生成された場合は、$m_i(X_i) = 1/M$が適切となります。

$$ m_i(X_i) = \frac{1}{M} \quad (\text{for}\: i=1,\: … \:,M) $$

3. リサンプリング重み:$w_i$を計算します。UCWとリサンプリングMISウエイトがわかれば、以下のように計算することができます。

$$ w_i = m_i(X_i) \hat{p}(X_i) W_{X_i} \quad (\text{for}\: i=1,\: … \:,M) $$

4. リサンプリング重み:$w_i$に比例する形でサンプル列:$S$からサンプルを選択します。選択されたサンプルを$Y$とします。

5. サンプル$Y$の新しいUCW:$W_Y$を計算します。

$$ W_Y = \frac{1}{\hat{p}(Y)} \sum_{i=1}^{M}w_i $$

6. 最後に、選択されたサンプル$Y$を用いて、$f(Y)$とUCW:$W_Y$を乗算することで、RISによるMC推定となります。

$$ \langle I \rangle = f(Y)W_{Y} $$

この一般化で、RISの候補サンプルと対応するUCWから、リサンプリング重みを計算するように手順を変更しました。 これによって、RISの候補サンプルは、必ずしもサンプルの生成確率が計算可能なサンプルである必要がなく、UCWが計算可能ならばRISの候補サンプルになれることを示しています。

Resampled Importance Sampling, Differently Distributed Samples

次に、サンプルごとに異なる確率密度関数:$p_i(x)$を用いた場合のRISについて説明します。これは、RISのMultiple Importance Sampling版と考えられます。

まず、サンプル列$S$は、サンプルごとに対応する確率密度関数$p_i(x)$によって生成します。

$$ S =\{X_1,\: … \:, X_M\}, \quad \text{where} \quad X_i \sim p_i(x) \: (\text{for}\: i=1,\: … \:,M) \quad \text{and} \quad X_i \in \Omega \newline $$

UCW:$W_{X_i}$は、サンプルの生成に使った確率密度関数:$p_i(x)$がわかっているので、以下のように計算できます。 $$ W_{X_i} = \frac {1}{p_i(X_i)} \quad (\text{for}\: i=1,\: … \:,M) $$

次に、リサンプリングMISウエイト:$m_i(X_i)$を計算します。これは、先のMultiple Importance Samplingの項で説明したMISウエイトと同様です。 不偏である条件は、各サンプリング戦略の$m_i(x)$の総和が1であること、代表的なMISウエイトとして、Balance Heuristicsが挙げられるのも同様です。ここでは、各サンプルの生成に使った確率密度関数が 分かるので、Balance Heuristicsで計算します。

$$ m_i(X_i) = \frac{p_i(X_i)}{\sum_{j=1}^{M}p_j(X_i)} $$

次に、リサンプリングの選択ウエイト:$w_i$を以下のように計算します。

$$ w_i = m_i(X_i) \hat{p}(X_i) W_{X_i} $$

そして、リサンプリング重み:$w_i$に比例する形でサンプル列:$S$からサンプルを選択し、そのサンプルを$Y$とします。そしてUCWを更新します。

$$ W_Y = \frac{1}{\hat{p}(Y)} \sum_{i=1}^{M}w_i $$

最後に、選択されたサンプル$Y$を用いて、$f(Y)$とUCW:$W_Y$を乗算することで、RISによるMC推定となります。

$$ \langle I \rangle = f(Y)W_{Y} $$

結局、$\langle I_{\hat{p}} \rangle$に該当する部分がMultiple Importance Sampling化された部分以外は、同一確率密度関数を使ったRISと特に違いはありません。 不偏であるための条件等も、Multiple Importance Samplingの不偏条件に準じます。

RISのサンプル選択に関する重みづけ

RISでは、候補サンプルの中から$w_i$に比例した形でサンプルを選択します。$i$番目のサンプルを選択する確率:$p_s(i)$は以下のとおりです。 $$ p_s(i) = \frac{w_i}{\sum_{j=1}^{M}w_j} $$ このサンプルの選択による重みづけは、ここまで言及していませんでしたが、確率的選択をするという事は、その重みづけが必要になってくるはずです。

ここで、RISの候補サンプルごとに、ある寄与関数:$g_i(x)$を定義します。これは、とりあえずのRISの被積分関数だと考えてください。 そこで、$w_i$に比例した形で、あるサンプルインデックス:$s$が選択されたとします。寄与関数:$g_s(x)$に、対応するUCW:$W_{X_s}$を乗じたものに、さらに選択確率の重みづけ:$1/p_s(s)$を乗じたものの期待値を考えます。この期待値は、選択サンプルの全て場合の、選択確率に基づく加重平均と等しいはずです。 したがって、各々の加重平均の重み（分子側）と、選択確率に基づく重みづけ（分母側）は、相殺します。結果的に$g_i(X_i)W_i$の総和が残り、これは、$g_i(x)$の積分の総和に等しくなります。 $$ E[\frac{g_s(X_s)W_{X_s}}{p_s(s)}] = E[\sum_{i=1}^{M}g_i(X_i)W_i \frac{p_s(i)}{p_s(i)}] = \sum_{i=1}^{M} \int_{\Omega} g_i(x) dx $$

では逆に、右辺が、もともとの被積分関数:$f(x)$の積分になるように$g_i(x)$を考えると、$g_i(x)$は以下のようであるべきだと分かります。 $c_i(x)$は同じサンプル値$x$において、総和が1になるとします。これはMISウエイトと同じ考え方です。

$$ \text{if} \quad g_i(x) = c_i(x)f(x) \qquad \text{with} \quad \sum_{i=1}^{M} c_i(x) = 1, $$

$$ E[\frac{c_s(X_s)f(X_s)W_{X_s}}{p_s(s)}] = E[\sum_{i=1}^{M} c_i(X_s)f(X_s)W_{X_s}]= \int_{\Omega} f(x) dx $$

UCWは、$f(x)$との乗算の期待値が$f(x)$の積分になる値であるべきなので、RISのサンプル選択を行ったら、UCWは以下のように更新されるべきです。

$$ W_Y = c_s(X_s) \frac{\sum_{j=1}^{M}w_j}{w_s}W_{X_s} $$

$w_s$を展開すると、以下の式が得られます。$X_s$は選択されたサンプルなので$Y$と表記します。

$$ W_Y = \frac{c_s(Y)}{m_s(Y)} \frac{1}{\hat{p}(Y)} \sum_{j=1}^{M}w_j $$

$m_i(x)$は$\langle I_{\hat{p}} \rangle$の推定で使われるMISウエイトなので、リサンプリングMISウエイトと呼ばれ、$c_i(x)$は$\langle I \rangle$の推定で使われるMISウエイトなので、Contribution MIS Weights, 寄与MISウエイトと呼ばれます。$m_i(x)$と$c_i(x)$に同じ関数を使用した場合は、$W_Y$の式の先頭にある係数は相殺されるので、元のRISの式と一致します。Contribution MIS Weightsについては、後の項で軽く触れます。

RISにおけるMISウエイトについて

Balance Heuristicsについて

$$ m_i(x) = \frac{p_i(x)}{\sum_{j=1}^{M}p_j(x)} $$

Balance Heuristicsは、Multi Importance Samplingにおいて一般的に良いMISウエイトを算出できます。RISにおいても、リサンプリングMISウエイトで一般的に良いとされているのは、Balance Heuristicsです。 しかし、RISの候補に使うサンプリング戦略数:$M$が増えると、分母の総和の項数が多くなり計算コストが高くなります。例えば、$M=20$のRISを計算する時には、確率密度関数を400回評価しないと全てのMISウエイトが計算できません。計算量は$O(M^2)$になります。加えて、RISを再帰的に適用した場合の候補サンプルは、そのサンプルを生成した確率密度関数:$p(x)$が簡単に導出できない場合があります。そのため、MISウエイトの計算自体が困難になることがあります。そのため、RISにおいてBalance Heuristicsは、サンプリング戦略数が少なく、各戦略の確率密度関数が計算可能な時に実用的であるといえると思います。

Generalized Balance Heuristics

RISを再帰的に適用する場合、候補サンプルのUCWは必ず計算されていますが、候補サンプルの確率密度関数がわからない、もしくは追跡するのが困難な場合があります。そのため、リサンプリングMISウエイトに、Balance Heuristicsの代わりとしてGeneralized Balance Heuristicsを使うことが考えられます。 このMISウエイトは、RISで選択されたサンプルは、ある程度$\hat{p}(x)$の分布に基づくものになっているという仮定のもと、以下のようにリサンプリングMISウエイトを計算します。

$$ m_i(x) = \frac{\hat{p_i}(x)}{\sum_{j=1}^{M}\hat{p_j}(x)} $$

このMISウエイトが不偏性を維持するためには、$supp(\hat{p})$が、対応する候補サンプルの取りうる範囲に含まれている必要があります。

Contribution MIS Weights

前の項で示した通り、RISのMISウエイトにBalance Heuristics等を使うと、最悪で$O(M^2)$の計算コストがかかります。計算コストを削減しつつ、MISを適用する方法として、 リサンプリングMISウエイトと寄与MISウエイトに、別の関数を使う方法があります。リサンプリングMISウエイトは、候補サンプルの数だけ計算されるのに対して、寄与MISウエイトは、サンプル選択後に一度だけ計算されるので、例えば、リサンプリングMISウエイトに$m_i()=1/M$などの比較的簡単な関数を使い、寄与MISウエイトにBalance Heuristics、もしくはGeneralized Balanced Heuristicsを使うことが考えられると思います。こうすることで、$O(M^2)$だったBalance Heuristicsの計算コストを、O(M)に削減することができます。ただし、このRIS推定の分散は、リサンプリングMISウエイトにBalance Heuristicsを使った場合に比べて分散が増えてしまいます。

Pairwise MIS Weight

Pairwise MISの考え方は、実践的なReSTIRのアルゴリズムと一緒に考えるとわかりやすいです(この記事ではReSTIRのアルゴリズムについては言及しません。詳しくは他の資料を当たってください)。たとえば、ReSTIRのリサンプリング過程で、過去のピクセルや、近傍のピクセルのRISと、現在評価中のピクセルのRISを結合してリサンプリングするとします。この場合、現在評価中のピクセルのRISのサンプルが基準のサンプルとなります。これをPairwise MISでは、Canonical Sampleと呼びます。Canonical Sampleの分布は、被積分関数:$f(x)$のサポートを1サンプルで覆います。そしてリサンプリングMISウエイトは、Canonical Sampleと他のサンプルとの相対的な関係で計算します。ここで、Canonical Sampleのインデックスを$c$とします。

$$ \begin{align} m_i(x) &= \frac{1}{M-1}\frac{p_i(x)}{p_i(x) + p_c(x)}, & \text{if} \quad i &\ne c \newline m_c(x) &= \frac{1}{M-1}\sum_{i\ne c}^{M} \frac{p_c(x)}{p_i(x) + p_c(x)}, & \text{if} \quad i &= c \end{align} $$

Canonical SampleのMISウエイトのみ、$O(M)$の計算量が必要となりますが、Balance Heuristicsよりも計算コストが低いのがわかります。そして、MISウエイトの総和が1になる条件を満たしているのは、式より簡単にわかります。ただし、上式は、Canonical Sampleに、不必要に大きなウエイトを割り振ってしまいます。例えば、全てのサンプルが同一の$p(x)$より生成されていると仮定した場合、理想的には、全てのMISウエイトは等しくなるべきですが、$m_c(x)$が全体のほぼ$1/2$のウエイトを占めてしまいます。
このことを考慮すると、上式は以下のように修正されます。

$$ \begin{align} m_i(x) &= \frac{1}{M-1}\frac{p_i(x)}{p_i(x) + p_c(x)/(M-1)}, & \text{if} \quad i &\ne c \newline m_c(x) &= \frac{1}{M-1}\sum_{i\ne c}^{M} \frac{p_c(x)/(M-1)}{p_i(x) + p_c(x)/(M-1)}, & \text{if} \quad i &= c \end{align} $$

さらに、上式にGeneralized Balance Heuristicの考え方を導入すれば、Generalized Pairwise MISになります。

$$ \begin{align} m_i(x) &= \frac{1}{M-1}\frac{\hat{p_i}(x)}{\hat{p_i}(x) + \hat{p_c}(x)/(M-1)}, & \text{if} \quad i &\ne c \newline m_c(x) &= \frac{1}{M-1}\sum_{i\ne c}^{M} \frac{\hat{p_c}(x)/(M-1)}{\hat{p_i}(x) + \hat{p_c}(x)/(M-1)}, & \text{if} \quad i &= c \end{align} $$

関数$\hat{p}(x)$は、あくまで、それぞれのRISサンプルが十分な数になった時に推定として有効な関数なので、Canonical Sample以外の$m_i(x)$の値が大きいにもかかわらず、そのサンプルの信頼性が低い場合も考えられます。Canonical Sampleは、被積分関数のドメイン由来のサンプルなので、これを優先するようにウエイトに固定で、$1/M$を加えることで、保守的なリサンプリングMISウエイトにすることができます。

$$ \begin{align} m_i(x) &= \frac{1}{M}\frac{\hat{p_i}(x)}{\hat{p_i}(x) + \hat{p_c}(x)/(M-1)}, & \text{if} \quad i &\ne c \newline m_c(x) &= \frac{1}{M} \Big( 1 + \sum_{i\ne c}^{M}\frac{\hat{p_c}(x)/(M-1)}{\hat{p_i}(x) + \hat{p_c}(x)/(M-1)} \Big), & \text{if} \quad i &= c \end{align} $$

Canonical Sampleとその他のサンプルの信頼性に相対的な指標を適用したい場合は、サンプルごとにConfidence Weight:$c_i$を導入することもできます。例えば、この値は、それまでRISで選択対象になったサンプル数などを基準にすることが考えられます。

$$ \begin{align} \text{where} \quad c = \sum_{j=1}^{M} c_j, \newline m_i(x) &= \frac{c_i}{c}\frac{(c - c_c)\hat{p_i}(x)}{(c- c_c)\hat{p_i}(x) + c_c\hat{p_c}(x)}, & \text{if} \quad i &\ne c \newline m_c(x) &= \frac{c_c}{c} + \sum_{i\ne c}^{M} \frac{c_i}{c} \frac{c_c \hat{p_c}(x)}{(c - c_c)\hat{p_i}(x) + c_c \hat{p_c}(x)}, & \text{if} \quad i &= c \end{align} $$

Confidence Weightを導入して、Canonical Sampleを保守的に選択しなくて良い場合は元の形にConfidence Weightを適用したものを使用できます。

$$ \begin{align} m_i(x) &= \frac{c_i\hat{p_i}(x)}{(c- c_c)\hat{p_i}(x) + c_c\hat{p_c}(x)}, & \text{if} \quad i &\ne c \newline m_c(x) &= \sum_{i\ne c}^{M} \frac{c_i}{c} \frac{c_c \hat{p_c}(x)}{(c - c_c)\hat{p_i}(x) + c_c \hat{p_c}(x)}, & \text{if} \quad i &= c \end{align} $$

---