Approximate weighted model integration on DNF structures
Approximate weighted model integration on DNF structures
复制标题
DNF 结构上的近似加权模型集成
DOI：
10.1016/j.artint.2022.103753
复制
发表时间：
2022
影响因子：
14.4
通讯作者：
Abboud R
中科院分区：
文献类型：
--
作者：
Abboud R
加权模型计数包括计算命题公式的所有满意赋值的加权和。众所周知，加权模型计数对于精确求解是#P-困难的，但当限制于DNF结构时，它允许完全多项式随机近似方案。在这项工作中，我们研究了加权模型积分，它是加权模型计数的推广，它除了命题变量外还涉及实变量，并提出了以下问题：DNF结构上的加权模型积分是否允许全多项式随机逼近方案？基于近似加权模型计数和近似体积计算的经典结果，我们证明了DNF结构上的加权模型积分确实可以近似为一类权函数。我们的近似算法基于三个子例程，每个子例程都可以是弱的(即近似的)或强的(即精确的)预言，并且在所有情况下都有精度保证。我们在不同大小的随机生成的DNF实例上对我们的方法进行了实验验证，并表明我们的算法可以扩展到大型问题实例，涉及多达1K个变量，而这些变量目前是现有的通用加权模型集成求解器无法达到的。
Weighted model countingconsists of computing the weighted sum of all satisfying assignments of a propositional formula. Weighted model counting is well-known to be#P-hard for exact solving, but admits a fully polynomial randomized approximation scheme when restricted to DNF structures. In this work, we studyweighted model integration, a generalization of weighted model counting which involves real variables in addition to propositional variables, and pose the following question: Does weighted model integration onDNFstructures admit a fully polynomial randomized approximation scheme? Building on classical results from approximate weighted model counting and approximate volume computation, we show that weighted model integration onDNFstructures can indeed be approximated for a class of weight functions. Our approximation algorithm is based on three subroutines, each of which can be aweak(i.e., approximate), or astrong(i.e., exact) oracle, and in all cases, comes along with accuracy guarantees. We experimentally verify our approach over randomly generatedDNFinstances of varying sizes, and show that our algorithm scales to large problem instances, involving up to 1K variables, which are currently out of reach for existing, general-purpose weighted model integration solvers.
登录
查看更多内容
DOI：
10.1609/aaai.v26i1.8406
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
S. Sanner;Ehsan Abbasnejad
通讯作者：
Ehsan Abbasnejad
DOI：
10.1609/aaai.v34i04.5705
发表时间：
2019-04
期刊：
--
影响因子：
--
作者：
Ralph Abboud;I. Ceylan;Thomas Lukasiewicz
通讯作者：
Ralph Abboud;I. Ceylan;Thomas Lukasiewicz
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Borgwardt S
通讯作者：
Borgwardt S
影响因子：
2.7
作者：
Emiris, Ioannis Z.;Fisikopoulos, Vissarion
通讯作者：
Fisikopoulos, Vissarion
基于对数线性概率数据的本体介导的查询应答
DOI：
--
发表时间：
2019
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Stefan Borgwardt;I. Ceylan;Thomas Lukasiewicz
通讯作者：
Thomas Lukasiewicz