Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting
By Ralph Abboud, Ismail Ilkan Ceylan, Thomas Lukasiewicz. 2019
32 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Natural Language Processing, Prompting & Reasoning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Mohit Bansal
- Kyle Richardson
- Swarnadeep Saha
- Peter Clark
- Oyvind Tafjord
- Ashish Sabharwal
- Hannaneh Hajishirzi
- Shashank Srivastava
In Natural Language Processing
- Mohit Bansal
- Kyle Richardson
- Swarnadeep Saha
- Peter Clark
- Oyvind Tafjord
- Ashish Sabharwal
- Shashank Srivastava
- Sayan Ghosh
In Prompting & Reasoning
- Mohit Bansal
- Peter Clark
- Kyle Richardson
- Oyvind Tafjord
- Shashank Srivastava
- Swarnadeep Saha
- Antonia Creswell
- Murray Shanahan
Citations in the corpus
- Transformers as Soft Reasoners over Language (2020, methodology): “, 2019], approximate (DNF) model counting [Abboud et al., 2020], and formula embedding [Abdelaziz et al.”
- PRover: Proof Generation for Interpretable Reasoning over Rules (2020, methodology): “, 2020), approximate (DNF) model counting (Abboud et al., 2020), etc.”