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

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)

相似文章

诱导因子化概率分布的可比性

arXiv cs.AI

本文提出了一种方法，将定义在不同变量集上的因子化概率分布扩展到共同的可测空间，从而能够使用分布差异度量进行有原则的比较。

快速阶乘算法

Hacker News Top

一份全面资源，详细介绍了计算阶乘函数的多种快速算法，包括 prime swing、split recursive 和 Moessner 算法，并提供了多种编程语言的实现。

图神经网络Top-k解释中的自同构诱导非规范性问题

arXiv cs.LG

本文揭示了图神经网络top-k解释中的一个根本问题：输入图中的自同构导致解释不唯一，因为模型无法区分对称元素。作者提出了一个检测这种任意性的标准，并利用Lean 4中的自动推理对其进行了验证，表明该问题在分子数据集中广泛存在。