Pattern-based compaction for ProbLog inference

The probabilistic inference of current Probabilistic Logic Programming systems uses weighted model counting (WMC). To compute the success probability of a query, first the set of proofs of the query is computed. Next, the set of proofs is converted into a corresponding Boolean formula which is compiled into a suitable representation that allows WMC in polynomial time. The computational cost of each step depends on the size and the complexity of the output of the previous step. The set of proofs, computed in the first step, can become large. In this paper we propose a way to reduce the size of the collected proofs in order to improve the next steps. We use an AND-OR graph to represent the collected proofs. Our method compacts the AND-OR graph by detecting several patterns and applying transformations on them. Experiments confirm that by decreasing the size of the AND-OR graph, we reduce the time and memory consumption of the next steps. Our algorithm enables probabilistic inference on problems previously unsolvable.nrpages: 19status: publishe