nips nips2013 nips2013-122 nips2013-122-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nima Taghipour, Jesse Davis, Hendrik Blockeel
Abstract: Lifting attempts to speedup probabilistic inference by exploiting symmetries in the model. Exact lifted inference methods, like their propositional counterparts, work by recursively decomposing the model and the problem. In the propositional case, there exist formal structures, such as decomposition trees (dtrees), that represent such a decomposition and allow us to determine the complexity of inference a priori. However, there is currently no equivalent structure nor analogous complexity results for lifted inference. In this paper, we introduce FO-dtrees, which upgrade propositional dtrees to the first-order level. We show how these trees can characterize a lifted inference solution for a probabilistic logical model (in terms of a sequence of lifted operations), and make a theoretical analysis of the complexity of lifted inference in terms of the novel notion of lifted width for the tree. 1
[1] F. Bacchus, S. Dalmao, and T. Pitassi. Solving #-SAT and Bayesian inference with backtracking search. Journal of Artificial Intelligence Research, 34(2):391, 2009.
[2] Adnan Darwiche. Recursive conditioning. Artif. Intell., 126(1-2):5–41, 2001.
[3] Rodrigo de Salvo Braz, Eyal Amir, and Dan Roth. Lifted first-order probabilistic inference. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 1319–1325, 2005.
[4] Rina Dechter. Bucket elimination: A unifying framework for reasoning. Artif. Intell., 113(1-2):41–85, 1999.
[5] Lise Getoor and Ben Taskar, editors. An Introduction to Statistical Relational Learning. MIT Press, 2007.
[6] Vibhav Gogate and Pedro Domingos. Probabilistic theorem proving. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI), pages 256–265, 2011.
[7] Manfred Jaeger and Guy Van den Broeck. Liftability of probabilistic inference: Upper and lower bounds. In Proceedings of the 2nd International Workshop on Statistical Relational AI (StaRAI), 2012.
[8] Abhay Jha, Vibhav Gogate, Alexandra Meliou, and Dan Suciu. Lifted inference seen from the other side : The tractable features. In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS), pages 973–981. 2010.
[9] Kristian Kersting, Babak Ahmadi, and Sriraam Natarajan. Counting belief propagation. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pages 277–284, 2009.
[10] Brian Milch, Luke S. Zettlemoyer, Kristian Kersting, Michael Haimes, and Leslie Pack Kaelbling. Lifted probabilistic inference with counting formulas. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pages 1062–1608, 2008.
[11] Mathias Niepert. Markov chains on orbits of permutation groups. In Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI), pages 624–633, 2012.
[12] David Poole. First-order probabilistic inference. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pages 985–991, 2003.
[13] David Poole, Fahiem Bacchus, and Jacek Kisynski. Towards completely lifted search-based probabilistic inference. CoRR, abs/1107.4035, 2011.
[14] David Poole and Nevin Lianwen Zhang. Exploiting contextual independence in probabilistic inference. J. Artif. Intell. Res. (JAIR), 18:263–313, 2003.
[15] Parag Singla and Pedro Domingos. Lifted first-order belief propagation. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pages 1094–1099, 2008.
[16] Nima Taghipour and Jesse Davis. Generalized counting for lifted variable elimination. In Proceedings of the 2nd International Workshop on Statistical Relational AI (StaRAI), 2012.
[17] Nima Taghipour, Daan Fierens, Jesse Davis, and Hendrik Blockeel. Lifted variable elimination with arbitrary constraints. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1194–1202, 2012.
[18] Nima Taghipour, Daan Fierens, Guy Van den Broeck, Jesse Davis, and Hendrik Blockeel. Completeness results for lifted variable elimination. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS), 2013.
[19] Guy Van den Broeck. On the completeness of first-order knowledge compilation for lifted probabilistic inference. In Proceedings of the 24th Annual Conference on Advances in Neural Information Processing Systems (NIPS), pages 1386–1394, 2011.
[20] Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Lifted relax, compensate and then recover: From approximate to exact lifted probabilistic inference. In Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI), pages 131–141, 2012.
[21] Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, and Luc De Raedt. Lifted probabilistic inference by first-order knowledge compilation. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 2178–2185, 2011.
[22] Deepak Venugopal and Vibhav Gogate. On lifting the gibbs sampling algorithm. In Proceedings of the 26th Annual Conference on Advances in Neural Information Processing Systems (NIPS), pages 1–6, 2012. 9