On Hashing-Based Approaches to Approximate DNF-Counting
On Hashing-Based Approaches to Approximate DNF-Counting
复制标题
基于哈希的近似 DNF 计数方法
DOI：
10.4230/lipics.fsttcs.2017.41
复制
发表时间：
2017
影响因子：
3.1
通讯作者：
Moshe Y. Vardi
中科院分区：
文献类型：
--
作者：
Kuldeep S. Meel;Aditya A. Shrotri;Moshe Y. Vardi
命题模型计数是人工智能中的一个基本问题，在概率推理、不确定性决策、概率数据库等领域有着广泛的应用。因此，这一问题既具有理论意义，又具有实践意义。当约束被表示为DNF公式时，基于蒙特卡罗的技术已经被证明提供了一种完全多项式随机近似方案(FPRAS)。对于CNF约束，基于散列的近似技术已经被证明是非常成功的。此外，基于散列的技术还可以在不使用蒙特卡罗抽样的情况下产生用于DNF计数的FPRAS。然而，我们的分析表明，与基于蒙特卡洛的DNF计数技术相比，所提出的基于散列的DNF计数方法具有较低的时间复杂性。鉴于基于散列的技术在CNF约束方面的成功，人们自然会问：基于散列的技术能否为DNF计数提供有效的FPRAS？在本文中，我们对这个问题给出了肯定的回答。为此，我们引入了两种新的算法技术：符号散列和随机信元计数，以及一个新的散列族。这些创新使我们能够设计一个基于散列的FPRAS，用于DNF计数，其复杂性(最高可达PolyLog因子)与以前的工作相似。此外，我们预计这些技术将在DNF计数之外具有潜在的应用。
Propositional model counting is a fundamental problem in artificial intelligence with a wide variety of applications, such as probabilistic inference, decision making under uncertainty, and probabilistic databases. Consequently, the problem is of theoretical as well as practical interest. When the constraints are expressed as DNF formulas, Monte Carlo-based techniques have been shown to provide a fully polynomial randomized approximation scheme (FPRAS). For CNF constraints, hashing-based approximation techniques have been demonstrated to be highly successful. Furthermore, it was shown that hashing-based techniques also yield an FPRAS for DNF counting without usage of Monte Carlo sampling. Our analysis, however, shows that the proposed hashing-based approach to DNF counting provides poor time complexity compared to the Monte Carlo-based DNF counting techniques. Given the success of hashing-based techniques for CNF constraints, it is natural to ask: Can hashing-based techniques provide an efficient FPRAS for DNF counting? In this paper, we provide a positive answer to this question. To this end, we introduce two novel algorithmic techniques: \emph{Symbolic Hashing} and \emph{Stochastic Cell Counting}, along with a new hash family of \emph{Row-Echelon hash functions}. These innovations allow us to design a hashing-based FPRAS for DNF counting of similar complexity (up to polylog factors) as that of prior works. Furthermore, we expect these techniques to have potential applications beyond DNF counting.