重点サンプリング

  • ????????????????????

重点サンプリング (Importance Sampling) について。\(p(x)\) を密度関数として、物理量 \(f(x)\) の平均値

\begin{align}
I=\int f(x)p(x)dx
\end{align}

を近似する問題。

モンテカルロ積分

ふつうのモンテカルロ法では \(p(x)\) からN個サンプリングしてきて

\begin{align}
\frac1N\sum_{i=1}^N f(x_i)
\end{align}

と近似する。密度関数 \(p(x)\) からサンプリングできない場合や、分布の裾のほうの物理量が重要になる場合 (リスクの評価とか) は重点サンプリングを使うとよい場合がある。

重点サンプリング

概念はシンプル。\(\text{supp} \; p\subset\text{supp} \; q\) となるような任意の分布 \(q(x)\) に対して

\begin{align}
I=\int f(x)p(x)dx=\int f(x)\frac{p(x)}{q(x)}q(x)dx
\end{align}

なので、新しい物理量を \(\hat f(x)=f(x)p(x)/q(x)\) と定義して、\(q(x)\) からのサンプリングでモンテカルロを適用するというのが重点サンプリングの基本的な考え方。

\begin{align}
\frac1N\sum_{i=1}^N \hat f(x’_i)
\end{align}

ここで \(x’_i\) は \(q(x)\) からのサンプリング。

例題:分布の裾の確率の測定

標準正規分布に従う乱数が 10 より大きくなる確率を推定したい、とする(以下、すべてR言語)。この問題は

#  The exact value:
p.star <- pnorm(-10)
# => 7.619853e-24

のように、解 \(p^*\) がわかっているので、都合がいい。乱択アルゴリズム的な発想で、もっともシンプルな方法としては

  • 標準正規分布からひたすらサンプリングして 10 を超える割合をカウントする

とする方法がすぐに思いつく。これはモンテカルロ法の枠組みにあてはめれば、

\begin{align}
\int^\infty_{-\infty}I(x>10)p(x)dx
\end{align}

をモンテカルロ法で近似することに相当する。ここで I は特性関数であり、上で言うところの物理量に相当する。

ふつうのモンテカルロ法の使用

これをモンテカルロ法で推定しようとすると重大な問題に遭遇する。この場合はひとつ 10 を超える値をサンプリングするまでに要するサンプリング回数は典型的に

N <- 1.0/p.star
# => 1.312361e+23
# This is impossible!! (1/4 of Avogadro constant!!)

となり、不可能である(アボガドロ数のオーダーになってしまっている!【参考→アボガドロ数を実感する】)。ためしに \(10^9\) 程度のサンプリングをしてみても、推定される確率は当然 (ほぼ確実に[1]) ゼロになる。

N.mc <- 10^9     # One billion
huge.amount.of.r.v <- rnorm(N.mc)
estimated.MC <- mean(huge.amount.of.r.v > 10)
# => 0
rm(huge.amount.of.r.v) # サイズがでかいので消しておく

仮に、ものすごく幸運にも \(10^9\) のサンプルの中の1つに 10 を超えるものがあったとする。その場合、積分の推定値は

1.0/N.mc
# => 1e-09

となり、マイナス 24乗のオーダーである真値とはかけ離れた推定値が得られてしまう。ようするにいずれの場合もうまく行かず、この方針を取る限り、サンプル数をもっともっと増やしていくしかないことになる。

重点サンプリングの使用

ここで重点サンプリングを使ってみる。上での問題点は分布の裾のあたりの値がなかなかサンプリングされないことに起因していたので、とりあえず「提案分布」\(q(x)\) 平均 10、分散 5 の正規分布としてみる。これはこの分布であれば分布の裾をサンプリングできそうだよね、という直感で決めた。

この提案分布を使って重点サンプリングの式に沿って計算してみる:

# We use rnorm(x,10,5) as 'proposal distribution'
mega.amount <- rnorm(N.mc,10,5)
mean((mega.amount > 10) * 
     (dnorm(mega.amount)/dnorm(mega.amount,10,5)))
# => 6.802568e-24    # This is similar to p.star!!

ということで、得られた値 \(6.80\times 10^{-24}\) はわりと真の値に近いものがえられた。

ただし 32bit マシンではメモリ不足でエラーが出るので以下のように対処

# We use rnorm(x,10,5) as 'proposal distribution'
mega.amount.of.r.v <- rnorm(N.mc,10,5)
estimated.IS.divided <- rep(0,100)
for(i in 1:100){
  origin <- (i-1)*100+1
  divided <- mega.amount.of.r.v[origin:(origin+99)]
  estimated.IS.divided[i] <- 
    mean((divided > 10) * (dnorm(divided)/dnorm(divided,10,5)))
}
estimated.IS <- mean(estimated.IS.divided)

まとめ

通常のモンテカルロではかなり厳しい積分を、提案分布 \(q(x)\) の工夫によって現実的に実行できそう。

次回予告

  • サンプル数を増加させた時の誤差の減少の仕方
  • 提案分布 \(q(x)\) の誤差への影響
はてなブックマーク - 重点サンプリング
Pocket

  1. [1] 測度論的な意味ではなくて…