8.65 순차적 몬테카를로(SMC) 방법

1. 순차적 몬테카를로의 개요

순차적 몬테카를로(Sequential Monte Carlo, SMC)는 시간에 따라 변화하는 일련의 분포로부터 샘플링하는 몬테카를로 방법의 일반적 프레임워크이다. 입자 필터는 SMC의 한 형태이며, SMC는 그 외에도 사후 분포의 점진적 수렴, 정적 모델의 샘플링, 희소 사건 시뮬레이션 등 다양한 응용을 포함한다.

2. SMC의 일반 형식

목표 분포의 수열 $\pi_0, \pi_1, \pi_2, \ldots$ 가 주어졌을 때, SMC는 각 $\pi_t$ 로부터의 샘플을 순차적으로 생성한다. 각 단계에서 이전 단계의 샘플을 활용하여 계산 효율성을 확보한다.

2.1 일반 절차

초기화: $\pi_0$ 로부터 $N$ 개의 입자 $\{\mathbf{x}_0^{(i)}\}$ 와 초기 가중치 $\{w_0^{(i)}\}$ 생성
$t = 1, 2, \ldots$ 에 대해:
a. 이동(Move): 입자를 제안 분포를 통해 전파 $\mathbf{x}_t^{(i)} \sim K_t(\cdot \vert \mathbf{x}_{t-1}^{(i)})$
b. 가중치 갱신: 입자 가중치를 갱신하여 $\pi_t$ 로의 전이를 반영
c. 리샘플링: 필요 시 입자를 리샘플링하여 변성을 방지

3. 입자 필터로서의 SMC

베이즈 필터링 문제에서 $\pi_t(\mathbf{x}_{0:t}) = p(\mathbf{x}_{0:t} \vert \mathbf{z}_{1:t})$ 는 시간에 따라 증가하는 상태 궤적의 사후 분포이다. SMC는 이 분포의 순차적 샘플을 제공한다.

3.1 순차적 중요도 샘플링(SIS)

제안 분포 $q(\mathbf{x}_t \vert \mathbf{x}_{t-1}, \mathbf{z}_t)$ 를 통해 입자를 전파하고, 가중치를 순차적으로 갱신한다.

$w_t^{(i)} \propto w_{t-1}^{(i)}\frac{p(\mathbf{z}_t \vert \mathbf{x}_t^{(i)})p(\mathbf{x}_t^{(i)} \vert \mathbf{x}_{t-1}^{(i)})}{q(\mathbf{x}_t^{(i)} \vert \mathbf{x}_{t-1}^{(i)}, \mathbf{z}_t)}$

리샘플링을 추가하면 순차적 중요도 리샘플링(Sequential Importance Resampling, SIR)이 된다. 부트스트랩 필터는 $q = p(\mathbf{x}_t \vert \mathbf{x}_{t-1})$ 로 선택한 SIR이다.

4. 정적 SMC

시간 의존적이지 않은 정적 분포로부터 샘플링하는 SMC이다. 어려운 목표 분포 $\pi$ 로부터 직접 샘플링이 어려울 때, 중간 분포의 수열을 구성하여 점진적으로 $\pi$ 에 접근한다.

4.1 온도 담금질(Tempering)

$\pi_t(\mathbf{x}) \propto [p(\mathbf{x})]^{\beta_t}$

$\beta_t$ 가 $0$ 에서 $1$ 로 점진적으로 증가하면, $\pi_0$ 가 균일(또는 사전)에서 $\pi_T = p$ 로 전이한다. 각 단계에서 MCMC 이동과 리샘플링을 결합한다.

4.2 데이터 축적

$\pi_t(\boldsymbol{\theta}) = p(\boldsymbol{\theta} \vert \mathbf{z}_{1:t})$

베이지안 업데이트를 순차적으로 수행한다. 새 데이터가 추가될 때마다 사후 분포가 갱신되며, SMC가 이를 입자로 추적한다.

5. 증거 추정

SMC는 정규화 상수(증거)의 몬테카를로 추정을 자연스럽게 제공한다.

$\hat{Z}_t = \prod_{s=1}^{t}\left(\frac{1}{N}\sum_{i=1}^{N}\tilde{w}_s^{(i)}\right)$

여기서 $\tilde{w}_s$ 는 정규화 이전의 가중치이다. 이 성질은 베이지안 모델 비교에서 중요하다.

6. MCMC와의 결합

SMC 샘플러(SMC Sampler)는 MCMC 커널을 사용하여 입자를 이동시키는 방법이다. 각 입자가 MCMC 이동을 거치므로, 리샘플링 후 서로 다른 입자 수가 증가하여 샘플 빈곤을 완화한다.

7. 병렬화

SMC의 입자 전파와 가중치 계산은 독립적이므로 자연스럽게 병렬화가 가능하다. GPU에서 수천~수만 개의 입자를 동시에 처리할 수 있어 고차원 문제에 적합하다.

8. 로봇 공학에서의 응용

베이즈 필터링: 입자 필터로서의 SMC가 비선형 상태 추정의 표준 도구이다.

베이지안 모델 학습: 로봇 모델의 파라미터 사후 분포를 SMC로 점진적으로 학습한다.

궤적 분포 표본화: 불확실한 환경에서의 가능한 궤적의 분포를 SMC로 탐색한다.

희소 사건 확률 추정: 로봇의 드문 고장 사건이나 충돌 확률을 중요도 샘플링 기반 SMC로 효율적으로 추정한다.

9. 참고 문헌

Doucet, A., de Freitas, N., & Gordon, N. (Eds.). (2001). Sequential Monte Carlo Methods in Practice. Springer.
Del Moral, P., Doucet, A., & Jasra, A. (2006). “Sequential Monte Carlo Samplers.” Journal of the Royal Statistical Society: Series B, 68(3), 411–436.
Chopin, N., & Papaspiliopoulos, O. (2020). An Introduction to Sequential Monte Carlo. Springer.
Arulampalam, M. S., et al. (2002). “A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking.” IEEE Transactions on Signal Processing, 50(2), 174–188.

version: 1.0