Author:

Keywords:

ProbLog, Statistical Relation Learning, Probabilistic Logical Programming, Variable Compression, Binary Decision Diagrams, Science & Technology, Technology, Physical Sciences, Computer Science, Software Engineering, Computer Science, Theory & Methods, Mathematics, Applied, Computer Science, Mathematics, Probabilistic Logic Programming, COMPLEXITY

Abstract:

In order to compute the probability of a query, ProbLog represents the proofs of the query as disjunctions of conjunctions, for which a Reduced Ordered Binary Decision Diagram (ROBDD) is computed. The paper identifies patterns of Boolean variables that occur in Boolean formulae, namely AND-clusters and OR-clusters. Our method compresses the variables in these clusters and thus reduces the size of ROBDDs without affecting the probability. We give a polynomial algorithm that detects AND-clusters in disjunctive normal form (DNF) Boolean formulae, or OR-clusters in conjunctive normal form (CNF) Boolean formulae. We do an experimental evaluation of the effects of AND-cluster compression for a real application of ProbLog. With our prototype implementation we have a significant improvement in performance (up to 87%) for the generation of ROBDDs. Moreover, compressing AND-clusters of Boolean variables in the DNFs makes it feasible to deal with ProbLog queries that give rise to larger DNFs.