[论文] 贝叶斯网络, 马尔可夫网络, Moralisation, Triangulation: 范畴视角

Source: arXiv - 2512.09908v1

概览

论文 “贝叶斯网络、马尔可夫网络、道德化、三角化：一种范畴视角” 通过 范畴论 的视角重新审视概率图模型中的两种经典转换——道德化（将有向贝叶斯网络转化为无向马尔可夫网络）和三角化（相反方向的转换）。作者将网络本身视为函子，揭示了 句法 重写（纯结构性）与 语义 操作（涉及底层概率分布）之间的清晰分离。这种抽象不仅阐明了长期存在的算法步骤，如变量消除，还为构建更模块化、可组合的概率推理软件打开了道路。

主要贡献

• 图模型的函子表示：贝叶斯网络和马尔可夫网络被建模为从“句法”范畴（图结构）到“语义”范畴（概率空间）的函子。
• 道德化与三角化的范畴化表述：两种转换都成为函子前组合，其中道德化完全是句法层面的，而三角化则需要语义信息。
• 变量消除的分解：经典的消除算法被拆分为两个独立的函子——一个处理句法三角化步骤，另一个处理语义因子组合步骤。
• 句法与语义修改的明确区分：该框架明确指出哪些转换只影响图结构，哪些影响底层概率分布。
• 为组合式概率编程奠定基础：通过将模型转换视为范畴态射，工作提出了一种模块化构建和操作概率程序的方式。

方法论

1. 定义句法范畴，其对象是图状结构（贝叶斯网的有向边、马尔可夫网的无向边），其态射捕获图的重写。
2. 定义语义范畴，其对象是概率空间，其态射是可测映射（例如边缘化、条件化）。
3. 将具体网络建模为函子 F : Syntax → Semantics，为每个句法组件分配相应的概率因子。
4. 道德化 表示为在句法侧与道德化函子前组合贝叶斯网函子；不需要任何概率计算。
5. 三角化 表示为在句法侧与三角化函子前组合马尔可夫网函子，该函子依赖于语义（例如变量消除顺序）。
6. 变量消除 被重新表述为两个函子的组合：
   • 一个 句法三角化函子，向图中添加填充边使其成为弦图；
   • 一个 语义消除函子，对相关因子进行乘积并边缘化。

所有构造均被证明是函子的，保证了链式转换遵守组合与恒等律。

结果与发现

• 道德化是纯句法的：将贝叶斯网络转换为马尔可夫网络从不触及底层概率表；它仅是图的重写。
• 三角化混合句法与语义：虽然图结构（添加填充边）可以用句法描述，但具体添加哪些边取决于消除顺序，而消除顺序受因子大小等分布特性的影响——属于语义层面。
• 变量消除清晰分割：通过分离两个函子，论文展示了推理中昂贵的部分（计算新因子）可以与较廉价的图结构部分（使图成为弦图）隔离。
• 函子性保证可组合性：任何将道德化、三角化和消除串联的管线都表现可预测，从而实现对复杂推理管线的模块化推理。

实际意义

• 模块化推理库：开发者可以一次实现句法部分（图转换），并在不同的概率后端之间复用，只需在不触及图代码的情况下替换自定义语义（离散、连续或混合分布）。
• 概率编程语言（PPL）编译优化：编译器可以将道德化视为编译时重写，而将三角化延迟到运行时优化阶段，以获取因子大小统计信息，从而在内存和速度之间取得更佳平衡。
• 可解释 AI 工具：由于范畴视角将“模型外观”与“数值含义”分离，调试工具可以独立可视化纯句法变化（如新增的填充边）和数值问题（如因子乘积时的溢出）。
• 教育与文档：函子视角提供了一种高层、语言无关的方式来教授图模型转换，使新工程师更容易理解为何某些步骤（如道德化）代价低，而其他步骤（如三角化）代价高。
• 模型等价性的自动推理潜力：由于转换是态射，自动定理证明器可以验证不同管线是否产生相同的底层分布，帮助模型版本管理和可重复性。

局限性与未来工作

• 抽象性与实现之间的差距：尽管范畴形式优雅，但在没有额外工程层的情况下将其转化为高性能代码可能并非易事。
• 语义三角化的可扩展性：语义部分仍依赖于启发式（如最小填充、最小权重），在超大模型上可能代价高昂；本文未提供新的启发式。
• 局限于精确推理：框架聚焦于精确的变量消除；将其扩展到近似方法（如环路信念传播、变分推断）仍是未解挑战。
• 经验验证不足：作者提供了理论证明，但实验基准有限；未来工作可以在真实 PPL 中量化分离句法与语义步骤带来的运行时提升。

总体而言，本文提供了一种新颖且数学严谨的方式来思考经典图模型转换，为构建更可组合、可维护的概率软件奠定了基础。

作者

• Antonio Lorenzin
• Fabio Zanasi

论文信息

• arXiv ID: 2512.09908v1
• 分类: cs.AI, cs.LO, math.CT
• 出版时间: 2025 年 12 月 10 日
• PDF: Download PDF