Compositionality in algorithms for smoothing

이 논문은 **부분 관측 시스템 (Partially Observed Systems)**에 대한 베이지안 추론, 특히 스무딩 (Smoothing) 문제를 해결하기 위한 역방향 필터링 전방향 가이드 (Backward Filtering Forward Guiding, BFFG) 알고리즘을 범주론 (Category Theory) 의 관점에서 분석하고 그 **구성성 (Compositionality)**을 규명하는 것을 목표로 합니다.

다음은 논문의 문제 정의, 방법론, 주요 기여, 결과 및 의의에 대한 상세한 기술적 요약입니다.

1. 문제 정의 (Problem)

• 배경: 최근 컴퓨팅 성능의 향상으로 통계 및 머신러닝 모델의 규모와 복잡도가 급격히 증가했습니다. 이러한 복잡한 알고리즘을 이해하고 분석하기 위해서는 알고리즘의 기본 구성 요소와 그 간의 관계를 파악하는 **구성성 (Compositionality)**을 이해하는 것이 필수적입니다.
• 핵심 문제: 상태 공간 모델 (State Space Models) 또는 은닉 마르코프 모델 (HMM) 과 같은 부분 관측 시스템에서, 관측된 리프 (leaf) 노드들의 데이터를 바탕으로 내부 (비관측) 노드들의 분포를 추론하는 스무딩 문제가 있습니다.
• 기존 접근법의 한계:
  • 칼만 필터 - 스무더 (선형 가우스 시스템) 나 유한 상태 공간과 같은 특정 설정에서는 폐쇄형 해 (closed-form solution) 를 구할 수 있습니다.
  • 그러나 일반적인 비선형/비가우스 시스템에서는 정확한 스무딩 분포를 계산하기 어렵습니다.
  • 기존 알고리즘인 **역방향 필터링 전방향 샘플링 (BFFS)**이나 **역방향 필터링 전방향 가이드 (BFFG)**는 양방향 데이터 흐름을 가지지만, 이를 구성적인 관점에서 체계적으로 분석한 연구는 부족했습니다.

2. 방법론 (Methodology)

저자들은 범주론 (Category Theory), 특히 옵틱스 (Optics) 개념을 도입하여 BFFG 알고리즘을 재해석하고 그 구조적 성질을 증명했습니다.

• 옵틱스 (Optics) 활용:
  • 옵틱스는 양방향 데이터 흐름을 모델링하기 위해 고안된 범주론적 구조입니다.
  • BFFG 알고리즘의 두 단계인 **역방향 필터링 (Backward Filtering)**과 **전방향 가이드 (Forward Guiding)**를 옵틱스의 **첫 번째 맵 (forward pass)**과 **두 번째 맵 (backward pass)**에 대응시킵니다.
  • 참고: 논문의 용어에 따르면, BFFG 의 '역방향 필터링'이 옵틱스의 '첫 번째 맵'에, '전방향 가이드'가 '두 번째 맵'에 해당합니다.
• 마르코프 커널과 범주:
  • 마르코프 커널이 형성하는 범주 $Stoch$와 이를 기반으로 정의된 **옵틱스 범주$Optic(Set)$**을 사용합니다.
  • BFFG 알고리즘을 마르코프 커널 쌍 $(\kappa, \tilde{\kappa})$ (여기서 $\kappa$는 실제 전이 커널, $\tilde{\kappa}$는 가이드를 위한 근사 커널) 에서 옵틱스로 매핑하는 **함자 (Functor)**로 정의합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

논문의 핵심 기여는 BFFG 알고리즘이 **함자 (Functor)**이며, 특정 조건에서 느슨한 단사적 (Lax Monoidal) 성질을 가진다는 것을 수학적으로 증명하는 것입니다.

3.1. 순차 구성성의 보존 (Functoriality)

• 정리 8 (Theorem 8): BFFG 알고리즘은 마르코프 커널의 범주 $Stoch^2$의 반대 범주에서 옵틱스 범주 $Optic(Set)$로 가는 **반변함자 (Contravariant Functor)**를 정의합니다.
• 의미: 두 개의 마르코프 커널을 순차적으로 합성 (Composition) 한 후 BFFG 를 적용하는 것과, 각 커널에 BFFG 를 적용하여 얻은 옵틱스를 합성하는 것은 동일한 결과를 냅니다.
  • 즉, $O(\kappa_1 \circ \kappa_2) \cong O(\kappa_2) \circ O(\kappa_1)$이 성립합니다.
  • 이는 알고리즘을 그래프의 엣지 단위로 분해하여 구현하고 합성할 수 있음을 보장합니다.

3.2. 병렬 구성성의 보존 (Lax Monoidality)

• 정리 11 (Theorem 11): 가이드 커널이 실제 커널과 일치하는 경우 ($\tilde{\kappa} = \kappa$, 즉 BFFS 알고리즘) 에는, BFFG 알고리즘은 **느슨한 단사적 함자 (Lax Monoidal Functor)**가 됩니다.
• 의미: 독립적인 두 시스템 (병렬 구성) 에 대해 BFFS 를 적용한 후 합성하는 것과, 결합된 시스템에 BFFS 를 적용하는 것은 **동치 (Equivalence)**입니다.
  • 이는 조건부 독립성이 리프 노드의 관측 하에서도 유지됨을 의미합니다.
• BFFG 의 경우: 일반적인 BFFG ($\tilde{\kappa} \neq \kappa$) 의 경우, 전역 가중치 (Global Weights) 를 추적해야 하므로 엄밀한 단사적 성질은 깨지지만, 몬테카를로 추론 (MCMC, SMC) 의 관점에서는 이 차이가 중요하지 않음을 Remark 17에서 설명합니다.

3.3. 알고리즘적 함의

• 구성적 접근: 복잡한 스무딩 알고리즘을 기본 단위 (엣지별 전방향/역방향 맵) 로 분해하여 구현할 수 있음을 보여줍니다.
• 유연성:
  • 관측 누락 처리: 관측이 없는 노드를 건너뛰고 커널을 합성하여 처리할 수 있습니다 (예 19).
  • 비처리 가능한 커널 분해: 계산이 불가능한 커널을 여러 개의 처리 가능한 작은 커널로 분할하여 근사할 수 있습니다 (예 20, 21).

4. 의의 및 결론 (Significance)

1. 이론적 통찰: BFFG 와 같은 복잡한 통계 알고리즘이 단순한 계산 절차가 아니라, 범주론적 구조를 보존하는 고차원적 (Higher-order) 구조를 가지고 있음을 규명했습니다.
2. 구현의 용이성: 알고리즘을 엣지 단위의 구성 요소로 분해할 수 있으므로, 복잡한 모델 (예: SDE, 복잡한 트리 구조) 에 대한 구현과 이해가 용이해집니다.
3. 확장성: 이 프레임워크는 HMM 을 넘어 더 일반적인 방향성 그래프 (Directed Acyclic Graphs) 및 트리 구조의 확률 과정에 적용 가능합니다.
4. 미래 연구: 범주론적 확률 (Categorical Probability) 과 옵틱스를 결합하여 베이지안 추론 알고리즘을 체계적으로 분류하고 새로운 알고리즘을 설계하는 데 기초를 제공합니다.

요약하자면, 이 논문은 BFFG 알고리즘이 마르코프 커널의 합성과 옵틱스의 합성을 보존하는 함자임을 증명함으로써, 통계적 스무딩 문제를 구성적 (Compositional) 관점에서 재정의하고 알고리즘의 모듈화와 유연성을 이론적으로 뒷받침했습니다.