Abstract
Lifted message passing approaches can be extremely fast at computing approximate marginal probability distributions over single variables and neighboring ones in the underlying graphical model. They do, however, not prescribe a way to solve more complex inference tasks such as computing joint marginals for k-tuples of distant random variables or satisfying assignments of CNFs. A popular solution in these cases is the idea of turning the complex inference task into a sequence of simpler ones by selecting and clamping variables one at a time and running lifted message passing again after each selection. This naive solution, however, recomputes the lifted network in each step from scratch, therefore often canceling the benefits of lifted inference. We show how to avoid this by efficiently computing the lifted network for each conditioning directly from the one already known for the single node marginals. Our experiments show that significant efficiency gains are possible for lifted message passing guided decimation for SAT and sampling.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Acar, U., Ihler, A., Mettu, R., Sumer, O.: Adaptive inference on general graphical models. In: Proc. of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI 2008). AUAI Press, Corvallis (2008)
Braunstein, A., Mézard, M., Zecchina, R.: Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms 27(2), 201–226 (2005)
Delcher, A.L., Grove, A.J., Kasif, S., Pearl, J.: Logarithmic-time updates and queries in probabilistic networks. JAIR 4, 37–59 (1996)
Gomes, C.P., Hoffmann, J., Sabharwal, A., Selman, B.: From sampling to model counting. In: 20th IJCAI, Hyderabad, India, pp. 2293–2299 (January 2007)
Ihler, A.T., Fisher III, J.W., Willsky, A.S.: Loopy belief propagation: Convergence and effects of message errors. JMLR 6, 905–936 (2005)
Kersting, K., Ahmadi, B., Natarajan, S.: Counting belief propagation. In: Proc. of the 25th Conf. on Uncertainty in AI (UAI 2009), Montreal, Canada (2009)
Kschischang, F.R., Frey, B.J., Loeliger, H.-A.: Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory 47 (2001)
Mezard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Inc., New York (2009)
Milch, B., Zettlemoyer, L., Kersting, K., Haimes, M., Pack Kaelbling, L.: Lifted Probabilistic Inference with Counting Formulas. In: Proc. of the 23rd AAAI Conf. on Artificial Intelligence, AAAI 2008 (July 13–17, 2008)
Montanari, A., Ricci-Tersenghi, F., Semerjian, G.: Solving constraint satisfaction problems through belief propagation-guided decimation. In: Proc. of the 45th Allerton Conference on Communications, Control and Computing (2007)
Nath, A., Domingos, P.: Efficient lifting for online probabilistic inference. In: Proceedings of the Twenty-Fourth AAAI Conference on AI, AAAI 2010 (2010)
Pearl, J.: Reasoning in Intelligent Systems: Networks of Plausible Inference, 2nd edn. Morgan Kaufmann, San Francisco (1991)
Richardson, M., Domingos, P.: Markov Logic Networks. MLJ 62, 107–136 (2006)
Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 521–532 (1995)
Sen, P., Deshpande, A., Getoor, L.: Bisimulation-based approximate lifted inference. In: Proc. of the 25th Conf. on Uncertainty in AI, UAI 2009 (2009)
Singla, P., Domingos, P.: Lifted First-Order Belief Propagation. In: Proc. of the 23rd AAAI Conf. on AI (AAAI 2008), pp. 1094–1099 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hadiji, F., Ahmadi, B., Kersting, K. (2011). Efficient Sequential Clamping for Lifted Message Passing. In: Bach, J., Edelkamp, S. (eds) KI 2011: Advances in Artificial Intelligence. KI 2011. Lecture Notes in Computer Science(), vol 7006. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24455-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-24455-1_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24454-4
Online ISBN: 978-3-642-24455-1
eBook Packages: Computer ScienceComputer Science (R0)