メモ: Importance sampling(重点サンプリング)

概要

・サンプリングの難しい分布からのサンプリングを工夫することで期待値計算を効率的にする

Importance sampling

自分もよく分かっていない部分もあるので怪しいですが。ある期待値計算
$$
E \left( s \right) = \int s \cdot f \left( s \right) {\rm d}s
$$
をしたいけれど、\( f \left( \cdot \right) \)からサンプリングするのが難しいとする。
そんなときにサンプリングが簡単にできる\( g \left( \cdot \right) \)をもってくると
$$
E \left( s \right) = \int s \cdot f \left( s \right) {\rm d}s
= \int s \cdot \frac{f \left( s \right)}{g \left( s \right)} \cdot g \left( s \right) {\rm d}s
$$
と変形することができ、\( g \left( \cdot \right) \)からのサンプルで期待値を計算することができる。ここで\( \frac{f \left( s \right)}{g \left( s \right)} \)は重みと呼ばれる。

例題

参考サイト1に記載されている問題を考える。
「You want to simulate the mean of a standard normal distribution, truncated to the unit interval [0,1].」

[0, 1]だとImportance samplingの有り難みが分からないので、ここでは[2, 2.1]とする。
つまり、[2, 2.1]の範囲の標準正規分布の期待値を計算する。[2, 2.1]だとそもそもの範囲が狭いのと、標準正規分布で2以上の値を出すにはそれなりの試行回数が必要になると考えられるので、それなりにImportance samplingの有り難みが分かるはず

また、\( f \left( \cdot \right) \)の形は
$$
f \left( s \right) = \frac{\phi \left( x \right)}{\int_2^{2.1} \phi \left( x \right) {\rm d}z}
$$
となりまして、気合で標準正規乱数からサンプリングすることもできますが、\( f \left( \cdot \right) \)から直接サンプリングしたい場合には、はてどうやるんですかねという感じですね。\( \phi \left( \cdot \right) \)は標準正規分布の密度関数。

また、\( g \left( \cdot \right) \)は一様分布を用います。言わずもがな乱数を発生させるのが簡単なのと、[2, 2.1]の場合、\( g \left( x \right) = 10 \)となり、重みの計算も簡単になります。

Rコード

Brute force simulationと記載されているのはそのまま力技で期待値を計算する方法で、標準正規分布の乱数が[2, 2.1]の値をとった時のみ、期待値を計算するようにします。
当然ながらほとんどのサンプルがrejectされてしまうので、期待値が収束するまで時間がかかるはず。

一方でImportance samplingは一様分布を用いており、全てのサンプルを用いて期待値を計算することができる。
期待値の収束の過程をプロットしてみると以下。
黒線がBrute forceで、赤線がImportance samplingとなります。
黒線はなかなかサンプルが発生しないので収束まで時間がかかっていることが分かります。
150107_1

追記(21-Jan-2015)

効率の悪い書き方をしているような気がするので書き直し。結果を出力するために余分なコードが入っていますが基本的には同じ(はす)

参考

Lecture notes: Simulation
http://people.hss.caltech.edu/~mshum/gradio/simulation.pdf

パーティクルフィルタ
http://watanabe-www.math.dis.titech.ac.jp/~miki_t/pdf/s1114.pdf?bcsi_scan_4c5c01dba4894524=0&bcsi_scan_filename=s1114.pdf