베이즈 필터로부터 파티클 필터 유도하기
파티클 필터(Particle Filter)는 베이즈 필터의 순차 몬테카를로(sequential Monte Carlo) 구현이다. 칼만 필터와 달리 선형성이나 가우시안 가정을 요구하지 않아, 비선형 시스템과 비가우시안 분포에 적합하다. Belief를 평균과 공분산으로 표현하는 대신, 이산 샘플 또는 파티클(particle)의 집합을 이용해 분포를 근사한다. 이 글은 파티클 필터 알고리즘의 업데이트 과정을 수학적으로 유도한다.
위 인터랙티브 데모는 파티클 필터가 위치 추정(localization) 문제를 어떻게 푸는지 실시간으로 시각화한다. 화면을 클릭하여 공간 곳곳에 초록 랜드마크를 배치한 다음, 커서를 움직이거나 터치하여 로봇의 위치를 이동시킨다. 이 로봇은 파란 점선 탐지 범위 안에서 가장 가까운 랜드마크까지의 거리만을 측정할 수 있다. 주황색 파티클은 로봇이 자신의 위치에 대해 갖는 belief를 나타낸다. 로봇이 움직이고 새로운 데이터를 측정하면, 존재할 확률이 떨어지는 위치 파티클은 더 낮은 가중치를 받고 재가중(reweighting)과 재표본(resampling)을 통해 점차 제거되어, 파티클이 실제 위치로 수렴한다. 탐지 범위를 조정하여 제한된 감지가 위치 추정 수렴 속도에 어떻게 영향을 주는지 보거나, 운동 및 측정 노이즈의 분산을 수정하여 필터의 강건성을 관찰할 수 있다. 커서가 화면을 벗어나면 파티클은 자동으로 초기화된다.
가정
칼만 필터는 아래 두 가지 핵심 가정 하에서 최적의 상태 추정값을 계산한다.
- 선형 시스템 동역학과 측정 모델
- 가우시안 노이즈 분포
그러나 실제 시스템들은 이 가정들을 지키기 어렵다. 하나의 측정치에 대해 여러 상태가 가능한 다봉(multimodal) 환경에서 자기 위치를 추정하는 로봇이나, 비선형 동역학을 가진 추적 시스템을 생각해 보자. 이러한 경우 belief \(bel(x_t)\)는 단일 가우시안으로 충분히 표현될 수 없다.
파티클 필터는 유한한 가중 샘플(파티클) 집합을 이용해 belief를 표현함으로써 이 한계를 해결하며, 임의의 확률 분포를 근사할 수 있다. 파티클 필터는 아래를 만족하는 시스템에서 베이즈 필터로써 동작한다.
- 비선형성: 상태 전이 모델과 측정 모델이 비선형일 수 있다.
- 비가우시안 잡음: 프로세스 잡음 \(w_t\)와 측정 잡음 \(v_t\)는 임의의 확률 분포를 따를 수 있다.
- 비파라메트릭 표현: belief \(bel(x_t)\)는 (가우시안 같은) 함수 형태에 제한되지 않는다. 대신 \(M\)개의 가중 파티클 집합으로 표현된다.
파티클
파티클 필터의 핵심 아이디어는 belief \(bel(x_t)\)를 \(M\)개의 가중 파티클로 이루어진 이산 집합으로 표현하는 것이다.
\[\mathcal{X}_t = {(x_t^{(i)}, w_t^{(i)}) : i = 1, \ldots, M},\]여기서
- \(x_t^{(i)}\)는 \(i\)번째 파티클(시각 \(t\)에서의 상태에 대한 가설)
- \(w_t^{(i)}\)는 \(i\)번째 파티클의 중요도 가중치(importance weight)로, \(\sum_{i=1}^{M} w_t^{(i)} = 1\)을 만족한다.
belief는 다음과 같이 근사된다.
\[bel(x_t) \approx \sum_{i=1}^{M} w_t^{(i)} \delta(x_t - x_t^{(i)}).\]여기서 \(\delta(\cdot)\)는 Dirac 델타 함수다. 이 표현은 충분히 많은 파티클이 주어지면 임의의 확률 분포를 근사할 수 있다.
베이즈 필터로부터의 유도
베이즈 필터의 두 주요 단계는 아래와 같다.
- 예측
- 보정
이제 각 단계가 파티클을 이용해 어떻게 구현되는지 유도한다.
예측 단계
시각 \(t-1\)에서의 파티클 표현으로 시작하여,
\[bel(x_{t-1}) \approx \sum_{i=1}^{M} w_{t-1}^{(i)} \delta(x_{t-1} - x_{t-1}^{(i)})\]를 예측 방정식에 대입한다.
\[\begin{align} \overline{bel}(x_t) &= \int p(x_t \vert x_{t-1}, u_t) bel(x_{t-1}) dx_{t-1} \\ &\approx \int p(x_t \vert x_{t-1}, u_t) \sum_{i=1}^{M} w_{t-1}^{(i)} \delta(x_{t-1} - x_{t-1}^{(i)}) dx_{t-1} \\ &= \sum_{i=1}^{M} w_{t-1}^{(i)} \int p(x_t \vert x_{t-1}, u_t) \delta(x_{t-1} - x_{t-1}^{(i)}) dx_{t-1} \\ &= \sum_{i=1}^{M} w_{t-1}^{(i)} p(x_t \vert x_{t-1}^{(i)}, u_t). \end{align}\]핵심 포인트는 Dirac 델타 함수가 \(x_{t-1} = x_{t-1}^{(i)}\)에서의 값을 선택하여, 이전 시각의 각 파티클에 조건부인 전이 확률을 만들어낸다는 것이다.
이제 각 항 \(p(x_t \vert x_{t-1}^{(i)}, u_t)\)는 \(x_t\)에 대한 연속 확률 분포다. 원칙적으로 이 분포를 여러 샘플로 표현할 수 있다.
\[p(x_t \vert x_{t-1}^{(i)}, u_t) \approx \frac{1}{K} \sum_{k=1}^{K} \delta(x_t - x_t^{(i,k)}),\]여기서 \(x_t^{(i,k)} \sim p(x_t \vert x_{t-1}^{(i)}, u_t)\) 이다. 그러나 계산 효율성을 위해, 파티클 필터는 파티클당 하나의 샘플만 사용한다(\(K=1\)).
\[p(x_t \vert x_{t-1}^{(i)}, u_t) \approx \delta(x_t - x_t^{(i)}),\]여기서 \(x_t^{(i)} \sim p(x_t \vert x_{t-1}^{(i)}, u_t)\) 이다. 이것이 파티클 필터의 샘플링 단계다. 각 파티클 \(x_{t-1}^{(i)}\)는 운동 모델에서 샘플링하여 새 파티클 \(x_t^{(i)}\)를 생성한다. 그러면 예측된 belief는
\[\overline{bel}(x_t) \approx \sum_{i=1}^{M} w_{t-1}^{(i)} \delta(x_t - x_t^{(i)})\]이다. 이 단일 샘플 근사는 오차를 만들지만, \(M \to \infty\)일 때 전체 근사는 참 사후 분포로 수렴한다. 예측 단계 동안 가중치는 변하지 않는다. 즉, \(\bar{w}_t^{(i)} = w_{t-1}^{(i)}\).
보정 단계
보정 단계는 측정 \(z_t\)를 통합한다.
\[\begin{align} bel(x_t) &= \eta p(z_t \vert x_t)\overline{bel}(x_t) \\ &\approx \eta p(z_t \vert x_t) \sum_{i=1}^{M} \bar{w}_t^{(i)} \delta(x_t - x_t^{(i)}) \\ &= \eta \sum_{i=1}^{M} \bar{w}_t^{(i)} p(z_t \vert x_t) \delta(x_t - x_t^{(i)}) \\ &= \eta \sum_{i=1}^{M} \bar{w}_t^{(i)} p(z_t \vert x_t^{(i)}) \delta(x_t - x_t^{(i)}). \end{align}\]측정 우도 \(p(z_t \vert x_t)\)는 각 파티클 위치 \(x_t^{(i)}\)에서 평가된다. 여기서 가중치가 업데이트된다.
\[w_t^{(i)} \propto \bar{w}_t^{(i)} p(z_t \vert x_t^{(i)})\]왜냐하면
\[bel(x_t) \approx \sum_{i=1}^{M} w_t^{(i)} \delta(x_{t} - x_{t}^{(i)})\]이기 때문이다. 그리고 \(\bar{w}_t^{(i)} = w_{t-1}^{(i)}\)이므로, 다음과 같이 쓸 수 있다.
\[w_t^{(i)} \propto w_{t-1}^{(i)} p(z_t \vert x_t^{(i)}).\]가중치의 합이 1이 되도록 정규화한다.
\[w_t^{(i)} = \frac{w_{t-1}^{(i)} p(z_t \vert x_t^{(i)})}{\sum_{j=1}^{M} w_{t-1}^{(j)} p(z_t \vert x_t^{(j)})}.\]이것이 재가중(reweighting) 단계다. 실제 측정값과 더 일치하는 예측값을 생성한 파티클이 더 높은 가중치를 받는다.
가중치 붕괴 문제와 재표본
순차 중요도 샘플링(Sequential Importance Sampling)의 근본적인 문제는 가중치 붕괴(weight degeneracy)다. 여러 번 반복한 후 대부분의 파티클은 무시할 만한 가중치를 가지게 되고, 소수의 파티클만 belief 표현에 기여한다. 이는 다음 때문에 발생한다.
- 중요도 가중치의 분산이 시간에 따라 증가한다.
- 소수의 파티클이 파티클 집합을 지배한다.
붕괴 정도를 정량화하기 위해, 유효 표본 크기(effective sample size)를 계산한다.
\[N_{\text{eff}} = \frac{1}{\sum_{i=1}^{M} (w_t^{(i)})^2}.\]\(N_{\text{eff}}\)가 작으면 (보통 \(N_{\text{eff}} < M/2\)) 파티클 집합이 붕괴된 것으로 간주한다.
해법은 재표본(resampling)이다. 현재 파티클 집합에서 \(M\)개의 새 파티클을 뽑되, 파티클 \(x_t^{(i)}\)를 선택할 확률을 그 가중치 \(w_t^{(i)}\)에 비례하게 한다. 재표본 후,
- 모든 새 파티클은 균일한 가중치를 가진다. \(w_t^{(i)} = 1/M\)
- 높은 가중치를 가진 파티클은 여러 번 복제된다.
- 낮은 가중치를 가진 파티클은 폐기될 가능성이 높다.
수학적으로, 재표본은 belief 확률에서 파티클을 뽑는다.
\[\tilde{x}_t^{(i)} \sim bel(x_t)\]이는 새 파티클 집합 \(\{\tilde{x}_t^{(i)}, 1/M\}_{i=1}^{M}\)을 준다.
정리하며
모든 단계를 결합하면, 시각 \(t\)에서의 파티클 필터 알고리즘은 다음과 같다.
-
샘플링(예측): \(i = 1, \ldots, M\)에 대해
\[x_t^{(i)} \sim p(x_t \vert x_{t-1}^{(i)}, u_t)\] -
가중(보정): \(i = 1, \ldots, M\)에 대해
\[w_t^{(i)} = w_{t-1}^{(i)} \cdot p(z_t \vert x_t^{(i)})\] -
정규화: \(i = 1, \ldots, M\)에 대해
\[w_t^{(i)} = \frac{w_t^{(i)}}{\sum_{j=1}^{M} w_t^{(j)}}\] -
재표본(필요시): \(N_{\text{eff}} < N_{\text{threshold}}\)이면
- \(\{x_t^{(i)}, w_t^{(i)}\}_{i=1}^{M}\)에서 \(M\)개의 파티클 \({\tilde{x}_t^{(i)}}_{i=1}^{M}\)을 뽑는다
- 모든 \(i\)에 대해 \(x_t^{(i)} \leftarrow \tilde{x}_t^{(i)}\), \(w_t^{(i)} \leftarrow 1/M\)로 설정한다
파티클 필터는 예측, 보정, 재표본을 통해 베이즈 필터링을 구현한다. 칼만 필터와 달리, 파티클 필터는 선형성이나 가우시안 가정을 요구하지 않으며 multimodal 분포를 표현할 수 있다. 비선형성이나 비가우시안 잡음으로 인해 칼만 필터가 부적합한 위치 추정, 추적, SLAM 문제 등 로보틱스에 널리 사용된다. 그러나 파티클 수와 재표본 전략을 신중하게 조정해야 한다.