12.18 인수 그래프(Factor Graph)의 기본 개념

12.18 인수 그래프(Factor Graph)의 기본 개념

1. 인수 그래프의 개요

인수 그래프(factor graph)는 확률 분포의 인수 분해를 그래프 형태로 표현하는 자료 구조이며, 1988년 라우(Lauritzen)와 슈피겔할터(Spiegelhalter)의 그래픽 모델 연구에서 발전하여 2001년 크첸(Kschischang) 등이 형식화하였다. 인수 그래프는 변수 노드와 인수 노드의 두 종류의 노드를 가진 이분 그래프이며, 변수들 사이의 결합 확률 분포를 효율적으로 표현하고 추론할 수 있게 한다. 로봇공학의 SLAM, 상태 추정, 최적화 등에서 핵심적인 도구이며, 특히 GTSAM 라이브러리의 기반이다.

2. 인수 그래프의 정의

2.1 형식적 정의

인수 그래프 G = (V, F, E)는 다음으로 구성된다.

  • V: 변수 노드의 집합
  • F: 인수 노드의 집합
  • E: 변수와 인수 사이의 엣지

엣지는 변수가 인수에 포함되어 있을 때 존재한다.

2.2 두 종류의 노드

2.2.1 변수 노드

변수 노드는 추정할 미지의 양을 나타낸다. 일반적으로 원으로 표시한다.

  • 자세 (예: SE(3)의 원소)
  • 랜드마크 (예: 3차원 점)
  • 칼리브레이션 매개변수
  • 바이어스
  • 다른 모든 추정 변수

2.2.2 인수 노드

인수 노드는 변수들 사이의 제약 또는 측정을 나타낸다. 일반적으로 사각형이나 작은 점으로 표시한다.

  • 측정 인수 (센서 측정에서 유래)
  • 사전 인수 (사전 분포)
  • 동역학 인수 (운동 모형)
  • 결합 인수 (변수들 사이의 관계)

2.3 이분 구조

인수 그래프는 이분 그래프이다. 변수 노드끼리 또는 인수 노드끼리는 직접 연결되지 않는다. 변수와 인수가 엣지로 연결될 뿐이다.

3. 확률 분포의 인수 분해

3.1 결합 분포

여러 변수의 결합 분포는 일반적으로 인수의 곱으로 표현될 수 있다.

P(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n) = \prod_{i}f_i(\mathbf{x}_{i_1}, \mathbf{x}_{i_2}, \ldots)

여기서 f_i는 변수의 부분 집합에 대한 함수(인수)이다.

3.2 인수 그래프의 표현

이러한 인수 분해가 인수 그래프로 표현된다.

  • 변수 노드: \mathbf{x}_1, \mathbf{x}_2, \ldots
  • 인수 노드: f_1, f_2, \ldots
  • 엣지: 인수가 변수를 인자로 가질 때

3.3 효율성

인수 분해를 명시적으로 표현함으로써 효율적인 추론이 가능하다. 인수 그래프의 구조를 활용한 알고리즘이 사용된다.

4. 인수 그래프와 다른 그래프 모델

4.1 베이즈 네트워크

베이즈 네트워크(Bayesian network)는 방향 그래프이며, 노드는 변수, 엣지는 조건부 의존성이다. 인수 그래프는 베이즈 네트워크의 무방향 일반화로 볼 수 있다.

4.2 마르코프 랜덤 필드

마르코프 랜덤 필드(Markov random field, MRF)는 무방향 그래프이며, 변수들 사이의 조건부 의존성을 표현한다. 인수 그래프는 MRF의 더 명시적인 형태이다.

4.3 변환 가능성

베이즈 네트워크와 MRF는 인수 그래프로 변환될 수 있다. 인수 그래프는 가장 일반적인 표현이다.

5. 인수의 정의

5.1 인수의 형태

인수는 일반적으로 다음의 형태이다.

f(\mathbf{x}) = \exp\!\left(-\frac{1}{2}\mathbf{r}(\mathbf{x})^T\Omega\mathbf{r}(\mathbf{x})\right)

여기서

  • \mathbf{r}(\mathbf{x}): 잔차 함수
  • \Omega: 정보 행렬 (공분산의 역)

이는 가우시안 분포의 형태이며, 비선형 잔차에 대해서도 정의될 수 있다.

5.2 음의 로그 우도

인수의 음의 로그 우도는 가중 잔차의 제곱이다.

-\log f(\mathbf{x}) = \frac{1}{2}\mathbf{r}(\mathbf{x})^T\Omega\mathbf{r}(\mathbf{x}) + \text{const}

이는 비용 함수의 한 항이 된다.

5.3 비가우시안 인수

가우시안이 아닌 인수도 가능하다. 예를 들어 강건 손실 함수(Huber, Cauchy)를 사용한 인수가 있다.

6. 인수의 종류

6.1 사전 인수

사전 인수(prior factor)는 한 변수의 사전 분포를 나타낸다.

f_{\text{prior}}(\mathbf{x}) = P(\mathbf{x})

예를 들어 시작 자세의 사전 분포가 사전 인수이다.

6.2 측정 인수

측정 인수(measurement factor)는 측정값과 변수 사이의 관계를 나타낸다.

f_{\text{meas}}(\mathbf{x}) = P(\mathbf{z} | \mathbf{x})

여기서 \mathbf{z}는 측정값이다.

6.3 운동 인수

운동 인수(motion factor)는 두 시점의 자세 사이의 관계를 나타낸다.

f_{\text{motion}}(\mathbf{x}_t, \mathbf{x}_{t+1}) = P(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t)

여기서 \mathbf{u}_t는 제어 입력이다.

6.4 결합 인수

결합 인수(binary factor)는 두 변수 사이의 관계를 나타낸다.

6.5 다중 인수

세 개 이상의 변수에 의존하는 인수도 가능하다.

7. 인수 그래프 위의 추론

7.1 MAP 추론

가장 일반적인 추론 문제는 MAP(Maximum A Posteriori) 추정이다. 이는 결합 확률을 최대화하는 변수 값을 찾는다.

\hat{\mathbf{X}} = \arg\max_{\mathbf{X}}\prod_{i}f_i(\mathbf{X}_i)

음의 로그를 취하면 비용 함수의 최소화 문제가 된다.

\hat{\mathbf{X}} = \arg\min_{\mathbf{X}}\sum_{i}\frac{1}{2}\mathbf{r}_i(\mathbf{X}_i)^T\Omega_i\mathbf{r}_i(\mathbf{X}_i)

이는 비선형 최소제곱 문제이다.

7.2 주변 분포

특정 변수의 주변 분포(marginal distribution)를 계산하는 것도 추론 문제이다. 이는 합산 알고리즘으로 가능하다.

7.3 합산-곱 알고리즘

합산-곱 알고리즘(sum-product algorithm)은 인수 그래프 위에서 메시지 전달을 통해 주변 분포를 계산한다. 트리 구조의 그래프에서는 정확하다.

7.4 최대-곱 알고리즘

최대-곱 알고리즘(max-product algorithm)은 MAP 추정을 위한 메시지 전달 알고리즘이다.

8. 인수 그래프의 최적화

8.1 비선형 최소제곱

대부분의 SLAM 응용에서 인수 그래프의 최적화는 비선형 최소제곱 문제이다. 가우스-뉴턴법이나 레벤버그-마쿼트법이 사용된다.

8.2 자코비안

자코비안은 잔차의 변수에 대한 미분이다. 인수마다 자코비안을 계산해야 한다.

8.3 정보 행렬의 희소성

인수 그래프의 정보 행렬은 매우 희소하다. 각 인수는 적은 수의 변수에만 의존하기 때문이다.

8.4 효율적인 풀이

희소 선형 시스템의 풀이에는 콜레스키 분해, QR 분해 등이 사용된다.

9. 인수 그래프의 응용

9.1 SLAM

SLAM 문제는 인수 그래프로 자연스럽게 표현된다. 자세와 랜드마크가 변수, 측정과 운동이 인수이다.

9.2 상태 추정

일반적인 상태 추정 문제도 인수 그래프로 표현될 수 있다. 칼만 필터의 일반화로 볼 수 있다.

9.3 비주얼-관성 항법

VIO에서 카메라 자세, 속도, 바이어스 등이 변수이며, 시각 측정과 IMU 미리 적분이 인수이다.

9.4 다중 로봇 SLAM

다중 로봇이 협력하여 SLAM을 수행할 때 각 로봇의 자세와 측정이 통합된 인수 그래프로 표현된다.

9.5 칼만 필터의 일반화

확장 칼만 필터(EKF)는 인수 그래프의 특수한 경우로 볼 수 있다. 인수 그래프는 EKF보다 더 일반적이고 강건하다.

10. GTSAM 라이브러리

10.1 개요

GTSAM(Georgia Tech Smoothing and Mapping)은 인수 그래프 기반 SLAM과 추정 라이브러리이다. 프랭크 델라르트(Frank Dellaert) 그룹이 개발하였으며, 인수 그래프의 표준 도구이다.

10.2 주요 기능

GTSAM은 다음의 기능을 제공한다.

  • 인수 그래프의 구축과 관리
  • 다양한 종류의 인수 (사전, 측정, 운동 등)
  • 비선형 최적화 (가우스-뉴턴, 레벤버그-마쿼트)
  • 점진적 최적화 (iSAM2)
  • 자동 미분
  • 리 군 변수 지원

10.3 사용 예시

#include <gtsam/nonlinear/NonlinearFactorGraph.h>
#include <gtsam/slam/PriorFactor.h>
#include <gtsam/slam/BetweenFactor.h>

gtsam::NonlinearFactorGraph graph;
gtsam::Values initial;

// 사전 인수
graph.add(gtsam::PriorFactor<gtsam::Pose2>(1, prior_pose, prior_noise));

// 운동 인수
graph.add(gtsam::BetweenFactor<gtsam::Pose2>(1, 2, odometry, odometry_noise));

// 초기 추정
initial.insert(1, gtsam::Pose2(0, 0, 0));
initial.insert(2, gtsam::Pose2(2, 0, 0));

// 최적화
gtsam::LevenbergMarquardtOptimizer optimizer(graph, initial);
gtsam::Values result = optimizer.optimize();

11. iSAM과 iSAM2

11.1 점진적 최적화

iSAM(incremental Smoothing and Mapping)은 점진적 인수 그래프 최적화 알고리즘이다. 새로운 측정이 도착할 때 부분적으로만 갱신한다.

11.2 iSAM2

iSAM2는 iSAM의 후속이며, 베이즈 트리(Bayes tree) 자료 구조를 사용한다. 더 효율적이고 유연하다.

11.3 응용

실시간 SLAM 시스템에서 iSAM2가 표준이다.

12. 강건성

12.1 이상치 처리

인수 그래프에서 이상치(outlier) 측정을 처리하기 위한 방법이 있다.

12.2 M-추정

M-추정(M-estimator)은 큰 잔차의 영향을 줄인다. 강건 손실 함수를 인수에 적용한다.

12.3 스위치 가능 제약

스위치 가능 제약(switchable constraints)은 의심스러운 인수를 비활성화할 수 있게 한다.

12.4 동적 공분산 스케일링

DCS는 잔차에 따라 공분산을 동적으로 조정한다.

13. 인수 그래프와 베이즈 네트워크

13.1 변환

베이즈 네트워크는 인수 그래프로 변환될 수 있다. 각 조건부 분포가 인수가 된다.

13.2 차이

측면베이즈 네트워크인수 그래프
그래프 종류방향 그래프이분 그래프
인과 관계명시적명시적이지 않음
일반성제한적일반적

13.3 응용

베이즈 네트워크는 인과 추론에 적합하고, 인수 그래프는 일반 추정에 적합하다.

14. 인수 그래프의 시각화

14.1 그림 표현

인수 그래프는 다음과 같이 시각화된다.

  • 변수: 원
  • 인수: 사각형 (또는 작은 점)
  • 엣지: 변수와 인수를 연결

14.2 도구

GTSAM, g2o 등의 라이브러리는 인수 그래프의 시각화 도구를 제공한다. Graphviz로 출력할 수 있다.

15. 응용 예시: 비주얼 SLAM

비주얼 SLAM에서 인수 그래프는 다음과 같이 구축된다.

  • 변수: 카메라 자세, 3차원 점
  • 인수:
  • 사전 인수: 초기 자세
  • 재투영 인수: 카메라 자세와 3차원 점에 의한 픽셀 측정
  • 운동 인수: 연속된 카메라 자세 사이의 운동

16. 응용 예시: 비주얼-관성 항법

VIO에서 인수 그래프는 더 풍부하다.

  • 변수: 자세, 속도, 자이로 바이어스, 가속도계 바이어스, 3차원 점
  • 인수:
  • 사전 인수
  • 시각 측정 인수
  • IMU 미리 적분 인수
  • 바이어스 진화 인수

17. 응용 예시: 라이다 SLAM

라이다 SLAM에서 인수 그래프는 다음과 같이 구축된다.

  • 변수: 자세 (키스캔)
  • 인수:
  • 사전 인수
  • ICP 정합 인수 (연속된 키스캔)
  • 회로 폐쇄 인수

18. 응용 예시: 다중 센서 융합

여러 센서(GPS, IMU, 카메라, 라이다)의 측정을 융합할 때 인수 그래프가 자연스럽다. 각 센서의 측정이 인수로 추가된다.

19. 응용 예시: 다중 로봇 SLAM

다중 로봇이 협력하여 SLAM을 수행할 때 각 로봇의 변수와 측정이 통합된 인수 그래프로 표현된다.

20. 응용 예시: 매니퓰레이터의 운동학 캘리브레이션

매니퓰레이터의 운동학 매개변수를 캘리브레이션할 때 인수 그래프를 사용할 수 있다. 매개변수가 변수, 측정이 인수이다.

21. 인수 그래프의 한계

21.1 가우시안 가정

대부분의 응용에서 인수가 가우시안으로 가정된다. 비가우시안 분포의 처리는 더 복잡하다.

21.2 큰 그래프의 최적화

매우 큰 인수 그래프의 최적화는 계산 비용이 크다. 점진적 알고리즘과 마진화가 필요하다.

21.3 자코비안 계산

복잡한 인수의 자코비안 계산은 어렵다. 자동 미분이 도움이 된다.

22. 미래의 발전

22.1 학습 기반 인수

신경망으로 학습된 인수가 활발히 연구되고 있다. 측정 모형이나 잡음 모형을 학습한다.

22.2 비가우시안 인수

비가우시안 분포를 다루는 방법이 발전하고 있다.

22.3 분산 인수 그래프

여러 컴퓨터에 분산된 인수 그래프의 최적화 방법이 연구되고 있다.

23. 학습의 가치

인수 그래프를 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

  • 확률적 추론의 강력한 도구를 익힌다.
  • SLAM과 상태 추정의 일반적 틀을 이해한다.
  • GTSAM 등의 라이브러리를 효과적으로 활용할 수 있다.
  • 다양한 측정과 변수를 통합적으로 다룰 수 있다.
  • 학술 문헌의 표준 접근법을 이해할 수 있다.

24. 학습 권장사항

24.1 직접 구현

작은 인수 그래프를 직접 구현해 본다. 단순한 1차원 문제부터 시작한다.

24.2 GTSAM 학습

GTSAM 라이브러리의 튜토리얼을 따라가며 사용법을 익힌다.

24.3 시각화

인수 그래프를 시각화하면 구조를 이해하기 쉽다.

24.4 응용 학습

실제 SLAM 시스템을 인수 그래프로 모델링해 본다.

25. 본 절의 의의

본 절은 인수 그래프의 기본 개념을 다루었다. 인수 그래프는 현대 SLAM과 상태 추정의 이론적 기반이며, GTSAM과 같은 라이브러리를 통해 광범위하게 사용된다. 인수 그래프의 이해는 로봇공학의 핵심 알고리즘을 학습하는 데 필수적이다.

26. 참고 문헌

  • Kschischang, F. R., Frey, B. J., & Loeliger, H. A. (2001). “Factor graphs and the sum-product algorithm.” IEEE Transactions on Information Theory, 47(2), 498–519.
  • Dellaert, F., & Kaess, M. (2017). “Factor graphs for robot perception.” Foundations and Trends in Robotics, 6(1-2), 1–139.
  • Kaess, M., Ranganathan, A., & Dellaert, F. (2008). “iSAM: Incremental smoothing and mapping.” IEEE Transactions on Robotics, 24(6), 1365–1378.
  • Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J. J., & Dellaert, F. (2012). “iSAM2: Incremental smoothing and mapping using the Bayes tree.” International Journal of Robotics Research, 31(2), 216–235.
  • Dellaert, F. (2012). “Factor graphs and GTSAM: A hands-on introduction.” Technical Report, Georgia Tech.
  • Forster, C., Carlone, L., Dellaert, F., & Scaramuzza, D. (2017). “On-manifold preintegration for real-time visual-inertial odometry.” IEEE Transactions on Robotics, 33(1), 1–21.

version: 1.0