Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting
Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting
复制标题
DOI：
10.1609/aaai.v34i04.5705
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Ralph Abboud;I. Ceylan;Thomas Lukasiewicz
中科院分区：
文献类型：
--
作者：
Ralph Abboud;I. Ceylan;Thomas Lukasiewicz
加权模型计数(WMC)已成为一种流行的概率推理方法。在其最一般的形式中，WMC是#P-Hard。加权DNF计数是一种特殊情况，其中在O(Nm)内得到具有概率保证的近似，其中n表示变量数，m表示输入DNF的子句数，但这在实践中是不可伸缩的。本文提出了一种加权#DNF的神经模型计数方法，该方法将近似模型计数与深度学习相结合，在宽度有界的情况下，能够在线性时间内精确逼近模型计数。我们通过实验验证了我们的方法，并表明我们的模型对大规模的#DNF实例具有很好的学习和推广能力。
Weighted model counting (WMC) has emerged as a prevalent approach for probabilistic inference. In its most general form, WMC is #P-hard. Weighted DNF counting (weighted #DNF) is a special case, where approximations with probabilistic guarantees are obtained in O(nm), where n denotes the number of variables, and m the number of clauses of the input DNF, but this is not scalable in practice. In this paper, we propose a neural model counting approach for weighted #DNF that combines approximate model counting with deep learning, and accurately approximates model counts in linear time when width is bounded. We conduct experiments to validate our method, and show that our model learns and generalizes very well to large-scale #DNF instances.