📂머신러닝

몬테 카를로 적분

개요

몬테 카를로 적분은 주어진 함수의 적분을 계산하기 어려울 때 사용하는 수치적인 근사 방법 중 하나이다. 다음과 같은 상황을 가정하자. 주어진 $[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}$$