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

Hoifung Poon, Pedro Domingos, Marc Sumner

Many real-world problems are characterized by complex relational structure, which can be succinctly represented in first-order 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 like MCMC. 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.

Subjects: 3.4 Probabilistic Reasoning; 15.2 Constraint Satisfaction

Submitted: Apr 14, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.