Probabilistic Theorem Proving

Communications of the ACM

Many representation schemes combining first-order logic and probability have been proposed in recent years. Progress in unifying logical and probabilistic inference has been slower. Existing methods are mainly variants of lifted variable elimination and belief propagation, neither of which take logical structure into account. We propose the first method that has the full power of both graphical model inference and first-order theorem proving (in finite domains with Herbrand interpretations). We first define probabilistic theorem proving (PTP), their generalization, as the problem of computing the probability of a logical formula given the probabilities or weights of a set of formulas.

On the Completeness of First-Order Knowledge Compilation for Lifted Probabilistic Inference

Neural Information Processing Systems

Probabilistic logics are receiving a lot of attention today because of their expressive power for knowledge representation and learning. However, this expressivity is detrimental to the tractability of inference, when done at the propositional level. To solve this problem, various lifted inference algorithms have been proposed that reason at the first-order level, about groups of objects as a whole. Despite the existence of various lifted inference approaches, there are currently no completeness results about these algorithms. The key contribution of this paper is that we introduce a formal definition of lifted inference that allows us to reason about the completeness of lifted inference algorithms relative to a particular class of probabilistic models. We then show how to obtain a completeness result using a first-order knowledge compilation approach for theories of formulae containing up to two logical variables.

A Deeper Empirical Analysis of CBP Algorithm: Grounding Is the Bottleneck

AAAI Conferences

In this work-in-progress, we consider a lifted inference algorithm and analyze its scaling properties. We compare two versions of this algorithm – the original implementation and a newer implementation built on a database. Our preliminary results show that constructing the factor graph from the relational model ratherthan the construction of the compressed model is thekey bottleneck for the application of lifted inference in large domains.

Lifted Generative Parameter Learning

AAAI Conferences

Statistical relational learning (SRL) augments probabilistic models with relational representations and facilitates reasoning over sets of objects. When learning the probabilistic parameters for SRL models, however, one often resorts to reasoning over individual objects. To address this challenge, we compile a Markov logic network into a compact and efficient first-order data structure and use weighted first-order model counting to exactly optimize the likelihood of the parameters in a lifted manner. By exploiting the relational structure in the model, it is possible to learn more accurate parameters and dramatically improve the run time of the likelihood calculation. This allows us to calculate the exact likelihood for models where previously only approximate inference was feasible. Results on real-world data sets show that this approach learns more accurate models.

Lifted Inference Seen from the Other Side : The Tractable Features

Neural Information Processing Systems

Lifted inference algorithms for representations that combine first-order logic and probabilistic graphical models have been the focus of much recent research. All lifted algorithms developed to date are based on the same underlying idea: take a standard probabilistic inference algorithm (e.g., variable elimination, belief propagation etc.) and improve its efficiency by exploiting repeated structure in the first-order model. In this paper, we propose an approach from the other side in that we use techniques from logic for probabilistic inference. In particular, we define a set of rules that look only at the logical representation to identify models for which exact efficient inference is possible. We show that our rules yield several new tractable classes that cannot be solved efficiently by any of the existing techniques.