A General Method for Reducing the Complexity of Relational Inference And its Application to MCMC

Hoifung Poon and Pedro Domingos and Marc Sumner

Abstract:

Many real-world problems are characterized by complex relational structure, which can be succinctly represented in firstorder logic. However, many relational inference algorithms proceed by first fully instantiating the first-order theory and then working at the propositional level. The applicability of such approaches is severely limited by the exponential time and memory cost of propositionalization. Singla and Domingos (2006) addressed this by developing a âlazyâ version of the WalkSAT algorithm, which grounds atoms and clauses only as needed. In this paper we generalize their ideas to a much broader class of algorithms, including other types of SAT solvers and probabilistic inference methods likeMCMC. Lazy inference is potentially applicable whenever variables and functions have default values (i.e., a value that is much more frequent than the others). In relational domains, the default is false for atoms and true for clauses. We illustrate our framework by applying it to MC-SAT, a state-of-the-art MCMC algorithm. Experiments on a number of real-world domains show that lazy inference reduces both space and time by several orders of magnitude, making probabilistic relational inference applicable in previously infeasible domains.

Download:

Paper (PDF)

MLNs used:

Datasets used: