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.

本文提出了精确算法和近似算法，以及相应的公式分解和条件概率以及基于模型计数的概率推断方法，并展示了其在实验中的实际有效性，特别是相比于最先进方案，本文提出的算法可以利用公式结构信息大大提高效率。