📂機械学習

モンテカルロ積分

概要

モンテカルロ積分は、与えられた関数の積分を計算するのが困難な場合に使用される数値的近似方法の一つである。次のような状況を想定しよう。与えられた $[0, 1]$^{または一般的に $[0, 1]^{n}$}で積分可能な関数 $f$に対して、私たちは $f(x)$の式を知っているが、その積分を計算するのは簡単ではない。しかし、私たちは $f$の積分 $I[f]$を計算したい。

$$\begin{equation} I[f] = \int_{[0,1]} f(x) dx \end{equation}$$

定義

モンテカルロ積分^{Monte Carlo integration}とは、与えられた $[0, 1]$ 上での分布に基づきサンプル $\left\{ x_{i} \right\}$を抽出し、$f$の積分を次のように推定^estimateする方法である。

$$I[f] \approx I_{n}[f] := \dfrac{1}{n}\sum_{i=1}^{n} f(x_{i})$$

区分求積法との違い

区分求積法のアイデアは、区間 $[0,1]$を $n$等分し、点 $\left\{ x_{i} = \frac{i-1}{n} \right\}_{i=1}^{n}$を得て、これらの点での関数値を全て加算することである。

$$\text{区分求積法}[f] = \dfrac{1}{n}\sum_{i=1}^{n} f(x_{i})$$

式の見た目だけではモンテカルロ積分と区分求積法は異なるもののないように見えるが、その意味は全く異なる。区分求積法での $\left\{ x_{i} \right\}$は区間 $[0, 1]$を $n$等分して得た点であるのに対し、モンテカルロ積分では $x$が従う分布 $p(x)$から抽出された $n$個のサンプルを意味する。したがって、区分求積法で得られた値は単純に $f$が描くグラフの下の面積を意味するが、モンテカルロ積分で得られた値は $f$の期待値である。

性質

式 $(1)$が持つ統計的な意味は「$I[f]$は $X$が一様分布に従うときの $f(X)$の期待値と同じである」ということである。

$$X \sim U(0,1) \implies I[f] = \int_{[0,1]} f(x) dx = E\left[ f(X) \right]$$

期待値

確率変数 $X$が一様分布に従うとしよう。$I_{n}[f]$は $I[f]$の不偏推定量である。

$$E\left[ I_{n}[f] \right] = I[f]$$

証明

$$\begin{align*} E\left[ I_{n}[f] \right] &= E\left[ \dfrac{1}{n} \sum\limits_{i=1}^{n} f(X_{i}) \right] \\ &= \dfrac{1}{n} \sum\limits_{i=1}^{n} E\left[ f(X_{i}) \right] \qquad \text{by linearity of$$$E$} \\ &= \dfrac{1}{n} \sum\limits_{i=1}^{n} I\left[ f \right] \\ &= I\left[ f \right] \end{align*}

■

分散

証明

分散の性質

[a] $\Var (aX) = a^{2} \Var (X)$

[b] $X, Y$が独立ならば、$\Var (X + Y) = \Var(X) + \Var(Y)$

$f(X)$の分散を $\sigma^{2}$としよう。すると分散の性質により、

$$\begin{align*} \Var \left[ I_{n}[f] \right] &= \Var \left[ \dfrac{1}{n} \sum\limits_{i=1}^{n} f(X_{i}) \right] \\ &= \dfrac{1}{n^{2}} \Var \left[ \sum\limits_{i=1}^{n} f(X_{i}) \right] \\ &= \dfrac{1}{n^{2}} \sum\limits_{i=1}^{n} \Var \left[ f(X_{i}) \right] \\ &= \dfrac{1}{n^{2}} \sum\limits_{i=1}^{n} \sigma^{2} \\ &= \dfrac{\sigma^{2}}{n} \end{align*}$$

■

一般化

ここで $p(x) \ge 0$で $\int_{[0,1]} p = 1$となる関数 $p$について、積分 $I[fp]$を考えよう。

$$I[fp] = \int_{[0, 1]}f(x)p(x) dx$$

これは確率密度関数が $p$である確率変数 $X$について、$f(X)$の期待値と同じである。この値を近似する方法として、次の二つの方法が考えられる。

1. サンプル $\left\{ x_{i} \right\}_{i=1}^{n}$を一様分布から抽出し、$I[fp]$を次のように近似する。

$$X_{i} \sim U(0,1) \qquad I[fp] \approx \dfrac{1}{n}\sum\limits_{i}f(x_{i})p(x_{i})$$

2. サンプル $\left\{ x_{i} \right\}_{i=1}^{n}$を $p(x)$から抽出し、$I[fp]$を次のように近似する。

$$X_{i} \sim p(x) \qquad I[fp] = I_{p}[f] \approx \dfrac{1}{n}\sum\limits_{i}f(x_{i})$$

言い換えれば、1.は $f(x)p(x)$を一様分布でサンプリングして平均を求めたものであり、2.は $f(x)$を $p(x)$でサンプリングして平均を求めたものである。これらのうち分散がより小さいのは1.である。$I = I[fp] = I[fp]$と簡単に記しよう。

• 1.の場合 $$\begin{align*} \sigma_{1}^{2} = \Var [fp] &= E \left[ (fp - I)^{2} \right] \\ &= \int (fp - I)^{2} dx \\ &= \int (fp)^{2} dx - 2I\int fp dx + I^{2}\int dx\\ &= \int (fp)^{2} dx - 2I^{2} + I^{2}\\ &= \int (fp)^{2} dx - I^{2}\\ \end{align*}$$

• 2.の場合 $$\begin{align*} \sigma_{2}^{2} = \Var [f] &= E_{p} \left[ (f - I)^{2} \right] \\ &= \int (f - I)^{2}p dx \\ &= \int f^{2}p dx - 2I\int fp dx + I^{2}\int pdx\\ &= \int f^{2}p dx - 2I^{2} + I^{2}\\ &= \int f^{2}p dx - I^{2}\\ \end{align*}$$

しかし $0 \le p \le 1$であるため、$f^{2}p \ge f^{2}p^{2}$である。したがって

$$\sigma_{1}^{2} \le \sigma_{2}^{2}$$