Formula-Based Probabilistic Inference
  Computing the probability of a formula given the probabilities or 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 it includes
many standard inference problems as special cases. In this paper, we propose
two algorithms for this problem: formula decomposition and conditioning, which
is an exact method, and formula importance sampling, which is an approximate
method. The latter is, to our knowledge, the first application of model
counting to approximate probabilistic inference. Unlike conventional
variable-based algorithms, our algorithms work in the dual realm of logical
formulas. Theoretically, we show that our algorithms can greatly improve
efficiency by exploiting the structural information in the formulas.
Empirically, we show that they are indeed quite powerful, often achieving
substantial performance gains over state-of-the-art schemes.
