logo

重要度サンプリング 📂機械学習

重要度サンプリング

説明

つまり、重要度サンプリングは、以下のようにモンテカルロ積分を計算することだ。

以下の使用方法が役立つ。

  • ビルドアップの例のように、$p(x)$の尾が薄すぎる場合、サポートが大きい分布を提案関数として用いる。
  • $p(x)$の分布からサンプリングするのが難しい場合、サンプリングしやすい分布を提案関数$q(x)$として用いる。

$q$が$p$の分母に乗じられるため、$\supp q$は$\supp p$を含む必要がある。

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

3516_IS.png

# 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}$ならば、等号が成り立つ。