Sound and Efficient Inference with Probabilistic and Deterministic Dependencies
Reasoning with both probabilistic and deterministic dependencies
is important for many real-world problems, and in
particular for the emerging field of statistical relational learning.
However, probabilistic inference methods like MCMC
or belief propagation tend to give poor results when deterministic
or near-deterministic dependencies are present, and
logical ones like satisfiability testing are inapplicable to probabilistic
ones. In this paper we propose MC-SAT, an inference
algorithm that combines ideas from MCMC and satisfiability.
MC-SAT is based on Markov logic, which defines
Markov networks using weighted clauses in first-order logic.
From the point of view ofMCMC,MC-SAT is a slice sampler
with an auxiliary variable per clause, and with a satisfiabilitybased
method for sampling the original variables given the
auxiliary ones. From the point of view of satisfiability, MCSAT
wraps a procedure around the SampleSAT uniform sampler
that enables it to sample from highly non-uniform distributions
over satisfying assignments. Experiments on entity
resolution and collective classification problems show that
MC-SAT greatly outperforms Gibbs sampling and simulated
tempering over a broad range of problem sizes and degrees of