University of Washington - Computer Science & Engineering
Computing the probability of a formula given weights associated with other formulas is a natural extension of logical inference to the probabilistic setting. Surprisingly, this problem has received little attention in the literature to date, particularly considering that the problem of probabilistic inference over graphical models can be reduced to it.
In this talk, I'll present two formula-based algorithms for this problem: formula decomposition and conditioning, which is an exact method, and formula SampleSearch, which is an approximate sampling-based method. The latter is, to my knowledge, the first application of model counting to approximate probabilistic inference. Unlike conventional variable-based algorithms which explore the search-space defined by truth-assignments to variables, formula-based algorithms explore the search space defined by truth assignments to logical formulas. This simple notion generalizes variable-based inference because a variable is a special case of a formula, namely a unit clause. Formula-based inference is quite powerful because it can often yield a substantially smaller search space as compared to variable-based inference. Thus, theoretically, formula-based algorithms are guaranteed to be more efficient than their variable-based counterparts.
Experimentally, I'll show that formula-based algorithms are not only theoretically viable but also practically relevant, often achieving substantial performance gains over state-of-the-art variable-based algorithms. In particular, I'll present results from the recently held 2010 UAI approximate inference challenge, in which formula SampleSearch won 2 out of 3 categories in the likelihood estimation track.
This is a joint work with Pedro Domingos and appeared in UAI 2010.