복잡한 분포에 대한 정확한 추론을 수행하는 것은 계산적으로 어렵기 때문에, 일반적으로 Monte Carlo 기반의 근사 방법이 사용된다.
그 중에서, MCMC(Markov Chain Monte Carlo)는 전체 데이터를 사용해 반복적으로 분포를 근사하는 방식이다.
그러나 데이터가 순차적으로 도착하거나, 시점별로 상태를 추적해야 하는 경우 비효율적이거나, 사실상 불가능하다.
따라서 이를 해결하기 위해 Sequential Monte Carlo (SMC) 는 이러한 문제를 해결하기 위해 제안되었으며, 여러 개의 입자(particle)를 활용하여 시계열적으로 확률 분포를 근사한다. 이는 데이터가 들어올 때마다 상태를 점직적으로 추론하며, 이전 추정값들을 기반으로 값을 효율적으로 계산할 수 있다.
- Particle: 가능한 상태 추정값 - 예를 들어, $t$시점의 particle은 $[x_t^{(1)}, x_t^{(2)}, ..., x_t^{(N)}]$이다.
Perfect Monte Carlo Sampling
$N$개의 i.i.d인 난수 샘플을 시뮬레이션할 수 있다고 가정하면, 특정 질량에 대한 확률은 위와 같이 표시할 수 있다.
이러한 이상적인 조건에서 어떠한 추정치 $I(f_t)$를 추정하고자 할 때,
로 추정할 수 있으며 이 추정량은 unbiased하며 실제로 Strong Law of Large Numbers 법칙에 의해서 실제 모수 $I(f_t)$에 almost surely convergence를 보일 수 있다.
또한 $f_t(x_{0:t})$ 분산이 유한한 경우, CLT가 성립함도 보일 수 있다.
이러한 이상적인 조건(i.i.d. 샘플링)은 대부분의 실제 문제에서 성립하지 않는다. 목표 분포에서 직접 샘플링하는 것이 불가능하거나, 정규화 상수를 알 수 없는 경우가 많기 때문이다.
일반적으로는 MCMC와 같은 대안이 사용되지만, 본 글에서는 MCMC를 다루지 않고, 시계열 기반 추론에 적합한 접근법인 Sequential Importance Sampling(SIS)을 소개하고자 한다. 이를 위해 먼저, 그 기초가 되는 Importance Sampling(IS) 기법을 간단히 설명한다.
Importance Sampling
직접적으로 실제 분포 $p$에서 샘플을 가져오기 어려운 경우 대안 분포 $\pi(x_{0:t} | y_{1: t} )$을 사용하며, $I(f_t)$는 다음과 같이 표시될 수 있다:
여기서 $w(x_{0:t})$는 importance weight라 하며, 다음과 같이 표시된다:
$N$개의 i.i.d. particle을 대안 분포 $\pi$를 통해서 생성할 수 있다면, $I(f_t)$에 대한 가능한 추정은:
유도는 다음과 같다 (타자치기가 너무 어렵다):
이후
와 같은 내용이 나오는데, 이에 대한 유도는 다음과 같다:
이렇게 알게 된 $P$의 추정을 아래의 식에 Plug-in 하면 된다.
그렇게 $I(f_t)$에 대한 추정을 importance sampling을 통해 가능하게 되는데, 다만 이러한 방법은 여전히 recursive 추정, 즉 시계열성에 대한 추론으로는 적합하지 않다. 왜냐하면 새로운 데이터 $y_{t+1}$이 등장하게 되면, Importance Weight를 얻기 위해 전체 시퀀스를 다시 계산해야 되기 때문이다. 따라서 이번에는 SIS (Sequential Importance Sampling)을 알아보도록 하자.
Sequential Importance Sampling
이전의 문제에서 언급했듯이, sequential한 상황에서의 monte-carlo는 새로운 시점 t가 주어졌을 때 이전의 trajectory에 대한 확률분포를 수정하지 않고도 이루어야만 한다. 우선 $pi(x_{0:t} | y_{1:t})$를 다음과 같이 분리할 수 있다:
이를 좀 더 일반적으로 표현할 수 있다:
이 식에 대한 유도 과정은 다음과 같다(화난다):
이렇게 두게 되니 importance weight를 recursively하게 볼 수 있도록 구조화가 된다.
해석을 해보자.
- $\tilde{w}_{t-1}^{(i)}$ : 이전 시점의 weight.
- $p(y_t \mid x_t^{(i)})$ : 우도, 현재의 확률변수가 오늘의 관측을 나타낼 확률
- $p(x_t^{(i)} \mid x_{t-1}^{(i)})$ : 전이, t-1시점의 확률변수와 t시점의 확률변수가 일치할 경우 큼
- $\pi(x_t^{(i)} \mid x_{0:t-1}^{(i)}, y_{1:t})$ : 제안된 분포
즉 모델 기준으로 더 그럴듯하게 나타난 particle은 가중치가 커지고, 제안 모델이 과하게 밀어준 방향은 분모 때문에 과도한 보정이 줄어든다.
Weight가 쉽게 Skew되는 이유는 다음과 같다고 한다:
이에 대한 해결책으로 SMC는 Bootstrap Filter을 제안한다.
The Bootstrap Filter
이전 문단에서 언급했듯이, 가중치가 특정 위치로만 쏠려 skew되는 문제점이 있다. 따라서 리샘플링을 거쳐 weight들을 초기화해주는 절차를 거친다.
핵심은 만들어진 새로운 가중치가 각 particle i에 대해서 다르지 않다는 것인데, 필자는 이를 보고 매우 이상하다 생각했다.
(약간 말하자면 우수한 학생 있는데 다 빼앗고 똑같이 돌려주는 느낌...)
우선 수학적으로도 괜찮다고 한다:
1. 기댓값(적분)이 보존됨
2. 리샘플링으로 인한 노이즈 통제 가능
다만 매번 이렇게 가중치 초기화를 하는 것은 추정에서 더 불리하게 작용할 여지가 있기 때문에(즉 언제까지나 bootstrap filter을 적용하는 것은 weight가 아예 소실되는 것을 방지하기 위한 것) ESS를 기준으로 일정 수준보다 낮으면 리샘플링을 진행한다.
알고리즘은 다음과 같다:
