몬테카를로 방법 (Monte Carlo Method)과 베이지안 머신러닝

1. 큰 수의 법칙 (Law of Large Numbers, LLN)

이 글에서 소개할 몬테카를로 방법 (Monte Carlo method)은 큰 수의 법칙을 기반으로 하며, 큰 수의 (약한) 법칙은 동일한 확률분포에서 독립적으로 추출된 (i.i.d. 조건) 확률변수에 대해 아래와 같이 정의된다.

i.i.d. 확률변수 $X_1, X_2, ..., X_n$에 대해 $n$ 증가하면 $\bar{X} = \frac{X_1 + X_2 + \cdots + X_n}{n}$은 실제 기댓값 $\mu$로 수렴한다.

큰 수의 법칙은 샘플 (데이터)이 생성된 확률분포를 모르더라도 샘플로부터 확률분포에 대한 정보를 추정할 수 있음을 보여준다. 이러한 큰 수의 법칙을 직관적으로 나타내면 식 $\eqref{eq:lln}$과 같다.

$$\begin{equation} \lim_{n \rightarrow \infty} \frac{X_1 + X_2 + \cdots X_n}{n} = \mu \label{eq:lln} \end{equation}$$

그러나 엄밀히 정의하면 큰 수의 법칙에는 큰 수의 약한 법칙과 강한 법칙이 있으며, 식 $\eqref{eq:lln}$과는 약간 다르게 정의된다. 이 글에서는 큰 수의 약한 법칙을 그냥 큰 수의 법칙이라 하며, 큰 수의 약한 법칙에 대한 수학적 증명은 아래와 같다.

 

1.1. 체비쇼프 부등식 (Chebyshev inequality)

체비쇼프 부등식은 확률분포의 평균과 표준편차만 알고 있더라도 해당 분포를 따르는 특정 확률의 최솟값만큼은 계산하는 방법을 제공한다. 체비쇼프 부등식은 아래의 식 $\eqref{eq:chbs_inequ}$와 같다.

$$\begin{equation} P(|X - \mu| < \epsilon) \geq 1 - \frac{Var[X]}{\epsilon^2} \label{eq:chbs_inequ} \end{equation}$$

확률변수 $Z$의 밀도함수를 $f_Z$라 할 때, 체비쇼프 부등식에 대한 증명은 아래와 같다.

$$\begin{equation}\begin{aligned}[b] E[Z^2] &= \int_{\mathbb{R}} z^2 f_Z(z)dz\\ &\geq \int_{|z|\geq \epsilon} z^2 f_Z(z)dz\\ &\geq \epsilon^2 \int_{|z|\geq \epsilon} f_Z(z)dz\\ &= \epsilon^2 P(|Z| \geq \epsilon) \end{aligned} \label{eq:chbs_inequ_proof} \end{equation}$$

확률변수 $X$와 $X$의 실제 평균 (true mean) $\mu$에 대해 $Z = X - \mu$라고 하면, 식 $\eqref{eq:chbs_inequ_proof}$은 아래와 같다.

$$\begin{equation} P(|X - \mu| \geq \epsilon) \leq \frac{E[(X - \mu)^2]}{\epsilon^2} \label{eq:chbs_inequ_proof2} \end{equation}$$

분산에 대한 정의 $E[(X - \mu)^2] = Var[X]$와 확률의 대한 성질 $1 - P(|X - \mu| \geq \epsilon) = P(|X - \mu| < \epsilon)$을 적용하면 식 $\eqref{eq:chbs_inequ_proof2}$는 식 $\eqref{eq:chbs_inequ}$의 체비쇼프 부등식과 같음을 알 수 있다.

 

1.2. 큰 수의 약한 법칙 (Weak Law of Large Numbers)과 수학적 증명

큰 수의 약한 법칙은 샘플의 수가 증가하면 i.i.d. 확률변수 $X_1, X_2, ..., X_n$으로부터 계산된 샘플 평균과 실제 평균 $\mu$의 차이가 어떠한 양의 실수 $\epsilon$보다 클 확률이 0으로 수렴함을 말한다. 큰 수의 약한 법칙을 수학적으로 서술하면 아래의 식 $\eqref{eq:weak_lln}$와 같다. 샘플의 평균 자체가 $\mu$와 같아진다는 큰 수의 강한 법칙 (strong law of large numbers)은 이 문서에 서술되어있다.

$$\begin{equation} \lim_{n \rightarrow \infty} P\left(\left| \frac{X_1 + X_2 + \cdots + X_n}{n} - \mu \right| \geq \epsilon \right) = 0 \label{eq:weak_lln} \end{equation}$$

$Var[X_i] = \sigma^2$이라 하면, 큰 수의 약한 법칙은 체비쇼프 부등식의 한 형태인 $\eqref{eq:chbs_inequ_proof2}$를 기반으로 다음과 같이 증명된다.

$$\begin{equation}\begin{aligned}[b] P\left(\left|\frac{X_1 + X_2 + \cdots + X_n}{n} - \mu \right| \geq \epsilon \right) &\leq \frac{1}{\epsilon^2} Var\left[\frac{X_1 + X_2 + \cdots + X_n}{n} \right]\\ &= \frac{1}{n^2 \epsilon^2} Var[X_1 + X_2 + \cdots + X_n]\\ &= \frac{\sigma^2}{n \epsilon^2} \end{aligned} \label{eq:proof_weak_lln} \end{equation}$$

따라서, $n \rightarrow \infty$이면 $\frac{\sigma^2}{n \epsilon^2} = 0$이므로, 아래와 같이 큰 수의 약한 법칙이 성립한다.

$$\begin{equation} \lim_{n \rightarrow \infty} P\left(\left|\frac{X_1 + X_2 + \cdots + X_n}{n} - \mu \right| \geq \epsilon \right) = 0 \label{eq:7} \end{equation}$$

 

2. 몬테카를로 적분 (Monte Carlo Integration)

몬테카를로 방법 (Monte Carlo method)은 무작위로 추출된 샘플을 바탕으로 함수의 값을 수리적으로 근사하는 알고리즘이다. 몬테카를로 방법의 한 응용으로써 몬테카를로 적분 (Monte Carlo integration)이 있으며, 몬테카를로 적분은 수학, 물리, 인공지능 등에서 매우 다양하게 활용되고 있다. 몬테카를로 적분은 독립적으로 추출된 샘플을 이용하여 적분값을 계산하기 위한 방법이다.

어떠한 함수 $f(x)$의 적분값을 계산하기 위한 몬테카를로 적분은 아래와 같이 유도된다. 식 $\eqref{eq:mci_drv}$에서 $\phi(\textbf{x})$는 $\textbf{x}$의 확률밀도함수이며, $\Omega$는 적분을 수행하려는 공간을 의미한다.

$$\begin{equation}\begin{aligned}[b] \int_\Omega f(\textbf{x}) d\textbf{x} &= \int_\Omega \frac{f(\textbf{x})}{\phi(\textbf{x})} \phi(\textbf{x}) d\textbf{x}\\ &= \text{E}_{\phi(\textbf{x})} \left[\frac{f(\textbf{x})}{\phi(\textbf{x})} \right] \end{aligned} \label{eq:mci_drv} \end{equation}$$

샘플의 수 $n$이 충분히 크면 식 $\eqref{eq:lln}$에서 설명한 큰 수의 법칙에 의해 식 $\eqref{eq:mci_drv}$은 아래와 같이 근사된다.

$$\begin{equation} \text{E}_{\phi(\textbf{x})} \left[\frac{f(\textbf{x})}{\phi(\textbf{x})} \right] \approx \frac{1}{n}\sum_{i=1}^n \frac{f(\textbf{x}_i)}{\phi(\textbf{x}_i)} \label{eq:mcidrv2} \end{equation}$$

최종적으로 함수 $f(\textbf{x})$의 적분값은 식 $\eqref{eq:mci}$과 같이 근사되며, 이를 일반화된 몬테카를로 적분 (general Monte Carlo integration)이라 한다.

$$\begin{equation} \int_\Omega f(\textbf{x}) d\textbf{x} \approx \frac{1}{n}\sum_{i=1}^n \frac{f(\textbf{x}_i)}{\phi(\textbf{x}_i)} \label{eq:mci} \end{equation}$$

몬테카를로 적분의 정확한 계산을 위해서는 $\textbf{x}$의 확률밀도함수인 $\phi(\textbf{x})$에 대한 정의가 필요하다. 몬테카를로 방법에서 $\phi(\textbf{x})$를 정의하기 위해 일반적으로 이용되는 것은 균등분포 (uniform distribution)이다. 단순한 균등분포를 가정하는 것이 어느정도 유효한 이유는 큰 수의 법칙에서 설명했다.

만약 $\textbf{x} \in [a, b]^d$가 균등분포를 따라 존재하는 변수라고 가정하면, $\phi(\textbf{x}) = 1 / (b-a)^d$가 되며 몬테카를로 적분은 식 $\eqref{eq:mci_uniform}$과 같다.

$$\begin{equation} \int_\Omega f(\textbf{x}) d\textbf{x} \approx \frac{(b - a)^d}{n} \sum_{i=1}^n f(\textbf{x}_i) \label{eq:mci_uniform} \end{equation}$$

따라서, 우리는 $f(\textbf{x})$의 역도함수 (antiderivative)인 $F(\textbf{x})$를 계산할 수 없는 경우에도 샘플 $\textbf{x}_1, \textbf{x}_2, ..., \textbf{x}_n$를 기반으로 몬테카를로 적분을 이용하여 함수의 적분값을 근사할 수 있는 것이다.

 

2.1. 몬테카를로 적분 예제: 원의 넓이

식 $\eqref{eq:mci_uniform}$에서 정의한 몬테카를로 적분의 예제로써 적분 계산 없이 원의 넓이를 구하는 방법을 소개한다. 물론 원의 넓이를 계산하기 위한 적분 문제는 삼각함수와 치환적분을 통해 계산할 수 있지만, 이 예제에서 보이는 방법은 임의의 함수 $f(\textbf{x})$에도 적용할 수 있다는 것이 중요하다.

그림 1. 원의 방정식과 원의 넓이

수학적으로 2차원 평면에 존재하는 반지름 $r$인 원은 그림 1a와 같이 식 $\eqref{eq:circle}$으로 정의된다.

$$\begin{equation} x^2 + y^2 = r^2 \label{eq:circle} \end{equation}$$

적분 계산을 통해 원의 넓이 $S$를 계산하기 위해서는 그림 1b와 같이 식 $\eqref{eq:int_circle}$을 계산해야한다. 그림 1b는 1사분면에 대한 원의 넓이만을 정의하기 때문에 식 $\eqref{eq:int_circle}$에서는 4를 곱했다.

$$\begin{equation} S = 4\int_0^r \sqrt{r^2 - x^2} dx \label{eq:int_circle} \end{equation}$$

삼각함수 기반의 치환적분 또는 $\pi r^2$이라는 원의 넓이 공식을 이용하면, 반지름이 3인 경우 ($r=3$) 원의 넓이는 약 28.274으로 계산된다.

$[0, 3]$의 범위에서 균등분포에 의해 무작위로 생성된 $n$개의 샘플 $x_1, x_2, ..., x_n$에 대해 몬테카를로 적분을 기반으로 원의 넓이를 근사하면 아래와 같다.

$$\begin{equation} 4\int_0^r \sqrt{9 - x^2}dx \approx \frac{12}{n} \sum_{i=1}^n \sqrt{9 - x_i^2} \label{eq:mci_circle} \end{equation}$$

샘플의 수 $n$의 증가에 따른 식 $\eqref{eq:mci_circle}$의 값은 그림 2와 같다. 파란색 실선은 몬테카를로 적분값이고, 검은색 점선은 식 $\eqref{eq:int_circle}$의 실제 적분값을 계산한 것이다.

그림 2. 몬테카를로 적분으로 계산한 원의 넓이

그림 2를 보면 큰 수의 법칙에 의해 샘플의 수가 증가할수록 몬테카를로 적분값이 실제 적분값 28.274에 근접하는 것을 확인할 수 있다. 따라서 우리는 몬테카를로 적분을 이용함으로써 $f(\textbf{x})$의 역도함수 $F(\textbf{x})$를 구하지 않고도 $f(\textbf{x})$의 적분값을 계산했다.

 

3. 확률모델을 위한 몬테카를로 적분

확률모델의 학습이나 추론 과정에서 가장 빈번하게 마주치는 문제는 식 $\eqref{eq:expectation}$와 같이 어떠한 확률분포를 따르는 변수 $\textbf{x} \in \mathcal{X}$와 관련된 기댓값을 계산하는 것이다.

$$\begin{equation} \text{E}_{\textbf{x} \sim p} \left[f(\textbf{x}) \right] = \int_\mathcal{X} f(\textbf{x}) p(\textbf{x}) d\textbf{x} \label{eq:expectation} \end{equation}$$

머신러닝에서는 일반적으로 $p(\textbf{x})$를 따르는 i.i.d. 샘플 $\textbf{x}_1, \textbf{x}_2, ..., \textbf{x}_n$에 대한 몬테카를로 적분을 기반으로 아래와 같이 $f(\textbf{x})$의 기댓값을 계산한다.

$$\begin{equation} \int_\mathcal{X} f(\textbf{x})p(\textbf{x}) d\textbf{x} \approx \frac{1}{n}\sum_{i=1}^N f(\textbf{x}_i) \label{eq:approx_expectation}\end{equation}$$

식 $\eqref{eq:approx_expectation}$의 결과는 식 $\eqref{eq:mci}$에서 $\phi(\textbf{x}) = p(\textbf{x})$일 때와 같다는 것을 알 수 있다. 대부분의 머신러닝 응용에서는 데이터 (샘플)이 주어지기 때문에 가능도나 사후확률과 같은 어떠한 함수 $f(\textbf{x})$의 기댓값을 계산해야하는 문제에서 우리는 몬테카를로 적분을 이용하여 이를 해결할 수 있는 것이다.

 

부록 1. 큰 수의 강한 법칙 (Strong Law of Large Numbers)

큰 수의 강한 법칙은 샘플의 평균이 실제 평균 $\mu$로 거의 확실하게 수렴한다는 법칙이다. 큰 수의 강한 법칙은 수학적으로 아래와 같다.

$$\begin{equation} P\left(\lim_{n \rightarrow \infty}\frac{X_1 + X_2 + \cdots + X_n}{n} = \mu \right) = 1 \end{equation}$$

큰 수의 강한 법칙에 대한 증명은 이 문서에 서술되어있다.