Anytime Inference in Probabilistic Logic Programs with Tp-Compilation

Abstract

Existing techniques for inference in probabilistic logic programs are sequential: they first compute the relevant propositional formula for the query of interest, then compile it into a tractable target representation and finally, perform weighted model counting on the resulting representation. We propose Tp-compilation, a new inference technique based on forward reasoning. Tp-compilation proceeds incrementally in that it interleaves the knowledge compilation step for weighted model counting with forward reasoning on the logic program. This leads to a novel anytime algorithm that provides hard bounds on the inferred probabilities. Furthermore, an empirical evaluation shows that Tp-compilation effectively handles larger instances of complex real-world problems than current sequential approaches, both for exact and for anytime approximate inference.