칼만 필터는 모든 것이 가우시안일 때만 깔끔한 공식을 준다. 현실은 그렇지 않다 — 상태가 여러 봉우리로 갈라지고, 관측 모델이 비선형이며, 잡음이 정규분포가 아니다. 파티클 필터는 사후분포를 수식 대신 가중치 붙은 표본 집합으로 표현한다. 매 시각 표본을 한 발 전진시키고, 관측이 얼마나 그럴듯한지로 가중치를 매기고, 무거운 표본을 복제하며 가벼운 표본을 버린다. 이 페이지는 그 세 단계가 베이즈 정리의 어디서 오는지 유도하고, 죄인의 숲에서 위치를 추정하는 데 어떻게 쓰이는지 추적한다.
숨겨진 상태 x_t가 시간에 따라 변하고(상태 전이 모델 p(x_t | x_{t−1})), 우리는 그것을 직접 보지 못한 채 잡음 섞인 관측 z_t만 받는다(관측 모델 p(z_t | x_t)). 목표는 지금까지의 모든 관측 z_{1:t}이 주어졌을 때 현재 상태의 사후분포 p(x_t | z_{1:t})를 추정하는 것이다.
이것은 순차(sequential) 추정이다 — 관측이 한 번에 다 오는 게 아니라 한 시각씩 흘러들어오고, 우리는 매 시각 추정을 갱신해야 한다. 로봇의 자기 위치 추정(localization), 레이더 표적 추적, 추격 대상의 위치 예측이 모두 이 틀에 들어간다.
상태 전이와 관측이 모두 선형이고 모든 잡음이 가우시안이면, 사후분포는 항상 가우시안으로 유지되고 평균·공분산만 갱신하면 된다 — 그것이 칼만 필터(Kalman filter)다. 하지만 Expert의 추정 문제는 거의 항상 이 가정을 깬다. 숲에서 추격 대상이 갈림길을 만나면 사후분포가 여러 봉우리(multimodal)로 갈라진다 — "왼쪽 길로 갔거나, 오른쪽 길로 갔다." 단봉 가우시안 하나로는 이런 분포를 절대 표현할 수 없다. 관측 모델도 "장애물에 가리면 안 보임" 같은 비선형·불연속 규칙이다.
파티클 필터(Particle Filter, PF; 순차 몬테카를로 Sequential Monte Carlo라고도 한다)의 발상은 분포를 함수가 아니라 표본으로 표현하는 것이다. 사후분포 p(x_t | z_{1:t})를 N개의 입자(particle) {x_t^{(i)}}와 각 입자의 가중치 {w_t^{(i)}}로 근사한다:
입자가 빽빽이 모인 영역은 사후 확률이 높은 영역, 입자가 드문 영역은 낮은 영역이다. 봉우리가 둘이면 입자 구름도 두 무리로 갈라진다 — 멀티모달이 공짜로 표현된다. 추정값이 필요하면 가중 평균 Σ w^{(i)} x^{(i)} (MMSE 추정)이나 가장 무거운 입자(MAP 근사)를 쓴다.
알고리즘은 매 시각 세 단계를 돈다. predict — 모든 입자를 전이 모델로 한 발 전진시킨다(분포가 퍼진다). update — 새 관측이 각 입자를 얼마나 잘 설명하는지로 가중치를 매긴다(분포가 좁아진다). resample — 무거운 입자를 복제하고 가벼운 입자를 버려, 모든 입자가 다시 동등한 가중치를 갖게 한다(낭비되는 입자를 회수한다).
파티클 필터는 임의로 발명된 절차가 아니다. predict와 update는 정확한 베이즈 재귀(Bayes recursion)를 그대로 옮긴 것이고, 표본 표현과 resample은 그 재귀를 유한 계산으로 만들기 위한 몬테카를로 근사다. 정당성을 네 조각으로 잇는다.
마르코프 가정(x_t는 x_{t−1}에만 의존)과 관측 독립 가정(z_t는 x_t에만 의존) 아래에서, 사후분포는 두 단계 재귀를 만족한다:
예측: p(x_t|z_{1:t-1}) = ∫ p(x_t|x_{t-1}) p(x_{t-1}|z_{1:t-1}) dx_{t-1}
갱신: p(x_t|z_{1:t}) = p(z_t|x_t) p(x_t|z_{1:t-1}) / p(z_t|z_{1:t-1})
증명. 예측 단계는 전확률의 법칙(law of total probability)에 마르코프 가정을 결합한 것 — x_{t−1}에 대해 적분하며 p(x_t|x_{t−1},z_{1:t−1}) = p(x_t|x_{t−1})로 단순화한다. 갱신 단계는 z_t에 대한 베이즈 정리다: p(x_t|z_{1:t}) = p(x_t|z_t, z_{1:t−1}) ∝ p(z_t|x_t,z_{1:t−1})·p(x_t|z_{1:t−1}), 여기에 관측 독립 가정으로 p(z_t|x_t,z_{1:t−1}) = p(z_t|x_t). 분모 p(z_t|z_{1:t−1})는 x_t와 무관한 정규화 상수다.
목표 분포 π(x)에서 직접 표본을 뽑을 수 없어도, 표본을 뽑기 쉬운 제안 분포(proposal) q(x)에서 x^{(i)} ∼ q를 뽑고 가중치 w^{(i)} ∝ π(x^{(i)}) / q(x^{(i)})를 주면, π에 대한 임의의 기댓값을 추정할 수 있다.
검증. E_π[f] = ∫ f(x)π(x)dx = ∫ f(x)·(π(x)/q(x))·q(x)dx = E_q[f(x)·w(x)]. 따라서 q에서 뽑은 표본의 가중 평균 Σ w^{(i)}f(x^{(i)}) / Σ w^{(i)}은 E_π[f]의 일치추정량(consistent estimator)이다.
제안 분포로 전이 모델 q = p(x_t|x_{t−1})를 택하면(가장 흔한 선택, "bootstrap filter"), 가중치 갱신 공식이 극적으로 단순해진다:
w_t^{(i)} ∝ w_{t-1}^{(i)} · p(z_t | x_t^{(i)})
증명. 일반 순차 중요도 샘플링의 가중치 재귀는 w_t ∝ w_{t−1}·[p(z_t|x_t)·p(x_t|x_{t−1})] / q(x_t|x_{t−1},z_t)이다. 제안을 q = p(x_t|x_{t−1})로 잡으면 분자의 전이항과 분모가 정확히 상쇄되어 우도 p(z_t|x_t)만 남는다. 그래서 알고리즘이 두 줄이 된다 — predict는 "전이 모델에서 표본을 뽑는다"(제안 분포 샘플링), update는 "가중치에 우도를 곱한다." Theorem 1의 베이즈 재귀가 표본 위에서 이 모습으로 실현된다.
resampling 없이 순차 중요도 샘플링만 반복하면, 가중치 분산은 시간에 따라 단조 증가한다. 몇 스텝 후 거의 모든 가중치가 한 입자에 몰리고 나머지는 0에 수렴한다 — 가중치 퇴화(weight degeneracy). 그러면 N개 입자가 사실상 1개 입자만큼의 정보만 들고 있게 된다.
처방. 유효 표본 수(effective sample size)를 N_eff = 1 / Σ (w^{(i)})²로 정의한다. 모든 가중치가 같으면 N_eff = N, 하나에 다 몰리면 N_eff = 1. N_eff가 임계값(보통 N/2) 아래로 떨어지면 resample한다 — 가중치에 비례하는 확률로 N개를 복원추출(with replacement)하여 새 입자 집합을 만들고 모든 가중치를 1/N로 초기화한다. 무거운 입자는 여러 번 뽑혀 복제되고, 가벼운 입자는 사라진다. resampling은 표본을 사후 확률이 높은 영역으로 재배치해 계산 자원의 낭비를 막는다.
bootstrap 필터는 predict / update / resample 세 함수와 한 스텝 루프로 구성된다. resample은 단순한 다항(multinomial) 복원추출도 되지만, 분산이 더 작은 systematic resampling을 표준으로 쓴다 — 누적분포를 등간격으로 한 번만 훑어 O(N)에 끝나고, 난수를 단 하나만 소비한다. 아래는 2D 위치 추정을 가정한 완전한 구현이다.
#include <vector>#include <random>#include <cmath>using namespace std;struct Particle { double x, y, w; }; // 상태(x,y) + 가중치 wstruct ParticleFilter { vector<Particle> p; mt19937 rng{2024}; ParticleFilter(int N, double x0, double y0) : p(N) { // 초기 사전분포: (x0,y0) 주변에 균등 가중치로 흩뿌림 normal_distribution<double> init(0.0, 5.0); for (auto& q : p) q = { x0 + init(rng), y0 + init(rng), 1.0 / N }; } // (1) PREDICT — 전이 모델로 입자를 한 발 전진(제안 분포 샘플링) void predict(double dx, double dy, double procStd) { normal_distribution<double> noise(0.0, procStd); for (auto& q : p) { q.x += dx + noise(rng); // 제어입력 + 프로세스 잡음 q.y += dy + noise(rng); } } // (2) UPDATE — 관측 우도를 가중치에 곱하고 정규화 void update(double zx, double zy, double measStd) { double sum = 0.0; for (auto& q : p) { double d2 = (q.x-zx)*(q.x-zx) + (q.y-zy)*(q.y-zy); q.w *= exp(-d2 / (2*measStd*measStd)); // 가우시안 우도 sum += q.w; } for (auto& q : p) q.w /= sum; // Σw = 1 로 정규화 } // 유효 표본 수 — degeneracy 게이트 double nEff() const { double s = 0.0; for (auto& q : p) s += q.w * q.w; return 1.0 / s; } // (3) RESAMPLE — systematic: CDF 를 등간격으로 한 번 훑음 void resample() { int N = p.size(); vector<Particle> next; next.reserve(N); uniform_real_distribution<double> u(0.0, 1.0 / N); double r = u(rng); // 난수 단 하나만 소비 double c = p[0].w; int i = 0; for (int j = 0; j < N; ++j) { double thresh = r + j * (1.0 / N); while (thresh > c && i < N - 1) c += p[++i].w; next.push_back({ p[i].x, p[i].y, 1.0 / N }); } p = move(next); // 모든 가중치를 1/N 로 리셋 } // 한 스텝 = predict -> update -> (필요시) resample void step(double dx, double dy, double zx, double zy) { predict(dx, dy, 1.0); update(zx, zy, 2.0); if (nEff() < p.size() / 2.0) resample(); } // 상태 추정 — 가중 평균(MMSE) void estimate(double& ex, double& ey) const { ex = ey = 0.0; for (auto& q : p) { ex += q.w * q.x; ey += q.w * q.y; } }};
update의 가우시안 우도(라인 31~32)는 Theorem 2의 p(z_t|x_t^{(i)}) 곱셈 — 관측 모델이 비선형이거나 비가우시안이면 이 두 줄만 갈아끼우면 된다. resample의 systematic 방식(라인 44, 47)이 핵심 디테일이다. 다항 복원추출은 N개의 독립 난수를 뽑지만, systematic은 난수 하나 r ∈ [0, 1/N)로 등간격 격자 {r, r+1/N, …}를 만들어 누적분포(CDF)를 단 한 번 선형 스캔한다. 분산이 더 작고 정렬·이진탐색이 필요 없어 O(N)이다. 라인 60의 nEff() < N/2 게이트(Theorem 3)가 매 스텝 resample하지 않는 이유 — 불필요한 resampling은 입자 고갈만 가속한다.
한 스텝당 predict O(N), update O(N), systematic resample O(N). 전체 T 스텝이면 O(NT)로 입력에 선형이다. 공간은 입자 배열 O(N)(resample이 임시 배열을 쓰면 2N). 추정 오차는 중심극한정리에 따라 O(1/√N)로 줄어든다 — 정확도를 두 배로 올리려면 입자를 네 배로 늘려야 한다. 정확도와 시간의 트레이드오프를 쥔 단 하나의 다이얼이 N이며, 적정값은 상태 공간 차원과 사후분포의 봉우리 수에 달려 있다.
파티클 필터가 Expert에서 등장하는 신호는 "숨겨진 상태 + 잡음 섞인 순차 관측 + 비선형/멀티모달"의 삼박자다. 문제별 차이는 전이 모델·관측 모델·상태 표현의 설계로 흡수된다.
죄인의 숲은 추격 대상이 숲의 어느 위치에 있는지를, 시간차를 두고 들어오는 단서들로 추정하는 문제다. 여기서 PF가 비트는 지점은 셋이다.
핵심은 "관측 규칙을 우도 함수 p(z_t|x_t)로 번역할 수 있는가"이며, 번역만 되면 §2의 베이즈 재귀가 그대로 보장을 준다. 다익스트라에서 "비용 규칙을 비음 간선 가중치로 번역"하던 것과 같은 발상이다 — 문제 고유의 규칙을 표준 알고리즘이 먹는 형태로 옮기는 것.
| 알고리즘 | 스텝당 시간 | 비선형 / 멀티모달 | 쓰임 |
|---|---|---|---|
| Kalman Filter | O(d³) | 선형·단봉만 | 선형 가우시안 — 최적이고 가장 빠름 |
| Extended KF | O(d³) | 약한 비선형 / 단봉 | 야코비안 선형화로 비선형 근사 |
| Unscented KF | O(d³) | 중간 비선형 / 단봉 | 시그마 포인트 — 미분 불필요 |
| Particle Filter | O(Nd) | 임의 비선형·멀티모달 | 강한 비선형·다봉 — 저차원에서 강력 |
| Histogram Filter | O(격자 크기) | 임의 / 멀티모달 | 이산·저차원 격자 — 작은 상태공간 |
이 표는 하나의 트레이드오프 곡선이다 — 위로 갈수록 빠르고 제약이 강하며, 아래로 갈수록 일반적이고 비싸다. 칼만 필터는 선형·가우시안 세계에서 증명된 최적 추정량이고 d차원에서 O(d³)로 끝난다 — 가정이 맞으면 PF를 쓸 이유가 없다. EKF/UKF는 비선형성을 각각 1차 테일러 전개와 시그마 포인트로 근사해 단봉 가우시안 틀 안에 머문다.
PF는 분포 모양에 대한 가정을 완전히 버리는 대신, 입자 수 N이 차원에 지수적으로 필요해진다. 그래서 실무 선택 기준은 명확하다 — 상태가 저차원이고(대략 5차원 이하) 사후분포가 다봉이거나 관측 모델이 강하게 비선형이면 PF, 그렇지 않으면 칼만 계열. 죄인의 숲처럼 분포가 갈림길에서 갈라지는 문제는 PF의 정확히 그 영역이다. 히스토그램 필터는 상태 공간을 격자로 이산화해 셀마다 확률을 들고 가는 방식으로, 상태 공간이 충분히 작으면 PF보다 구현이 단순하고 입자 고갈 문제가 없다 — 사실 PF는 "고정 격자 대신 적응적으로 움직이는 격자(입자)를 쓰는 히스토그램 필터"라고 볼 수 있다.