이 페이지는 "왜 파티클 필터가 Kalman·Grid Bayesian을 이기는가"를 끝까지 따진다. 베이즈 정리 p(x|z)∝p(z|x)p(x)가 어떻게 predict–update–resample 세 단계로 분해되는지, 파티클 집합이 왜 사후분포의 일관 추정량인지, 그리고 1,000개 파티클이 어떻게 차원의 저주를 회피하며 100만 셀 그리드의 베이지안 갱신을 흉내 내는지를 수학적으로 해부한다.
죄인의 숲 문제의 점수는 추정 정확도 — 매 턴 추정한 죄인 위치가 진짜 위치에 얼마나 가까운가 — 로 정해진다. 숲에 흩어진 수십 개 센서가 죄인 위치를 보고하지만, 각 보고는 "진짜 좌표 ± Gaussian 노이즈"다. 죄인은 매 턴 일정 패턴으로 움직이고, 새 센서 보고가 다시 들어온다. 베스트 해법의 출발점은 발상의 전환이다.
핵심 통찰은 왜 단일 점이 실패하는가다. 센서 노이즈가 섞이면 사후분포가 다중 모드(multimodal)가 된다 — 죄인이 있을 만한 봉우리가 둘 이상 생긴다. 이때 평균이나 중앙값으로 한 점을 찍으면, 그 점은 "두 봉우리 사이의 빈 골짜기" — 죄인이 절대 없는 곳 — 에 떨어진다. 점 추정의 근본적 실패다.
파티클 필터의 정당성은 한 문장으로 요약된다 — 파티클 집합은 사후분포의 몬테카를로 표현이다. 이것이 무슨 뜻이고 왜 옳은지를 단계별로 증명한다. 먼저 표현의 정의부터 고정한다.
매 턴 update 직후, 다음이 성립한다: 가중된 파티클 집합 {(x⁽ⁱ⁾, w⁽ⁱ⁾)}이 정의하는 경험분포가 현재 사후분포 p(x|z₁:ₜ)를 근사한다.
구체적으로, 임의의 함수 f에 대한 사후 기댓값을 가중 평균으로 추정한다:
E[f(x) | z] ≈ Σi w⁽ⁱ⁾ · f(x⁽ⁱ⁾), Σi w⁽ⁱ⁾ = 1.
resample 단계는 가중치를 균등하게 되돌리되, 무거운 파티클을 여러 번 복제하고 가벼운 파티클을 버려 — 점의 밀도로 가중치를 다시 인코딩한다. 표현 형식만 바뀔 뿐 근사하는 분포는 같다.
파티클을 사전분포 p(x)에서 추출하고 가중치를 우도 w⁽ⁱ⁾ ∝ p(z|x⁽ⁱ⁾)로 설정하면, 가중 경험분포는 파티클 수 N → ∞일 때 사후분포 p(x|z)로 수렴한다(대수의 법칙). 이것이 importance sampling의 일치성(consistency)이다.
우리가 알고 싶은 것은 사후 기댓값 Ep(x|z)[f(x)]이지만, 사후분포에서 직접 샘플링할 수는 없다(정규화 상수 p(z)를 모름). importance sampling은 샘플링 가능한 제안분포 q(x)에서 뽑고 비율로 보정한다:
Ep(x|z)[f] = ∫ f(x) p(x|z) dx = ∫ f(x) · [p(x|z)/q(x)] · q(x) dx.
제안분포를 사전분포 q(x) = p(x)로 택하면, 베이즈 정리 p(x|z) ∝ p(z|x)p(x)에 의해 보정 비율이 p(x|z)/p(x) ∝ p(z|x) — 곧 우도다. 따라서 사전에서 뽑은 파티클 x⁽ⁱ⁾에 가중치 w⁽ⁱ⁾ ∝ p(z|x⁽ⁱ⁾)를 주고 정규화하면, 가중 평균 Σ w⁽ⁱ⁾ f(x⁽ⁱ⁾)는 사후 기댓값의 불편(혹은 약일치) 추정량이다. 대수의 법칙으로 N→∞에서 참값에 수렴한다.
Kalman 필터와의 결정적 차이가 여기서 갈린다. Kalman은 사후분포를 하나의 가우시안(평균 + 공분산)으로 강제한다 — 정의상 봉우리가 하나뿐이다. 죄인이 있을 곳이 둘로 갈리면 Kalman은 둘 사이 빈 곳에 평균을 찍고 폭주한다.
파티클 필터는 분포에 어떤 형태도 가정하지 않는다. 봉우리가 둘이면 파티클이 두 군데에 뭉친다 — 자연스럽게. 각 군집은 독립된 가설이고, 시간이 흐르며 센서 증거가 한 가설을 지지하면 그쪽 군집의 가중치가 무거워지고, 다른 군집은 resample에서 점점 솎여 사라진다.
진짜 위치 근처 파티클의 우도 p(z|x)는 거짓 모드의 파티클보다 크다 — 센서 보고와 더 일관되기 때문이다. resample은 가중치에 비례해 파티클을 복제하므로, 매 턴 진짜 모드의 파티클 수가 증가하고 거짓 모드의 수는 감소한다.
여러 턴에 걸쳐 우도가 곱으로 누적된다 — w⁽ⁱ⁾ ∝ Πt p(zt|x⁽ⁱ⁾). 진짜 모드는 매 턴 우도 우위를 가지므로, 그 누적곱이 거짓 모드를 지수적으로 압도한다. 그래서 시간이 흐를수록 분포가 진짜 위치로 응축한다 — 문제 페이지의 "분산이 1/3로 감소", "거의 모든 파티클이 진짜 위치 ±15 안"이 이 보조정리의 관측 결과다.
파티클 필터의 한 턴은 세 단계로 분해된다. (1) predict — 모션 모델로 파티클을 이동시켜 사전분포를 만든다. (2) update — 센서 우도로 가중치를 계산한다. (3) resample — 가중치에 비례해 파티클을 다시 뽑아 사후를 균등 가중 표현으로 되돌린다. 아래는 통과 코드의 핵심부다.
struct Particle { double x, y, w; };Particle P[N]; // N = 1000// (1) Predict — 모션 모델 + 프로세스 노이즈void predict(double mvx, double mvy) { for (int i = 0; i < N; ++i) { P[i].x += mvx + gauss(0, SIGMA_MOTION); // 결정적 이동 + 노이즈 P[i].y += mvy + gauss(0, SIGMA_MOTION); }}// (2) Update — 베이지안 갱신: 우도 곱void update(Sensor s[], int ns) { double sum = 0; for (int i = 0; i < N; ++i) { double w = 1.0; for (int k = 0; k < ns; ++k) { double d = hypot(P[i].x - s[k].x, P[i].y - s[k].y); double diff = d - s[k].reading; // 예측 거리 vs 보고 w *= exp(-(diff*diff) / (2*SIGMA_SENS*SIGMA_SENS)); // 가우시안 우도 } P[i].w = w; sum += w; } if (sum < 1e-300) sum = 1; // 전 파티클 소실 방지 for (int i = 0; i < N; ++i) P[i].w /= sum; // 정규화}
update에서 센서별 우도를 곱한다(w *= ...). 센서 노이즈가 서로 독립이라는 가정 아래, 여러 센서를 동시에 관측할 우도는 p(z₁,…,z_K|x) = Π_k p(z_k|x)로 분해된다. 각 센서의 우도는 "파티클이 예측하는 센서까지 거리"와 "센서가 실제 보고한 거리"의 차이를 가우시안 pdf에 넣은 값이다. 차이가 작을수록(보고와 일관될수록) 우도가 1에 가깝다.
// (3) Resample — 중요도 재샘플링 (저분산 systematic)void resample() { double cum[N]; // 가중치 누적분포 CDF cum[0] = P[0].w; for (int i = 1; i < N; ++i) cum[i] = cum[i-1] + P[i].w; Particle nxt[N]; double step = 1.0 / N; double u = uniform(0, step); // 단일 시작 오프셋 → 저분산 int idx = 0; for (int i = 0; i < N; ++i) { while (idx < N-1 && cum[idx] < u) ++idx; // CDF 역추적 nxt[i].x = P[idx].x + gauss(0, JITTER); // 복제 + 작은 흔들기 nxt[i].y = P[idx].y + gauss(0, JITTER); nxt[i].w = 1.0 / N; // 가중치 균등 리셋 u += step; } memcpy(P, nxt, sizeof(P));}
JITTER를 더해 사본들을 미세하게 흩뜨리면, 같은 모드 안에서 다양성이 유지된다. JITTER는 모션 노이즈보다 작아야 — 너무 크면 분포가 불필요하게 퍼진다.
턴당 비용: predict는 O(N), update는 파티클 × 센서 = O(N · K)(K는 센서 수, 수십), resample은 systematic 방식이라 CDF 구축 O(N) + 단조 인덱스 진행 O(N) = O(N). 턴 전체는 O(N·K)로, N=1000·K≈30이면 ~3×10⁴. 수백 턴을 합쳐도 ~10⁷ — 즉시 끝난다.
Grid Bayesian과 대조하라: M×M 격자의 갱신은 턴당 O(M²·K)이고, M=1000이면 3×10¹⁰ — 3~4 차수 더 느리다. 파티클 필터의 O(N·K)는 공간 부피 M²가 아니라 분포 표현 표본 수 N에만 의존한다. 공간 탐색에 kd-tree를 쓰면 센서 근방 파티클 질의가 O(log N)이 되지만, 1,000 파티클 규모에서는 선형 스캔으로도 충분하다.
순진한 구현은 매 턴 무조건 resample한다. 그러나 resample은 공짜가 아니다 — 무거운 파티클을 복제하고 가벼운 것을 버리는 과정은 몬테카를로 분산을 주입한다. 분포가 이미 잘 퍼져 있어 가중치가 비교적 균등할 때 resample하면, 의미 없이 다양성만 깎는다.
표준 처방은 유효 표본 수(effective sample size)로 resample 시점을 결정하는 것이다.
Neff가 임계(N/2) 아래로 떨어졌을 때만 resample하면, (1) 가중치 퇴화(소수 파티클이 가중치 독점)를 막으면서 (2) 불필요한 resampling이 주입하는 몬테카를로 분산을 최소화한다. 매 턴 resampling과 전혀 resampling하지 않는 것 사이의 최적 절충이다.
resampling 안 함: update를 거듭하면 우도 곱이 누적되어, 진짜 위치에 가장 가까운 단 하나의 파티클이 가중치를 독점한다. Neff → 1로 퇴화 — 사실상 점 추정으로 붕괴해 다중 모드 표현 능력을 잃는다. 가중치가 0에 수렴한 999개 파티클은 계산만 잡아먹는 죽은 표본이다.
매 턴 resampling: resample은 가중치를 점 밀도로 변환하는 무작위 추출이라, 매번 추출 분산을 더한다. 가중치가 이미 균등(Neff ≈ N)할 때 resample하면 얻을 게 없이 다양성만 잃어, 표본 고갈을 가속한다.
Neff < N/2 게이트는 "퇴화가 실제로 진행됐을 때만" resample을 발동한다. 퇴화 전에는 가중치 표현을 유지해 분산 주입을 피하고, 퇴화 후에는 즉시 재표현해 죽은 표본을 살린다. 두 실패 사이의 유일한 안전 구간이다.
두 번째 심화는 우도 계산의 σsensor를 턴에 따라 줄이는 것이다. 문제 페이지의 시뮬레이션이 σ = 30 → 27 → 24 → 21 → 18로 스케줄링하는 것이 정확히 이 기법이다.
초기에는 분포가 넓게 퍼져 있어, 우도를 날카롭게(작은 σ) 잡으면 진짜 모드 근처에 파티클이 하나도 없을 때 — 모든 가중치가 0으로 소실된다(파티클 박탈, particle deprivation). 큰 σ는 우도를 완만하게 만들어 멀리 있는 파티클도 약간의 가중치를 받게 한다. 분포가 진짜 위치로 모이면 σ를 줄여 우도를 날카롭게 — 추정을 정밀하게 조인다. 일종의 어닐링이다.
sum이 언더플로하고 정규화가 깨진다. 그 턴의 분포는 완전히 무의미해진다. 방어는 두 겹이다 — (1) σ 스케줄링으로 초기 우도를 완만하게 유지, (2) predict의 모션 노이즈 σmotion를 충분히 둬 파티클이 매 턴 약간씩 퍼지게 한다. 모션 노이즈는 "예측 불확실성"을 모델링하는 동시에, 파티클 다양성을 보충하는 안전판 역할을 겸한다.
| 전략 | 다중 모드 | 턴당 비용 | 한계 |
|---|---|---|---|
| 최단거리 평균 / 중앙값 | 불가 | O(K) | 점이 두 봉우리 사이 빈 골짜기에 떨어짐 |
| Kalman Filter | 불가 | O(d³) | 가우시안 단일 모드 가정 — 다중 모드 폭주 |
| Grid Bayesian | 가능 | O(M²·K) | 공간 부피에 비례 — 큰 맵에서 메모리·시간 폭주 |
| Particle Filter | 자연 표현 | O(N·K) | 표본 고갈 — jitter·N_eff 게이트로 방어 |
표는 두 축의 경쟁을 보여준다. 세로축은 다중 모드 표현력 — 점 추정과 Kalman은 사후분포를 단일 봉우리로 강제해, 죄인의 위치가 둘로 갈리는 순간 무너진다(§2 Theorem 1·Lemma). 가로축은 계산 비용 — Grid Bayesian은 다중 모드를 표현할 수 있지만 비용이 공간 부피 M²에 비례해, 큰 맵에서 폭주한다(차원의 저주).
파티클 필터만이 두 축을 동시에 만족한다. 어떤 분포 형태도 가정하지 않아 다중 모드를 자연히 표현하고(Theorem 1), 비용이 공간 부피가 아닌 표본 수 N에만 의존해 차원의 저주를 회피한다(§2 note). 유일한 약점인 표본 고갈은 jitter와 Neff 게이트로 방어된다(§4). 1,000개 파티클이 100만 셀 그리드의 베이지안 갱신을 1/1000 비용으로 흉내 내는 — 문제 페이지가 말한 그 결론의 정당성이 여기 있다.
w를 계산한 뒤 Σw로 나누지 않으면, resample의 CDF가 1까지 누적되지 않아 인덱스 추출이 어긋난다. 가중 평균 추정도 틀어진다. 정규화는 베이즈 정리의 1/p(z) 항에 해당하는 필수 단계다.
double이 0으로 언더플로한다. 전 파티클의 우도가 0이면 정규화에서 0 나눗셈이 난다. sum < 1e-300 가드를 두거나, 우도를 로그 공간(Σ log p)에서 누적한 뒤 log-sum-exp로 정규화하라.
JITTER를 더해야 모드 안 다양성이 유지된다.
N_eff = 1/Σw²를 계산해 N_eff < N/2일 때만 resample하는 적응적 게이트를 두라.
SIGMA_SENS를 쓰면 넓게 퍼진 파티클이 모두 우도 0을 받아 박탈된다. σ를 크게 시작해(완만한 우도) 분포가 모이면 점차 줄여라. 모션 노이즈 SIGMA_MOTION도 충분히 둬 파티클 다양성을 매 턴 보충한다.
이 풀이가 "수렴한다"는 주장의 근거는 채점기 출력이다. 채점기는 매 턴 추정 위치(파티클 가중 평균 또는 MAP)와 숨겨진 진짜 위치의 거리 오차를 누적하고, 그 누적 오차를 PASS 기준과 비교한다.
main.cpp는 고정 seed로 죄인의 진짜 궤적과 노이즈 섞인 센서 보고열을 생성하고, 매 턴 step()이 반환한 추정 위치와 진짜 위치의 거리를 누적한다. g++ -O2로 main.cpp + user.cpp를 함께 컴파일해 실행하면, 턴이 진행될수록 추정 오차가 줄어들고(파티클 분포의 분산이 약 1/3로 감소) 최종 누적 오차가 PASS 기준 이하로 출력된다. N을 100·1000·5000으로 바꿔 재실행하면 Theorem 1의 일치성 — 파티클이 많을수록 추정이 참값에 수렴 — 을 직접 관찰할 수 있다.