📂機械学習

重要度サンプリング

概要¹

導入

標準正規分布において$z$値が$4$以上である確率は約$3.167 \times 10^{-5}$である。

$$ \begin{equation} \int_{4}^{\infty} \dfrac{1}{\sqrt{2\pi}} e^{-z^{2}/2}dz \approx 3.167 \times 10^{-5} \end{equation} $$

この積分をモンテカルロ積分で計算するJuliaコードは次の通りである。

using Distributions

n = 50000                      # sample size
z₀ = 4.0

for i in 1:5
    z = rand(Normal(), n)      # n-samples drawn from a standard normal distribution 
    est_MC = sum(z .> z₀)/n    # estmiates using Monte Carlo
    println(est_MC)
end

4.0e-5
6.0e-5
0.0
4.0e-5
4.0e-5

五回ほど試してみると計算された値は真値と似ておらず、さらには$0$と計算されることさえある。このような不正確さは標準正規分布の裾があまりに薄いために生じる。紙の上で積分するときは裾がどんなに薄くてもそれに対する計算が積分に含まれるが、コンピュータでサンプリングするときは有限のサンプルのみを扱うため、発生確率があまりに低い事象は計算に含まれないことがある。もちろん$n$を増やせばより正確になるだろうが、これはあまりにも当然のことであり、こういうものを解決方法とは呼ばない。

$$ \int f(x)p(x) dx = \int f(x)\dfrac{p(x)}{q(x)} q(x) dx = \int \left[ f(x)\dfrac{p(x)}{q(x)} \right] q(x) dx $$

さて、確率密度関数が$p$である確率変数$X$について、$f(X)$の期待値を計算する状況を考えてみよう。これは上の式の左辺のように計算できるが、ここで何らかの$q(x)$で割って掛けても依然として同じ値である。式の右辺は左辺と同じ値を持つが、意味は「確率密度関数が$q$である確率変数$X$について$f(X)\dfrac{p(X)}{q(X)}$の期待値」となる。ここで$q$を$p$より裾の厚い確率密度関数として選べば、発生確率のあまりに低い事象による不正確さを減らすことができる。

定義

$X$を確率密度関数が$p$である確率変数としよう。$q$を次を満たすもう一つの確率密度関数としよう。

$$ \supp p \subset \supp q \qquad (\iff q\ne 0 \text{ if } p \ne 0) $$

重要度サンプリング^{importance sampling}とは、$f(X)$の期待値$E_{p}[f(X)]$を$E_{q}[f(X)\frac{p(X)}{q(X)}]$として計算して求める方法をいう。このとき$\supp$は関数のサポートである。

$$ E_{p}[f] = \int f(x)p(x) dx = \int \left[ f(x)\dfrac{p(x)}{q(x)} \right] q(x) dx = E_{q}[fp/q] $$

ここで$q$を提案分布^{proposal distribution}、$w = \frac{p}{q}$を重要度重み^{importance weight}という。

説明

言い換えると、重要度サンプリングとはモンテカルロ積分を次のように計算することである。

$$ \dfrac{1}{n}\sum f(x_{i})\dfrac{p(x_{i})}{q(x_{i})}, X_{i} \sim q(x) \quad \left( \text{instead of } \dfrac{1}{n}\sum f(x_{i}), X_{i} \sim p(x) \right) $$

次のように使うと役立つ。

• ビルドアップでの例のように$p(x)$の裾があまりに薄いとき、サポートがより大きい分布を提案関数とする。
• $p(x)$の分布でサンプリングしにくいとき、サンプリングしやすい分布を提案関数$q(x)$とする。

$q$が$p$の分母として掛けられるため、$\supp q$は$\supp p$を含まなければならない。

ビルドアップの積分$(1)$をコーシー分布を提案分布として重要度サンプリングで計算し直した結果は次の通りである。

# Julia code

using Distributions

n = 50000                      # sample size
z₀ = 4.0

for i in 1:5
    z = rand(Cauchy(), n)                       # n-samples drawn from a Cauchy distribution 
    w = pdf.(Normal(), z) ./ pdf.(Cauchy(), z)
    est_IS = sum(w[z .> z₀])/n                  # estmiates using Importance Sampling
    println(est_IS)
end

3.0330744703037005e-5
3.1808448538011614e-5
3.049259883894785e-5
3.305423127141489e-5
3.1807695818207125e-5

性質

不偏推定量

$\dfrac{1}{n}\sum\limits f(x_{i})\dfrac{p(x_{i})}{q(x_{i})}$は$E_{p}[f(X)]$の不偏推定量である。

証明

$$ \begin{align*} E_{q}\left[ \frac{1}{n}\sum_{i}^{n}f(X_{i})\dfrac{p(X_{i})}{q(X_{i})} \right] &= \frac{1}{n}\sum_{i}^{n} E_{q}\left[ f(X_{i})\dfrac{p(X_{i})}{q(X_{i})} \right] &\text{by linearity of $E$} \\ &= E_{q}\left[ f(X)\dfrac{p(X)}{q(X)} \right] \\ &= E_{p}\left[ f(X) \right] \end{align*} $$

■

分散

重要度サンプリングにおける分散は

$$ \begin{align} \Var \left[ \frac{fp}{q} \right] &= E_{q}\left[ \left( \frac{fp}{q} \right)^{2} \right] - \left( E_{q}\left[ \frac{fp}{q} \right] \right)^{2} \\ &= \int \frac{f(x)^{2}p(x)^{2}}{q(x)} dx - \left( \int f(x)p(x) dx \right)^{2} \nonumber \end{align} $$

であるため、有限な分散を持つためには次が成り立たなければならない。

$$ \int \frac{f(x)^{2}p(x)^{2}}{q(x)} dx \lt \infty $$

これは$p(x)/q(x)$が有界でなければならないという意味であり、これはさらに$q(x)$の裾が$p(x)$の裾より厚くなければならないという意味と同じである。分散を最小化する$q$は次の通りである。

$$ q^{\ast} = \argmin\limits_{q} \Var [fp/q] = \frac{ \left| f(x) \right| p(x)}{ \int \left| f(x) \right| p(x) dx} $$

証明

$(2)$において二番目の項は$q$に依存するように見えても、$E_{q}\left[ \frac{fp}{q} \right] = {\displaystyle \int} f(x)p(x)dx$であるため$q$とは無関係な値である。

$$ \argmin\limits_{q} \Var [fp/q] = \argmin\limits_{q} E_{q}\left[ \left( \frac{fp}{q} \right)^{2} \right] $$

イェンセンの不等式

開区間$I$で関数$\phi$が凸かつ二回微分可能で、確率変数$X$の期待値$\mu$が存在し$X \subset I $であれば $$ \phi [ E(X) ] \le E [ \phi (X)] $$

ところで二次関数は凸であるため、

$$ \begin{align*} && \left( E_{q}\left[ \frac{fp}{q} \right] \right)^{2} &\le E_{q}\left[ \left( \frac{fp}{q} \right)^{2} \right] \\ \implies && \left( \int f(x)p(x) dx \right)^{2} &\le \int \frac{f(x)^{2} p(x)^{2}}{q(x)} dx \end{align*} $$

ここで$q(x) = \frac{ \left| f(x) \right| p(x)}{ \int \left| f(x) \right| p(x) dx}$であれば等号が成立する。

■