关于因子图中交换因子的检测：必要与充分条件

arXiv cs.AI 论文
factor-graphs commutative-factors lifted-inference probabilistic-graphical-models algorithm theoretical

摘要

本文重新审视了因子图中检测交换因子的理论基础，修正了先前错误的充分条件，并提出了修正后的算法。

arXiv:2605.26908v1 公告类型：新 摘要：在概率图模型（如因子图）中利用对象的不可区分性是提升概率推理算法的关键，并且能够处理与领域规模相关的可计算概率推理问题。利用因子图中不可区分对象的一个核心构建块是识别交换因子，即那些输出值在分配给其自变量子集的输入值的排列下保持不变的因子。在本文中，我们重新审视了当前最先进的检测交换因子算法背后的理论基础。具体来说，我们表明在其当前形式下，最先进的算法依赖于一个被错误地视为识别交换因子的充分条件的中心定理，而实际上它只暗示了必要条件。因此，正如我们在本文中所展示的，该最先进算法可能会产生错误的结果。为了解决当前最先进算法中存在的缺陷，我们证明了上述定理的一个稍加修改的版本，该版本作为识别交换因子的一个必要条件。此外，我们提出了一个修正后的最先进算法版本，它在保持效率的同时确保正确性，并引入了一个具有更紧最坏情况界限的补充算法。
查看原文
查看缓存全文

缓存时间: 2026/05/27 09:09 

# 关于因子图中交换因子检测：充要条件
来源：https://arxiv.org/abs/2605.26908
查看 PDF (https://arxiv.org/pdf/2605.26908)

> **摘要：** 在概率图模型（如因子图）中利用对象不可区分性，是提升概率推理算法的关键，能够实现对域规模下可处理的概率推理问题。在因子图中，利用不可区分对象的核心构建模块之一是识别交换因子，即其输出值在对其部分参数输入值进行置换时保持不变的因子。本文重新审视了现有最优交换因子检测算法所依赖的理论基础。具体而言，我们表明，现有最优算法所依赖的一个核心定理目前被错误地视为识别交换因子的充分条件，而实际上它仅蕴含必要条件。因此，正如本文所示，现有算法可能得出错误结果。为解决当前现有算法中的缺陷，我们证明了一个稍加修改的上述定理版本，该版本可作为识别交换因子的必要条件。此外，我们提出了一种修正后的现有最优算法，该算法在保持高效性的同时确保正确性，并引入了一个具有更紧最坏情况下界补的算法。

## 提交历史

来自：Malte Luttermann [查看邮件 (https://arxiv.org/show-email/c382cbc9/2605.26908)]  
**[v1]** 2026年5月26日星期二 12:05:53 UTC (55 KB)

相似文章

计算图的支配点

Lobsters Hottest

一篇技术博客文章，解释如何计算图的支配点，比较 Lengauer-Tarjan 算法与“A Simple, Fast Dominance Algorithm”，并深入介绍数据流方法背后的直觉。

代数图上的搜索

Lobsters Hottest

本文讨论了直接在代数图表示上运行Dijkstra算法的方法，无需转换为邻接图，并利用了图压缩技术。