입자 필터

1. 개요[편집]

분포를 수식으로 못 쓰겠으면, 그냥 점을 잔뜩 뿌려서 흉내 내면 된다.

입자 필터(particle filter)는 난수 표본의 무리로 확률분포를 근사하여, 비선형·비가우시안 계의 상태를 순차적으로 추정하는 방법이다. 순차 몬테카를로(Sequential Monte Carlo, SMC)라고도 부른다. 여기서 “입자”란 상태 공간에 뿌려진 하나하나의 표본을 말하며, 각 입자는 가중치(weight)를 달고 다닌다. 입자들의 위치와 가중치가 함께 사후분포(posterior)를 그려낸다.

칼만 필터가 “모든 것은 가우시안이고 선형이다”라는 세계관 위에서 아름답게 닫힌 해를 주는 반면, 현실의 계는 봉우리가 여러 개거나, 비틀린 비선형이거나, 잡음이 가우시안이 아니다. 입자 필터는 이 가정들을 죄다 내던지고, 몬테카를로 방법의 무식하지만 정직한 힘으로 밀어붙인다. 대가는 계산량. 하지만 분포의 모양이 아무리 이상해도 표본만 충분하면 근사할 수 있다는 것이 최대 강점이다.¹

2. 기본 아이디어: 중요도 표본추출[편집]

입자 필터의 뿌리는 중요도 표본추출(importance sampling)이다. 우리가 표본을 뽑고 싶은 진짜 분포 $p(x)$에서 직접 뽑기가 어려울 때, 뽑기 쉬운 제안분포(proposal) $q(x)$에서 뽑은 뒤 가중치 $w = p(x)/q(x)$로 보정하는 기법이다. 제안분포가 진짜 분포를 과소평가한 곳의 표본에는 큰 가중치를, 과대평가한 곳에는 작은 가중치를 줘서 균형을 맞춘다.

상태추정에서는 이걸 시간축으로 이어 붙인다. 시각 $t$에서 사후분포를 $N$개의 가중 입자로 표현한다.

$$p(\mathbf{x}_t \mid \mathbf{y}_{1:t}) \approx \sum_{i=1}^{N} w_t^{(i)} \, \delta\!\left(\mathbf{x}_t - \mathbf{x}_t^{(i)}\right)$$

여기서 $\delta$는 디랙 델타, $\mathbf{y}_{1:t}$는 지금까지의 관측 전체다. 새 관측이 들어올 때마다 각 입자의 가중치를 우도 $p(\mathbf{y}_t \mid \mathbf{x}_t^{(i)})$로 곱해 갱신한다. 관측과 잘 맞는 입자는 살이 오르고, 안 맞는 입자는 야윈다.

3. 순차 갱신과 재표본추출[편집]

기본 순환은 세 박자다.

1. 예측(propagate). 각 입자를 계의 동역학 모델(상태 전이)에 태워 다음 시각으로 밀어 보낸다. 여기에 프로세스 잡음을 얹어 입자들이 적당히 흩어지게 한다.
2. 갱신(weight). 새 관측이 오면 각 입자의 우도를 계산해 가중치를 갱신하고 정규화한다.
3. 재표본추출(resample). 가중치가 큰 입자는 여러 개로 복제하고, 작은 입자는 솎아낸다. 복제된 입자들은 이후 예측 단계의 잡음 덕에 다시 갈라진다.

재표본추출이 없으면 몇 스텝 만에 가중치 붕괴(weight degeneracy)가 일어난다. 거의 모든 가중치가 단 하나의 입자에 쏠리고, 나머지 수천 개는 계산 자원만 축내는 좀비가 되는 현상이다.² 재표본추출은 이 좀비들을 유망한 지역으로 재배치해 유효 표본 수를 되살린다. 대신 지나치게 자주 재표본추출하면 입자 다양성이 말라버리는 표본 고갈(sample impoverishment)이 생겨서, 유효 표본 수가 임계값 아래로 떨어질 때만 재표본추출하는 타협을 흔히 쓴다.

4. 가중 표본이라는 발상[편집]

입자 필터가 사후분포를 표현하는 방식의 뿌리는 결국 “가중된 난수 표본으로 분포를 그린다”는 몬테카를로 방법의 발상이다. 아래는 그 발상이 시간축 위에서 실제로 돌아가는 모습 — 1차원 SIR 입자 필터가 잡음 낀 관측만으로 숨은 상태를 추적하는 과정이다.

예측 단계에서 입자들이 퍼지고, 관측이 들어오면 우도로 가중되어 관측 근처의 입자가 살아남고, ESS가 떨어지면 재표본추출로 몰린 곳에서 입자가 복제된다 — 위 세 단계가 매 시각 반복되는 것이 입자 필터의 전부다. 표본으로 분포를 근사한다는 큰 그림은 몬테카를로 적분과 완전히 같고, 시간축과 재표본추출이라는 장치가 얹혔을 뿐이다.

5. 강점, 약점, 그리고 차원의 저주[편집]

입자 필터의 매력은 일반성이다. 상태 전이나 관측 모델이 미분 불가능하든, 잡음이 두꺼운 꼬리를 갖든, 사후분포가 봉우리 여러 개짜리든 상관없이 돌아간다. 로봇의 몬테카를로 위치추정(MCL), 표적 추적, 금융 시계열, 그리고 자료동화의 일부 응용에서 활약한다.

약점은 냉정하다. 필요한 입자 수가 상태 차원에 대해 지수적으로 늘어나는 차원의 저주에 정면으로 노출된다.³ 저차원(수~수십 차원)에서는 무적에 가깝지만, 수치기상예보처럼 상태가 수억 차원인 계에 그대로 붙이면 우주의 원자 수보다 많은 입자가 필요해진다. 그래서 고차원에서는 앙상블 칼만 필터처럼 가우시안 가정을 일부 되살린 방법에 자리를 내주고, 입자 필터는 국소화·하이브리드 형태로만 조심스레 등장한다. “이론적으로 가장 일반적인데 고차원에서 가장 먼저 죽는다”는 것이 입자 필터의 숙명적 아이러니다.

그럼에도 입자 필터는 비선형 상태추정을 배울 때 반드시 거쳐야 하는 관문이다. 칼만 필터가 우아한 특수해라면, 입자 필터는 그 우아함을 포기하는 대신 무엇이든 삼키는 일반해다.

6. 관련 문서[편집]

• 몬테카를로 방법
• 칼만 필터
• 앙상블 칼만 필터
• 자료동화
• 베이지안 최적화
• 마르코프 연쇄 몬테카를로
• 통계

7. Footnotes[편집]

1. “표본만 충분하면”이라는 조건이 문제다. 이 문장은 로또를 충분히 많이 사면 당첨된다는 말과 구조가 같다. 저차원에서는 충분히가 현실적이고, 고차원에서는 충분히가 우주의 종말까지 걸린다. ↩

2. 유효 표본 수(effective sample size, ESS)로 이 붕괴를 감시한다. $\text{ESS} = 1 / \sum_i (w^{(i)})^2$로 정의하는데, 가중치가 한 입자에 다 쏠리면 ESS가 1로 곤두박질친다. 입자가 1000개인데 ESS가 3이면, 사실상 3개짜리 필터를 1000개 값 주고 돌리는 셈이다. ↩

3. Snyder 등(2008)의 분석에 따르면, 표준 입자 필터가 붕괴를 피하려면 필요한 입자 수가 관측 차원의 분산에 지수적으로 의존한다. 수십 차원만 넘어가도 필요한 입자 수가 천문학적으로 뛰어서, “고차원 입자 필터”라는 말 자체가 한동안 형용모순 취급을 받았다. ↩