Title: Stable model counting and its application in probabilistic logic programming

Speaker:Rehan Aziz

When: Tuesday, September 2nd 11 AM - 12 NOON

Where: Doug McDonnell-10.05

Abstract:
Model counting is the problem of computing the number of models that satisfy a given propositional theory. It is a well-studied problem and has recently been applied to solving inference tasks in probabilistic logic programming, where the goal is to compute the probability of given queries being true provided a set of mutually independent random variables, a model (a logic program) and some evidence. The core of solving this inference task involves translating the logic program to a propositional theory and using a model counter. The probability of a query being true is the ratio between the weighted model counts of the translated theory plus the query and only the theory, where the weight of an assignment is equal to the product of probabilities of truth values of all random variables in the assignment. In this paper, we show that for some problems that involve inductive definitions like reachability in a graph, the translation of logic programs to SAT can be expensive for the purpose of solving inference tasks. For such problems, logic programming under stable model semantics provides a more natural representation and its implementation allows for more efficient solving. We present two techniques, based on unfounded set detection, that extend a propositional model counter to a stable model counter. Our experiments show that for particular problems, our approach outperforms solving probabilistic logic programs by translating them to SAT.

Bio:
Rehan Aziz is a PhD student at the University of Melbourne and NICTA. His supervisors are Peter Stuckey and Geoffrey Chu. His research interests include Answer Set Programming, and the goal of his PhD is to import useful features from ASP to Constraint Programming, and extend the answer set semantics to numeric quantities.

Back