2006 SoundandEfficientInferencewithP

• (Poon & Domingos, 2006) ⇒ Hoifung Poon, and Pedro Domingos. (2006). “ Sound and Efficient Inference with Probabilistic and Deterministic Dependencies.” In: Proceedings of the 21st national conference on Artificial intelligence. AAAI 2006. ISBN:978-1-57735-281-5

Subject Headings: MC-SAT Algorithm.

Cited By

• http://scholar.google.com/scholar?q=%222006%22+Sound+and+Efficient+Inference+with+Probabilistic+and+Deterministic+Dependencies
• http://dl.acm.org/citation.cfm?id=1597538.1597612&preflayout=flat#citedby

Quotes

Abstract

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 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, 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 determinism.

Figures

.

---

---

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2006 SoundandEfficientInferencewithP	Pedro Domingos Hoifung Poon			Sound and Efficient Inference with Probabilistic and Deterministic Dependencies						2006