用范畴论统一解释信念传播的成败,提出可精确推断的新算法。
Categorical Belief Propagation: Sheaf-Theoretic Inference via Descent and Holonomy
- 基于纤维化和上同调构建信念传播的范畴框架
- 通过计算因子复形的全同性检测推断障碍,实现精确推断
- 适合对概率图模型理论或推理算法优化感兴趣的读者
本文为因子图上的信念传播建立范畴基础。构造带类型的签名自由超图范畴 \\(Syn_Σ\\) 并证明其泛性质,从而通过唯一函子映射到矩阵范畴 \\(Mat_R\\) 获得组合语义。消息传递通过在极化因子图上的格罗滕迪克纤维化 \\(∫\Msg → \cat{FG}_Σ\\) 定义,调度索引的自同态决定 BP 更新。我们刻画精确推断为有效下降:当重叠区域满足相容条件时,局部信念构成下降数据。该框架统一了树状精确性、联结树算法与环路 BP 失败的上同调障碍。提出 HATCC(全同性感知树编译)算法,通过在因子复形上计算全同性检测下降障碍,将非平凡全同性编译为模式变量,并在扩展图上归约为树状 BP。复杂度为 \\(O(n^2 d_{\max} + c \cdot k_{\max} \cdot δ_{\max}^3 + n \cdot δ_{\max}^2)\\),其中 \\(n\\) 为因子数,\\(c\\) 为基本环数。实验表明,在网格马尔可夫随机场与随机图上显著优于联结树的速度,且可在可满足性实例中检测不可满足性。
原文摘要 · Abstract (English)
We develop a categorical foundation for belief propagation on factor graphs. We construct the free hypergraph category \(\Syn_Σ\) on a typed signature and prove its universal property, yielding compositional semantics via a unique functor to the matrix category \(\cat{Mat}_R\). Message-passing is formulated using a Grothendieck fibration \(\int\Msg \to \cat{FG}_Σ\) over polarized factor graphs, with schedule-indexed endomorphisms defining BP updates. We characterize exact inference as effective descent: local beliefs form a descent datum when compatibility conditions hold on overlaps. This framework unifies tree exactness, junction tree algorithms, and loopy BP failures under sheaf-theoretic obstructions. We introduce HATCC (Holonomy-Aware Tree Compilation), an algorithm that detects descent obstructions via holonomy computation on the factor nerve, compiles non-trivial holonomy into mode variables, and reduces to tree BP on an augmented graph. Complexity is \(O(n^2 d_{\max} + c \cdot k_{\max} \cdot δ_{\max}^3 + n \cdot δ_{\max}^2)\) for \(n\) factors and \(c\) fundamental cycles. Experimental results demonstrate exact inference with significant speedup over junction trees on grid MRFs and random graphs, along with UNSAT detection on satisfiability instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。