提出ε-交换性,让模型在近似对称时仍可高效推理。
Lifted Model Construction under Approximate Commutativity
- 引入ε-交换性,放宽精确对称要求
- 理论证明误差有界,实际推理更快更准
- 适合处理真实数据中不完全对称的场景
提升推理算法通过利用概率分布中对象的不可区分性,实现大规模对象域上的可扩展概率推理。构建提升表示的关键前提是识别潜在因子分解中的交换性因子,即输出值在输入子集置换下保持不变的函数。然而实践中,从数据学习到的参数不可避免地出现偏差,即使相关对象不可区分,其对应因子也仅近似交换而非严格交换。本文提出ε-交换性概念,作为交换性的松弛,即输出值仅在输入置换下近似不变。具体而言,我们展示了如何利用ε-交换性进行提升模型构建和下游概率推理,并证明了诱导近似误差的严格边界,从而确保提升模型构建的实际可用性,同时保持高精度查询结果。这些理论保证经实证验证,表明在更低运行时间下仍能获得相当的查询精度。
原文摘要 · Abstract (English)
Lifted inference algorithms enable scalable probabilistic inference even for large object domains by leveraging the indistinguishability of objects in a probability distribution. An essential prerequisite for constructing a lifted representation is to identify commutative factors, i.e., functions whose output values are invariant under permutations of a subset of their input values, in a potential-based factorisation. In practice, however, parameters learned from data inevitably deviate even if associated objects are indistinguishable, causing their corresponding factors to be only approximately commutative instead of being exactly commutative. We address this problem by introducing the concept of ε-commutativity, a relaxation of commutativity where output values are only approximately invariant under permutations of input values. Specifically, we show how ε-commutativity can be exploited for lifted model construction, downstream probabilistic inference, and prove strict bounds on the induced approximation error, thereby ensuring the practical applicability of lifted model construction while maintaining highly accurate query results. These theoretical guarantees are confirmed empirically, demonstrating comparable query accuracy at lower runtime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。