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: