6.142 정보 필터와 정보 행렬 표현

1. 정보 형태의 동기

칼만 필터는 상태의 평균과 공분산을 전파하는 모멘트(moment) 형태의 필터이다. 정보 필터(information filter)는 칼만 필터와 수학적으로 동치이지만, 공분산 행렬의 역행렬인 정보 행렬(information matrix)과 정보 벡터(information vector)를 직접 전파한다. 이 표현은 다중 센서 융합, 분산 추정, 대규모 SLAM 문제에서 특유의 장점을 가진다.

2. 정보 행렬과 정보 벡터의 정의

가우시안 분포 \mathcal{N}(\boldsymbol{\mu}, \mathbf{P})의 정보 형태 파라미터는 다음과 같이 정의한다.

\boldsymbol{\Omega} = \mathbf{P}^{-1} \quad \text{(정보 행렬, information matrix)}

\boldsymbol{\xi} = \mathbf{P}^{-1} \boldsymbol{\mu} = \boldsymbol{\Omega} \boldsymbol{\mu} \quad \text{(정보 벡터, information vector)}

역으로, 모멘트 형태로의 변환은 다음과 같다.

\mathbf{P} = \boldsymbol{\Omega}^{-1}, \quad \boldsymbol{\mu} = \boldsymbol{\Omega}^{-1} \boldsymbol{\xi}

가우시안 분포의 확률 밀도 함수를 정보 형태로 표현하면 다음과 같다.

p(\mathbf{x}) \propto \exp\left(-\frac{1}{2}\mathbf{x}^T \boldsymbol{\Omega} \mathbf{x} + \boldsymbol{\xi}^T \mathbf{x}\right)

이 표현에서 \boldsymbol{\Omega}는 로그 확률의 이차 항의 계수이고, \boldsymbol{\xi}는 일차 항의 계수이다.

3. 정보 필터 알고리즘

3.1 갱신 단계

정보 필터의 가장 큰 장점은 갱신 단계가 단순한 덧셈으로 표현된다는 것이다.

\boldsymbol{\Omega}_{k\vert k} = \boldsymbol{\Omega}_{k\vert k-1} + \mathbf{H}_k^T \mathbf{R}_k^{-1} \mathbf{H}_k

\boldsymbol{\xi}_{k\vert k} = \boldsymbol{\xi}_{k\vert k-1} + \mathbf{H}_k^T \mathbf{R}_k^{-1} \mathbf{z}_k

이 결과의 유도는 다음과 같다. 칼만 필터의 공분산 갱신 공식에 행렬 역전보조정리(matrix inversion lemma, 또는 Woodbury 항등식)를 적용한다.

(\mathbf{P}_{k\vert k-1} - \mathbf{P}_{k\vert k-1}\mathbf{H}_k^T (\mathbf{H}_k \mathbf{P}_{k\vert k-1} \mathbf{H}_k^T + \mathbf{R}_k)^{-1} \mathbf{H}_k \mathbf{P}_{k\vert k-1})^{-1}

= \mathbf{P}_{k\vert k-1}^{-1} + \mathbf{H}_k^T \mathbf{R}_k^{-1} \mathbf{H}_k

따라서

\boldsymbol{\Omega}_{k\vert k} = \boldsymbol{\Omega}_{k\vert k-1} + \mathbf{H}_k^T \mathbf{R}_k^{-1} \mathbf{H}_k

각 센서의 기여분 \mathbf{H}_k^T \mathbf{R}_k^{-1} \mathbf{H}_k는 양의 반정치 행렬이므로, 관측을 추가할수록 정보 행렬이 단조 증가한다. 이는 \boldsymbol{\Omega}_{k\vert k} \succeq \boldsymbol{\Omega}_{k\vert k-1}로 표현되며, 관측이 불확실성을 줄인다는 직관과 일치한다.

3.2 다중 센서 갱신

p개의 독립적인 센서로부터 관측 \mathbf{z}_k^{(1)}, \dots, \mathbf{z}_k^{(p)}를 받으면, 정보 형태에서는 각 센서의 기여분을 단순히 합산한다.

\boldsymbol{\Omega}_{k\vert k} = \boldsymbol{\Omega}_{k\vert k-1} + \sum_{j=1}^{p} (\mathbf{H}_k^{(j)})^T (\mathbf{R}_k^{(j)})^{-1} \mathbf{H}_k^{(j)}

\boldsymbol{\xi}_{k\vert k} = \boldsymbol{\xi}_{k\vert k-1} + \sum_{j=1}^{p} (\mathbf{H}_k^{(j)})^T (\mathbf{R}_k^{(j)})^{-1} \mathbf{z}_k^{(j)}

이 합산은 통신 순서에 무관하고 병렬화가 용이하므로, 분산 시스템에 적합하다.

3.3 예측 단계

정보 필터의 예측 단계는 칼만 필터와 달리 복잡하다.

\boldsymbol{\Omega}_{k+1\vert k} = (\mathbf{F}_k \boldsymbol{\Omega}_{k\vert k}^{-1} \mathbf{F}_k^T + \mathbf{Q}_k)^{-1}

\boldsymbol{\xi}_{k+1\vert k} = \boldsymbol{\Omega}_{k+1\vert k} \mathbf{F}_k \boldsymbol{\Omega}_{k\vert k}^{-1} \boldsymbol{\xi}_{k\vert k}

이 연산은 \boldsymbol{\Omega}_{k\vert k}의 역행렬 계산을 필요로 하므로 O(n^3)의 복잡도를 가진다. 행렬 역전보조정리를 적용하면 역행렬 계산을 회피할 수 있다.

\boldsymbol{\Omega}_{k+1\vert k} = \mathbf{Q}_k^{-1} - \mathbf{Q}_k^{-1}\mathbf{F}_k(\boldsymbol{\Omega}_{k\vert k} + \mathbf{F}_k^T \mathbf{Q}_k^{-1}\mathbf{F}_k)^{-1}\mathbf{F}_k^T \mathbf{Q}_k^{-1}

이 형태에서는 \mathbf{Q}_k^{-1}이 필요하므로, \mathbf{Q}_k가 특이하면 적용할 수 없다.

4. 칼만 필터와 정보 필터의 비교

5. 정보 행렬의 희소 구조

5.1 SLAM에서의 희소 정보 행렬

EKF 기반 SLAM에서 상태 벡터는 로봇 자세와 모든 랜드마크의 위치를 포함한다.

\mathbf{x} = [\mathbf{x}_r^T, \mathbf{l}_1^T, \mathbf{l}_2^T, \dots, \mathbf{l}_M^T]^T

공분산 행렬 \mathbf{P}는 일반적으로 밀집(dense) 행렬이다. 이는 로봇을 매개로 모든 랜드마크 쌍 사이에 간접적 상관이 존재하기 때문이다. 그러나 정보 행렬 \boldsymbol{\Omega} = \mathbf{P}^{-1}은 자연스럽게 희소 구조를 가진다.

정보 행렬의 (i,j) 블록이 비영(nonzero)인 것은 변수 i와 j 사이에 직접적 관측 관계가 존재함을 의미한다. 로봇이 랜드마크 i를 관측할 때, 정보 행렬의 (\text{robot}, i) 블록에만 정보가 추가되므로, 직접 관측하지 않는 랜드마크 쌍 사이의 블록은 영(zero)이다.

\boldsymbol{\Omega} = \begin{bmatrix} \boldsymbol{\Omega}_{rr} & \boldsymbol{\Omega}_{r1} & \boldsymbol{\Omega}_{r2} & \cdots & \boldsymbol{\Omega}_{rM} \\ \boldsymbol{\Omega}_{1r} & \boldsymbol{\Omega}_{11} & \mathbf{0} & \cdots & \mathbf{0} \\ \boldsymbol{\Omega}_{2r} & \mathbf{0} & \boldsymbol{\Omega}_{22} & \cdots & \mathbf{0} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \boldsymbol{\Omega}_{Mr} & \mathbf{0} & \mathbf{0} & \cdots & \boldsymbol{\Omega}_{MM} \end{bmatrix}

이 별 형태(star topology)의 희소 구조는 로봇이 각 랜드마크를 독립적으로 관측하는 상황을 반영한다. 랜드마크 i와 j를 동시에 관측하면 \boldsymbol{\Omega}_{ij} 블록이 비영이 된다.

5.2 그래프 구조와의 관계

정보 행렬의 희소 구조는 마르코프 랜덤 필드(Markov Random Field, MRF)의 그래프 구조와 직접 대응한다. \boldsymbol{\Omega}_{ij} \neq \mathbf{0}이면 변수 i와 j 사이에 간선(edge)이 존재한다. 이는 조건부 독립성을 나타낸다: \boldsymbol{\Omega}_{ij} = \mathbf{0}이면 다른 모든 변수가 주어진 조건 하에서 \mathbf{x}_i와 \mathbf{x}_j는 조건부 독립이다.

6. 희소 확장 정보 필터(Sparse Extended Information Filter, SEIF)

대규모 SLAM에서 정보 행렬의 희소성을 적극 활용하는 필터가 SEIF이다. 정보 행렬의 희소 구조를 유지하기 위하여, 활성 랜드마크(active landmark)의 수를 제한하고 비활성 랜드마크와 로봇 사이의 정보 연결을 근사적으로 제거(sparsification)한다.

희소화의 핵심 연산은 다음과 같다. 로봇 변수 \mathbf{x}_r을 소거(marginalize out)하면

\boldsymbol{\Omega}_{\text{landmarks}} = \boldsymbol{\Omega}_{ll} - \boldsymbol{\Omega}_{lr} \boldsymbol{\Omega}_{rr}^{-1} \boldsymbol{\Omega}_{rl}

이 슈어 보수(Schur complement) 연산에 의하여, 원래 희소했던 \boldsymbol{\Omega}_{ll}에 채움(fill-in)이 발생한다. 이 채움은 로봇이 매개하는 간접 관계가 직접 관계로 변환되기 때문이다.

7. 정보 형태의 수치적 고려 사항

7.1 상태 복원

정보 형태에서 상태 추정값을 직접 얻으려면 \boldsymbol{\mu} = \boldsymbol{\Omega}^{-1}\boldsymbol{\xi}를 계산해야 한다. 이는 선형 시스템 \boldsymbol{\Omega}\boldsymbol{\mu} = \boldsymbol{\xi}를 푸는 것과 동치이다. \boldsymbol{\Omega}가 희소하면 희소 촐레스키 분해를 이용하여 효율적으로 풀 수 있다.

7.2 조건수

공분산 행렬 \mathbf{P}의 조건수와 정보 행렬 \boldsymbol{\Omega}의 조건수는 동일하다.

\kappa(\boldsymbol{\Omega}) = \kappa(\mathbf{P}^{-1}) = \kappa(\mathbf{P})

따라서 정보 형태로의 변환이 수치적 조건을 개선하지는 않는다. 그러나 정보 행렬의 희소 구조를 활용할 수 있다는 것이 주된 장점이다.

7.3 초기화

상태에 대한 사전 정보가 전혀 없는 경우, 칼만 필터에서는 \mathbf{P}_0를 매우 큰 값으로 설정해야 하는 반면, 정보 필터에서는 \boldsymbol{\Omega}_0 = \mathbf{0}, \boldsymbol{\xi}_0 = \mathbf{0}으로 자연스럽게 초기화할 수 있다. 이는 정보가 없는 상태를 정보 행렬이 영 행렬인 것으로 표현하는 것이 수학적으로 일관적이기 때문이다.

8. 분산 정보 필터

다수의 로봇이 각자 관측을 수행하고 정보를 교환하는 분산 추정 시스템에서, 정보 형태는 특히 적합하다. 로봇 i가 수집한 정보 기여분

\Delta \boldsymbol{\Omega}_k^{(i)} = (\mathbf{H}_k^{(i)})^T (\mathbf{R}_k^{(i)})^{-1} \mathbf{H}_k^{(i)}

\Delta \boldsymbol{\xi}_k^{(i)} = (\mathbf{H}_k^{(i)})^T (\mathbf{R}_k^{(i)})^{-1} \mathbf{z}_k^{(i)}

를 중앙 서버에 전송하면, 서버는 이를 합산하여 전체 추정을 갱신한다. 통신 순서에 무관하고, 각 로봇의 기여분은 독립적으로 계산 가능하다.

합의 기반(consensus-based) 분산 필터에서는 인접 로봇 간의 정보 교환을 반복하여, 중앙 서버 없이도 전체 정보의 합의에 수렴시킬 수 있다. 이때 통신 그래프의 라플라시안 행렬(Laplacian matrix)의 스펙트럼 간극(spectral gap)이 수렴 속도를 결정한다.

9. 참고 문헌

• Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
• Mutambara, A. G. O. (1998). Decentralized Estimation and Control for Multisensor Systems. CRC Press.
• Eustice, R. M., Singh, H., & Leonard, J. J. (2006). Exactly sparse delayed-state filters for view-based SLAM. IEEE Transactions on Robotics, 22(6), 1100–1114.
• Walter, M. R., Eustice, R. M., & Leonard, J. J. (2007). Exactly sparse extended information filters for feature-based SLAM. International Journal of Robotics Research, 26(4), 335–359.
• Simon, D. (2006). Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches. Wiley.

v 0.1