8.59 몬테카를로 방법의 기본 원리

1. 몬테카를로 방법의 개요

몬테카를로(Monte Carlo, MC) 방법은 난수를 이용하여 수학적 문제를 수치적으로 해결하는 계산 기법의 총칭이다. 메트로폴리스(Metropolis)와 울람(Ulam)에 의해 1940년대 후반에 정립되었으며, 해석적 해가 불가능한 고차원 적분과 최적화 문제에 특히 유용하다.

2. 기본 원리: 몬테카를로 적분

함수 $g(\mathbf{x})$ 의 분포 $p(\mathbf{x})$ 에 대한 기댓값을 구하는 문제를 고려하라.

$I = \mathbb{E}[g(\mathbf{X})] = \int g(\mathbf{x})p(\mathbf{x}) \, d\mathbf{x}$

몬테카를로 추정: $p$ 로부터 $N$ 개의 독립 표본 $\mathbf{x}_1, \ldots, \mathbf{x}_N$ 을 추출하여 표본 평균으로 기댓값을 근사한다.

$\hat{I}_N = \frac{1}{N}\sum_{i=1}^{N}g(\mathbf{x}_i)$

3. 몬테카를로 추정의 성질

3.1 비편향성

$\mathbb{E}[\hat{I}_N] = \frac{1}{N}\sum_{i=1}^{N}\mathbb{E}[g(\mathbf{X}_i)] = I$

3.2 일관성

대수의 법칙에 의해:

$\hat{I}_N \xrightarrow{a.s.} I \quad \text{as} \quad N \to \infty$

3.3 수렴 속도

중심 극한 정리에 의해:

$\sqrt{N}(\hat{I}_N - I) \xrightarrow{d} \mathcal{N}(0, \sigma_g^2)$

여기서 $\sigma_g^2 = \text{Var}(g(\mathbf{X}))$ 이다. 표준 오차는 $\sigma_g/\sqrt{N}$ 이며, 정밀도를 2배 향상시키려면 4배의 표본이 필요하다.

3.4 차원 독립성

수렴 속도 $O(1/\sqrt{N})$ 은 적분의 차원 $d$ 에 무관하다. 이는 고차원에서 결정론적 수치 적분(격자 기반 방법의 복잡도가 $O(N^{1/d})$ 로 차원의 저주를 겪음)보다 몬테카를로가 유리한 근본적 이유이다.

4. 난수 생성

4.1 균일 난수 생성

대부분의 몬테카를로 방법은 $U(0, 1)$ 균일 난수에서 출발한다. 선형 합동 생성기(linear congruential generator), 메르센 트위스터(Mersenne Twister) 등의 의사 난수 생성기가 사용된다.

4.2 역변환 샘플링(Inverse Transform Sampling)

CDF의 역함수를 이용하여 임의의 1차원 분포에서 샘플링한다.

$U \sim U(0, 1), \quad X = F_X^{-1}(U)$

4.3 거부 샘플링(Rejection Sampling)

목표 분포 $p$ 의 상한을 제공하는 제안 분포 $q$ 를 이용한다.

$x \sim q$ 에서 샘플링
$u \sim U(0, 1)$ 에서 샘플링
$u \leq p(x)/(Mq(x))$ 이면 수락, 아니면 거부
수락된 샘플들이 $p$ 로부터의 샘플이다.

여기서 $M \geq \sup_x p(x)/q(x)$ 는 스케일링 상수이다.

4.4 중요도 샘플링(Importance Sampling)

$p$ 로부터 직접 샘플링하기 어려울 때, 다른 분포 $q$ 로부터 샘플을 추출하고 중요도 가중치로 보정한다.

$I = \int g(\mathbf{x})p(\mathbf{x})d\mathbf{x} = \int g(\mathbf{x})\frac{p(\mathbf{x})}{q(\mathbf{x})}q(\mathbf{x})d\mathbf{x} \approx \frac{1}{N}\sum_{i=1}^{N}g(\mathbf{x}_i)\frac{p(\mathbf{x}_i)}{q(\mathbf{x}_i)}$

여기서 $\mathbf{x}_i \sim q$ 이다.

4.5 MCMC(Markov Chain Monte Carlo)

고차원 복잡한 분포에서 직접 샘플링이 불가능할 때, 목표 분포를 정상 분포로 갖는 마르코프 체인을 구성하여 샘플을 생성한다. 메트로폴리스-헤이스팅스(Metropolis-Hastings), 깁스 샘플링(Gibbs sampling), 해밀토니안 몬테카를로(HMC) 등이 대표적이다.

5. 분산 감소 기법

5.1 반대 변수(Antithetic Variates)

음의 상관을 갖는 샘플 쌍을 사용하여 분산을 줄인다.

5.2 제어 변수(Control Variates)

알려진 기댓값을 갖는 보조 변수 $h$ 를 이용한다.

$\hat{I}_N^{CV} = \frac{1}{N}\sum_i[g(\mathbf{x}_i) - c(h(\mathbf{x}_i) - \mathbb{E}[h])]$

5.3 층화 샘플링(Stratified Sampling)

입력 공간을 층으로 분할하여 각 층에서 별도로 샘플링한다.

6. 로봇 공학에서의 몬테카를로 응용

입자 필터: 비선형/비가우시안 상태 추정에서 사후 분포를 가중 샘플로 근사한다.

몬테카를로 위치 추정: 확률 격자 기반 위치 추정의 확장으로, 로봇 위치의 분포를 입자로 표현한다.

궤적 샘플링: 경로 계획에서 다수의 궤적 샘플을 생성하여 비용을 평가하고 최적을 선택한다.

확률적 충돌 검사: 불확실한 환경에서의 충돌 확률을 몬테카를로 시뮬레이션으로 추정한다.

7. 참고 문헌

Robert, C. P., & Casella, G. (2004). Monte Carlo Statistical Methods (2nd ed.). Springer.
Metropolis, N., & Ulam, S. (1949). “The Monte Carlo Method.” Journal of the American Statistical Association, 44(247), 335–341.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.

version: 1.0