[Paper] 베이지안 네트워크, 마코프 네트워크, Moralisation, Triangulation: 범주적 관점

Source: arXiv - 2512.09908v1

Overview

논문 **“Bayesian Networks, Markov Networks, Moralisation, Triangulation: a Categorical Perspective”**는 확률 그래프 모델의 두 고전 변환—도덕화 (지시형 베이즈 네트워크를 무향 마르코프 네트워크로 변환)와 삼각분할 (그 반대 방향)—을 범주 이론의 관점에서 재구성한다. 네트워크 자체를 펑터(functor)로 취급함으로써 저자들은 구문적 재작성(순수히 구조적인)과 의미적 연산(기저 확률 분포와 관련된) 사이의 명확한 구분을 드러낸다. 이 추상화는 변수 소거와 같은 오래된 알고리즘 단계를 명료하게 할 뿐만 아니라, 확률적 추론을 위한 보다 모듈식·합성 가능한 소프트웨어로 나아가는 길을 연다.

Key Contributions

• 그래프 모델의 펑터적 표현: 베이즈 네트워크와 마르코프 네트워크를 “구문” 범주(그래프 구조)에서 “의미” 범주(확률 공간)로 가는 펑터로 모델링한다.
• 도덕화와 삼각분할의 범주적 정식화: 두 변환 모두 펑터 사전합성(pre‑composition)으로 표현되며, 도덕화는 완전히 구문적이고 삼각분할은 의미 정보를 필요로 한다.
• 변수 소거의 분해: 고전적인 소거 알고리즘을 두 개의 독립적인 펑터로 나눈다—하나는 구문적 삼각분할 단계, 다른 하나는 의미적 인자 결합 단계.
• 구문 vs. 의미 수정의 명확한 구분: 프레임워크는 변환의 어느 부분이 그래프에만 영향을 주고, 어느 부분이 기저 확률 분포에 영향을 주는지를 명시한다.
• 합성 확률 프로그래밍을 위한 기초 작업: 모델 변환을 범주적 사상으로 캐스팅함으로써, 확률 프로그램을 구축·조작하는 모듈식 방식을 제시한다.

Methodology

1. 구문 범주 정의: 객체는 그래프‑유사 구조(베이즈 네트워크의 노드·방향성 간선, 마르코프 네트워크의 무향 간선)이며, 사상은 그래프 재작성을 포착한다.
2. 의미 범주 정의: 객체는 확률 공간이고, 사상은 가측 함수(예: 주변화, 조건부)이다.
3. 구체적인 네트워크를 펑터 F : Syntax → Semantics 로 모델링하여 각 구문 구성요소에 해당 확률 인자를 할당한다.
4. 도덕화는 구문 측면의 도덕화 펑터와 베이즈‑넷 펑터를 사전합성(pre‑compose)함으로써 표현되며, 확률 계산이 전혀 필요하지 않다.
5. 삼각분할은 의미에 의존하는 삼각분할 펑터와 마르코프‑넷 펑터를 사전합성함으로써 표현된다(예: 변수 소거 순서).
6. 변수 소거는 두 펑터의 합성으로 재구성된다:
   • 구문 삼각분할 펑터: 그래프를 코드랄하게 만들기 위해 fill‑in 간선을 추가한다.
   • 의미 소거 펑터: 관련 인자를 곱하고 주변화한다.

모든 구성은 펑터성을 증명하여, 변환을 연쇄적으로 적용할 때 합성 및 항등성이 보존됨을 보장한다.

Results & Findings

• 도덕화는 순수 구문적 변환: 베이즈 네트워크를 마르코프 네트워크로 변환할 때 기저 확률 테이블은 전혀 건드리지 않는다; 그래프만 재작성한다.
• 삼각분할은 구문과 의미가 혼합: 그래프 구조( fill‑in 간선 추가)는 구문적으로 기술될 수 있지만, 어느 간선을 추가할지는 인자 크기에 기반한 소거 순서에 따라 달라지므로 의미적 고려가 필요하다.
• 변수 소거가 깔끔히 분리: 두 펑터를 분리함으로써, 추론의 비용이 많이 드는 부분(새 인자 계산)을 그래프 구조를 만드는 저렴한 부분과 명확히 구분할 수 있음을 보여준다.
• 펑터성은 합성 가능성을 보장: 도덕화, 삼각분할, 소거를 연쇄하는 어떤 파이프라인도 예측 가능하게 동작하므로 복잡한 추론 파이프라인을 모듈식으로 다룰 수 있다.

Practical Implications

• 모듈식 추론 라이브러리: 개발자는 구문 부분(그래프 변환)을 한 번 구현하고, 다양한 확률 백엔드(이산, 연속, 하이브리드 등)와 결합해도 그래프 코드를 수정할 필요가 없다.
• 확률 프로그래밍 언어(PPL) 컴파일 최적화: 컴파일러는 도덕화를 컴파일‑타임 재작성으로, 삼각분할은 인자 크기 통계에 접근 가능한 런타임 최적화 단계로 미룰 수 있어 메모리·속도 절충을 개선한다.
• 설명 가능한 AI 도구: 범주적 관점이 “모델이 어떻게 보이는가”와 “숫자는 무엇을 의미하는가”를 분리하므로, 디버깅 도구가 순수 구문적 변화(예: 추가된 fill‑in 간선)를 수치적 문제(예: 인자 곱셈 중 오버플로)와 독립적으로 시각화할 수 있다.
• 교육 및 문서화: 펑터적 시각은 언어에 구애받지 않는 고수준 설명을 제공해, 새로운 엔지니어가 왜 도덕화는 저렴하고 삼각분할은 비용이 많이 드는지 직관적으로 이해하도록 돕는다.
• 모델 동등성 자동 검증 가능성: 변환이 사상이므로 자동 정리 증명기가 서로 다른 파이프라인이 동일한 기저 분포를 생성함을 검증할 수 있어, 모델 버전 관리와 재현성을 지원한다.

Limitations & Future Work

• 추상성 vs. 구현: 범주적 형식은 우아하지만, 추가적인 엔지니어링 없이 고성능 코드로 옮기는 것이 쉽지 않을 수 있다.
• 의미적 삼각분할의 확장성: 의미적 구성 요소는 여전히 휴리스틱(예: min‑fill, min‑weight)에 의존하며, 매우 큰 모델에서는 비용이 많이 든다; 논문은 새로운 휴리스틱을 제시하지 않는다.
• 정확 추론에 국한: 프레임워크는 정확한 변수 소거에 초점을 맞추며, 루프 베일리 전파나 변분 추론 같은 근사 방법으로 확장하는 것은 아직 미해결 과제이다.
• 실증적 검증 부족: 저자들은 이론적 증명을 제공하지만 실험적 벤치마크는 제한적이다; 향후 연구에서는 실제 PPL에서 구문·의미 단계를 분리했을 때의 런타임 향상을 정량화할 필요가 있다.

Authors

• Antonio Lorenzin
• Fabio Zanasi

Paper Information

• arXiv ID: 2512.09908v1
• Categories: cs.AI, cs.LO, math.CT
• Published: December 10, 2025
• PDF: Download PDF