Difference between revisions of "2006 SoundandEfficientInferencewithP"

From GM-RKB
Jump to: navigation, search
m (Text replacement - " “" to " “")
m (Text replacement - " Pedro Domingos" to " Pedro Domingos")
 
Line 41: Line 41:
 
* 12. James D. Park, Using Weighted MAX-SAT Engines to Solve MPE, Eighteenth National Conference on Artificial Intelligence, p.682-687, July 28-August 01, 2002, Edmonton, Alberta, Canada
 
* 12. James D. Park, Using Weighted MAX-SAT Engines to Solve MPE, Eighteenth National Conference on Artificial Intelligence, p.682-687, July 28-August 01, 2002, Edmonton, Alberta, Canada
 
* 13. Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
 
* 13. Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
* 14. Matthew Richardson, Pedro Domingos, Markov Logic Networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [https://dx.doi.org/10.1007/s10994-006-5833-1 doi:10.1007/s10994-006-5833-1]
+
* 14. Matthew Richardson, [[Pedro Domingos]], Markov Logic Networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [https://dx.doi.org/10.1007/s10994-006-5833-1 doi:10.1007/s10994-006-5833-1]
 
* 15. Dan Roth, On the Hardness of Approximate Reasoning, Artificial Intelligence, v.82 n.1-2, p.273-302, April 1996 [https://dx.doi.org/10.1016/0004-3702(94)00092-1 doi:10.1016/0004-3702(94)00092-1]
 
* 15. Dan Roth, On the Hardness of Approximate Reasoning, Artificial Intelligence, v.82 n.1-2, p.273-302, April 1996 [https://dx.doi.org/10.1016/0004-3702(94)00092-1 doi:10.1016/0004-3702(94)00092-1]
 
* 16. Selman, B.; Kautz, H.; Cohen, B. 1996. Local Search Strategies for Satisfiability Testing. In <i>Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge</i>. AMS.
 
* 16. Selman, B.; Kautz, H.; Cohen, B. 1996. Local Search Strategies for Satisfiability Testing. In <i>Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge</i>. AMS.
* 17. Parag Singla, Pedro Domingos, Discriminative Training of Markov Logic Networks, Proceedings of the 20th National Conference on Artificial Intelligence, p.868-873, July 09-13, 2005, Pittsburgh, Pennsylvania
+
* 17. Parag Singla, [[Pedro Domingos]], Discriminative Training of Markov Logic Networks, Proceedings of the 20th National Conference on Artificial Intelligence, p.868-873, July 09-13, 2005, Pittsburgh, Pennsylvania
 
* 18. Yedidia, J. S.; Freeman, W. T.; Weiss, Y. 2001. Generalized Belief Propagation. In <i>NIPS-01</i>.
 
* 18. Yedidia, J. S.; Freeman, W. T.; Weiss, Y. 2001. Generalized Belief Propagation. In <i>NIPS-01</i>.
 
* 19. Wei Wei, Jordan Erenrich, Bart Selman, Towards Efficient Sampling: Exploiting Random Walk Strategies, Proceedings of the 19th National Conference on Artifical Intelligence, p.670-676, July 25-29, 2004, San Jose, California
 
* 19. Wei Wei, Jordan Erenrich, Bart Selman, Towards Efficient Sampling: Exploiting Random Walk Strategies, Proceedings of the 19th National Conference on Artifical Intelligence, p.670-676, July 25-29, 2004, San Jose, California

Latest revision as of 05:39, 16 August 2019

Subject Headings: MC-SAT Algorithm.

Notes

Cited By


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

2006 SoundandEfficientInferencewithP Algorithm1.png

References

;

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2006 SoundandEfficientInferencewithPHoifung Poon
Pedro Domingos
Sound and Efficient Inference with Probabilistic and Deterministic Dependencies2006
AuthorHoifung Poon + and Pedro Domingos +
titleSound and Efficient Inference with Probabilistic and Deterministic Dependencies +
year2006 +