Weighted model counting has emerged as a prevalent approach for probabilistic inference. In this paper, we are interested in weighted DNF counting, or briefly, weighted #DNF, which admits a fully polynomial randomized approximation scheme, as shown by Karp and Luby. To this date, the best algorithm for approximating #DNF is due to Karp, Luby and Madras. The drawback of this algorithm is that it runs in quadratic time and hence is not suitable for fast online reasoning. To overcome this, we propose a novel approach that combines approximate model counting with deep learning. We conduct detailed experiments to validate our approach, and show that our model learns and generalizes from #DNF instances with a very high accuracy.
翻译:加权模型计数已成为概率推论的普遍方法。 在本文中, 我们有兴趣使用加权的 DNF 计数, 或简短的加权 #DNF, 承认Karp 和 Luby 所显示的完全多元随机近似方案。 到今天, 约合 #DNF 的最佳算法是Karp、 Luby 和 Madras 。 这个算法的缺点是它运行在二次时间, 因此不适合快速在线推理 。 为了克服这一点, 我们提出了一种新颖的方法, 将近似模型计数与深层学习结合起来。 我们进行详细的实验来验证我们的方法, 并显示我们的模型非常精确地从 # DNF 实例中学习和概括。