改进对称性检测算法，让概率推理更快更紧凑。
Lifted Model Construction without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs
- 提出向量化方法，允许因子间任意缩放仍识别对称性
- 实验显示推理时间显著降低，比原算法检测更多对称性
- 适合需要高效概率推理的逻辑建模场景
提升概率推理通过利用概率模型中变量域规模的对称性实现可计算推理。我们发现当前最先进的参数化因子图构建算法——先进着色传递（ACP）——会遗漏可交换但缩放不同的因子之间的对称性，导致表示不够紧凑。本文提出ACP算法的推广版本，允许因子势函数任意缩放，并能更高效地检测出更多对称性。相比原始ACP算法，新算法在生成模型时严格发现了更多对称性，从而在实际应用中显著降低了在线查询的推理时间，实验结果验证了该优势。
原文摘要 · Abstract (English)
Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes of logical variables. We found that the current state-of-the-art algorithm to construct a lifted representation in form of a parametric factor graph misses symmetries between factors that are exchangeable but scaled differently, thereby leading to a less compact representation. In this paper, we propose a generalisation of the advanced colour passing (ACP) algorithm, which is the state of the art to construct a parametric factor graph. Our proposed algorithm allows for potentials of factors to be scaled arbitrarily and efficiently detects more symmetries than the original ACP algorithm. By detecting strictly more symmetries than ACP, our algorithm significantly reduces online query times for probabilistic inference when the resulting model is applied, which we also confirm in our experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。