8.60 중요도 샘플링의 원리와 구현

1. 중요도 샘플링의 동기

목표 분포 $p(\mathbf{x})$ 로부터 기댓값을 추정하는 몬테카를로 방법에서, $p$ 로부터 직접 샘플링이 어려운 경우가 많다. 중요도 샘플링(Importance Sampling, IS)은 샘플링이 용이한 제안 분포(proposal distribution) $q(\mathbf{x})$ 로부터 샘플을 추출하고, 중요도 가중치(importance weight)로 보정하여 $p$ 에 대한 기댓값을 추정한다.

2. 기본 공식

목표 기댓값 $I = \mathbb{E}_p[g(\mathbf{X})] = \int g(\mathbf{x})p(\mathbf{x})d\mathbf{x}$ 에 대해, $q$ 로부터 샘플링하도록 변형한다.

$I = \int g(\mathbf{x})\frac{p(\mathbf{x})}{q(\mathbf{x})}q(\mathbf{x})d\mathbf{x} = \mathbb{E}_q\left[g(\mathbf{X})\frac{p(\mathbf{X})}{q(\mathbf{X})}\right]$

$q$ 로부터 $N$ 개의 독립 표본 $\mathbf{x}_1, \ldots, \mathbf{x}_N$ 을 추출하여 기댓값을 추정한다.

$\hat{I}_{IS} = \frac{1}{N}\sum_{i=1}^{N}g(\mathbf{x}_i)w(\mathbf{x}_i), \quad w(\mathbf{x}) = \frac{p(\mathbf{x})}{q(\mathbf{x})}$

$w(\mathbf{x})$ 를 중요도 가중치라 한다.

3. 정규화된 중요도 샘플링

$p$ 와 $q$ 중 하나 또는 둘 다 정규화 상수를 모르는 경우, 정규화된(self-normalized) 중요도 샘플링을 사용한다.

$\hat{I}_{NIS} = \frac{\sum_{i=1}^{N}g(\mathbf{x}_i)\tilde{w}(\mathbf{x}_i)}{\sum_{i=1}^{N}\tilde{w}(\mathbf{x}_i)}$

여기서 $\tilde{w}(\mathbf{x}_i) \propto p(\mathbf{x}_i)/q(\mathbf{x}_i)$ 이다. 분모의 정규화 인자가 정규화 상수의 몬테카를로 추정이다.

정규화된 IS는 편향 추정량이지만(일관적임), 정규화 상수가 알려지지 않은 사후 분포에서의 기댓값 추정에 유용하다.

4. 유효 표본 수(Effective Sample Size)

중요도 샘플링의 효율성을 측정하는 지표이다.

$N_{eff} = \frac{(\sum_i w_i)^2}{\sum_i w_i^2}$

$1 \leq N_{eff} \leq N$ 이며, 가중치가 모두 같으면 $N_{eff} = N$ , 한 가중치가 지배적이면 $N_{eff} \to 1$ 이다. $N_{eff}$ 가 작으면 중요도 샘플링의 분산이 크다(소수의 샘플이 전체 추정에 지배적).

5. 제안 분포의 선택

5.1 최적 제안 분포

분산을 최소화하는 이상적 제안 분포는 다음과 같다.

$q^*(\mathbf{x}) \propto \lvert g(\mathbf{x})\rvert p(\mathbf{x})$

이 경우 분산이 영이지만, $q^*$ 자체를 알기 어려우므로 실용적이지 않다.

5.2 실용적 지침

$q$ 는 $p$ 와 유사해야 한다: 가중치의 변동을 줄이기 위함.
$q$ 의 꼬리는 $p$ 보다 두꺼워야 한다: $q(\mathbf{x}) = 0$ 이고 $p(\mathbf{x}) \neq 0$ 이면 가중치가 무한대가 되어 추정이 발산한다.
$q$ 로부터의 샘플링이 효율적이어야 한다.

6. 중요도 가중치의 분산과 변성(Degeneracy)

$p$ 와 $q$ 가 크게 다르면 소수의 샘플이 매우 큰 가중치를 가져 추정의 분산이 증가한다. 극단적으로 한 샘플이 전체 가중치를 차지하는 상태를 가중치 변성(weight degeneracy)이라 한다. 이는 중요도 샘플링의 주요 한계이다.

7. 순차적 중요도 샘플링

시간에 따라 분포가 변하는 문제에서, 샘플을 재활용하면서 가중치를 순차적으로 갱신한다.

$w_t = w_{t-1}\cdot\frac{p(\mathbf{x}_t \vert \text{새 관측})}{q(\mathbf{x}_t \vert \text{이전})}$

이는 입자 필터(particle filter)의 핵심이다.

8. 로봇 공학에서의 응용

8.1 입자 필터

입자 필터는 순차적 중요도 샘플링의 적용이다. 각 시각에서 입자(샘플)를 제안 분포로부터 생성하고, 관측 가능도에 의한 가중치를 곱한다. 주기적인 리샘플링이 가중치 변성을 완화한다.

8.2 희소 사건 시뮬레이션

로봇의 드문 고장 사건이나 안전 위반의 확률을 평가할 때, 표준 몬테카를로는 효율이 낮다(거의 모든 샘플이 정상). 중요도 샘플링으로 고장 영역에 집중된 제안 분포를 사용하여 희소 사건의 확률을 효율적으로 추정한다.

8.3 베이지안 추론에서의 증거 계산

사후 분포의 정규화 상수(증거) $p(\mathbf{z}) = \int p(\mathbf{z} \vert \boldsymbol{\theta})p(\boldsymbol{\theta})d\boldsymbol{\theta}$ 를 중요도 샘플링으로 추정한다. 모델 선택과 베이즈 인자 계산에 사용된다.

9. 참고 문헌

Robert, C. P., & Casella, G. (2004). Monte Carlo Statistical Methods (2nd ed.). Springer.
Doucet, A., de Freitas, N., & Gordon, N. (Eds.). (2001). Sequential Monte Carlo Methods in Practice. Springer.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
Owen, A. B. (2013). Monte Carlo Theory, Methods and Examples. https://artowen.su.domains/mc/.

version: 1.0