Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting

Understand

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.