Sound and Efficient Inference with Probabilistic and Deterministic Dependencies

Abstract

Reasoning with both probabilistic and deterministic depen-dencies is important for many real-world problems, and in particular for the emerging field of statistical relational learn-ing. However, probabilistic inference methods like MCMC or belief propagation tend to give poor results when deter-ministic or near-deterministic dependencies are present, and logical ones like satisfiability testing are inapplicable to prob-abilistic ones. In this paper we propose MC-SAT, an infer-ence algorithm that combines ideas from MCMC and satis-fiability. MC-SAT is based on Markov logic, which defines Markov networks using weighted clauses in first-order logic. From the point of view of MCMC,MC-SAT is a slice sampler with an auxiliary variable per clause, and with a satisfiability-based method for sampling the original variables given the auxiliary ones. From the point of view of satisfiability, MC-SAT wraps a procedure around the SampleSAT uniform sam-pler that enables it to sample from highly non-uniform distri-butions 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 determinism.