重点サンプリングの分散

こんにちはtatsyです。

本日の研究室での会話です。

後輩: 重点サンプリングをするときの提案分布はどうして被積分関数に近い方が良いのですか？

私: 定性的には、被積分関数の値が大きい部分により多くのサンプルを配する方が全体の誤差が抑えれるからかな… (ん、定量的にはどうなんだっけ？)

となりまして、定量的にはどうなるのかが気になったので、調べてこちらにまとめておきます。

重点サンプリング

関数$ \chi $ 全体での積分は、

$$ \displaystyle I = \int_\chi f(x) dx $$

のようになるわけですが、これをコンピュータ上で求める場合には当然ながら離散的な形で書き表す必要があります。

もし積分区間が有限で$[ a, b ]$ であれば、区間を分割することで、

$$ \displaystyle I \approx \frac{1}{N} \sum_{i=1}^N f(x_i) \qquad x_i = a + \frac{b - a}{N} i $$

のようにして、近似的に求めることができると思います。

ところが$ \chi $ が高次元空間の場合には、上記のような離散化をすると、とんでもない数の和を取らねばならなくなり、計算コストが高くなりすぎるという問題があります。

そのため、上記の積分を少数のサンプリングから効率よく求めるための方法がいくつも提案されています。その一つが重点サンプリング (importance sampling) です。

重点サンプリングでは、積分の式を、

$$ \displaystyle I = \int_\chi f(x) dx = \int_\chi \frac{f(x)}{p(x)} p(x) dx $$

のように書き直します。上記の式を離散化する場合には、サンプル$X_i \sim p(x)$と書きます) ことで、

$$ \displaystyle I \approx \sum_{i=1}^N \frac{f(X_i)}{p(X_i)} \qquad X_i \sim p(x) $$

と書き直すことができます。このとき、$p(x)$のことを提案分布と呼びまして、この提案分布が元々の被積分関数に近くなれば、重点サンプリングによる推定値の分散が小さくなることが知られています。

重点サンプリングの分散を最小化する

一般に、分散は平均と測定値の二乗誤差を足し合わせたものなので、$p(x)$による重みづけを考慮した分散は、

$$ \displaystyle \sigma^2 = \displaystyle \int_\chi \left( I - \frac{f(x)}{p(x)} \right)^2 p(x) dx $$

のように書くことができます。この式を展開して整理していくと、

$$ \begin{aligned} \sigma^2 &= \displaystyle \int_\chi \left( I - \frac{f(x)}{p(x)} \right)^2 p(x) dx \\ &= {\displaystyle I^2 \int_\chi p(x) dx - 2I \int_\chi \frac{f(x)}{p(x)} p(x) dx + \int_\chi \frac{f^2(x)}{p^2(x)} p(x) dx} \\ &= \int_\chi \frac{f^2(x)}{p^2(x)} p(x) dx - I^2 \end{aligned} $$ となります。なお、この式変形では、$I$ が定数であることを使っています。

この式に従えば、 $$ J^2 = \int_\chi \frac{f^2(x)}{p^2(x)} p(x) dx $$が、より$I^2$に近いときに$p(x)$が提案分布としてよりふさわしいことが分かります。

そこで$J^2$をさらに変形していきます。 $$ \begin{aligned} J^2 &= \int_\chi \frac{f^2(x)}{p^2(x)} p(x) dx \\ &= \int_\chi \left( \frac{f(x)}{p(x)} \right)^2 p(x) dx \int_\chi 1^2 p(x) dx \\ &\geq \left( \int_\chi \left( \frac{|f(x)|}{p(x)} \cdot 1 \right) p(x) dx \right)^2 \\ &= \left ( \int_\chi \frac{|f(x)|}{p(x)} p(x) dx \right)^2 \end{aligned} $$ となります ($p(x) \geq 0$と仮定)。

この式の中では、連続関数版のコーシー・シュワルツの不等式により大小関係が与えられていて、等式は$\frac{|f(x)|}{p(x)} = 1$の時に成り立ちます。

コーシー・シュワルツの不等式は両辺を各関数のノルムの二乗で割ると、2つの関数のコサイン距離が小さい場合に、よりタイトに不等式を満たすことが分かります (こちらのブログ記事が参考になると思います)。

ですので、実際には$|f(x)|$が$p(x)$ (の定数倍) に「より近いとき」に、重点サンプリングはより小さな分散を取ることが分かります。

ただし、このときの「より近い」の意味は確率$p(x)$による積分である $$ \displaystyle \int_\chi \frac{|f(x)|}{p(x)} p(x) dx $$ がより1に近いことが必要になるため、単に$|f(x)|$と$p(x)$の比が1に近いだけでなく、$p(x)$の値がより大きいところでは、よりその比が1に近い方が良いことも同時に分かります。

まとめ

今回は重点サンプリングの提案分布として、被積分関数に近いものを使った方が良い理由を理屈として説明してみました。

この説明を見てみると、単に非積分関数同士の距離(例えばL2距離のようなもの)が近いという意味ではなく、両関数の比が1に近いことが重要であることも分かります。

さらに、より提案分布が大きい場所では、より比が1に近い方が良いということも分かり、かなり理解が進んだ気がします。

それでは、この辺りで今回の記事を終わりにします。最後までお読みいただき、ありがとうございました。