More Web Proxy on the site http://driver.im/

Article

Fast lifted MAP inference via partitioning

Authors:

Somdeb Sarkhel,

Vibhav GogateAuthors Info & Claims

NIPS'15: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2

Pages 3240 - 3248

Published: 07 December 2015 Publication History

Abstract

Recently, there has been growing interest in lifting MAP inference algorithms for Markov logic networks (MLNs). A key advantage of these lifted algorithms is that they have much smaller computational complexity than propositional algorithms when symmetries are present in the MLN and these symmetries can be detected using lifted inference rules. Unfortunately, lifted inference rules are sound but not complete and can often miss many symmetries. This is problematic because when symmetries cannot be exploited, lifted inference algorithms ground the MLN, and search for solutions in the much larger propositional space. In this paper, we present a novel approach, which cleverly introduces new symmetries at the time of grounding. Our main idea is to partition the ground atoms and force the inference algorithm to treat all atoms in each part as indistinguishable. We show that by systematically and carefully refining (and growing) the partitions, we can build advanced any-time and any-space MAP inference algorithms. Our experiments on several real-world datasets clearly show that our new algorithm is superior to previous approaches and often finds useful symmetries in the search space that existing lifted inference rules are unable to detect.

References

[1]

U. Apsel and R. Braman. Exploiting uniform assignments in first-order MPE. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pages 74-83, 2012.

[2]

U. Apsel, K. Kersting, and M. Mladenov. Lifting Relational MAP-LPs Using Cluster Signatures. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.

Digital Library

[3]

H. Bui, T. Huynh, and S. Riedel. Automorphism groups of graphical models and lifted variational inference. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, 2013.

Digital Library

[4]

R. de Salvo Braz. Lifted First-Order Probabilistic Inference. PhD thesis, University of Illinois, Urbana-Champaign, IL, 2007.

Digital Library

[5]

P. Domingos and D. Lowd. Markov Logic: An Interface Layer for Artificial Intelligence. Morgan & Claypool, 2009.

Digital Library

[6]

V. Gogate and P. Domingos. Probabilistic Theorem Proving. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 256-265. AUAI Press, 2011.

Digital Library

[7]

F. Hadiji and K. Kersting. Reduce and Re-Lift: Bootstrapped Lifted Likelihood Maximization for MAP. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.

Digital Library

[8]

Gurobi Optimization Inc. Gurobi Optimizer Reference Manual, 2014.

[9]

A. Jha, V. Gogate, A. Meliou, and D. Suciu. Lifted Inference from the Other Side: The tractable Features. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems, 2010.

[10]

J. Kisynski and D. Poole. Constraint Processing in Lifted Probabilistic Inference. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 293-302, 2009.

Digital Library

[11]

S. Kok, M. Sumner, M. Richardson, P. Singla, H. Poon, D. Lowd, J. Wang, and P. Domingos. The Alchemy System for Statistical Relational AI. Technical report, Department of Computer Science and Engineering, University of Washington, Seattle, WA, 2008. http://alchemy.cs.washington.edu.

[12]

R. Marinescu and R. Dechter. AND/OR Branch-and-Bound Search for Combinatorial Optimization in Graphical Models. Artificial Intelligence, 173(16-17):1457-1491, 2009.

Digital Library

[13]

H. Mittal, P. Goyal, V. Gogate, and P. Singla. New Rules for Domain Independent Lifted MAP Inference. In Advances in Neural Information Processing Systems, 2014.

[14]

M. Mladenov, A. Globerson, and K. Kersting. Efficient Lifting of MAP LP Relaxations Using k-Locality. Proceedings of the 17th International Conference on Artificial Intelligence and Statistics, 2014.

[15]

F. Niu, C. Ré, A. Doan, and J. Shavlik. Tuffy: Scaling up Statistical Inference in Markov Logic Networks Using an RDBMS. Proceedings of the VLDB Endowment, 2011.

Digital Library

[16]

J. Noessner, M. Niepert, and H. Stuckenschmidt. RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational Models. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.

Digital Library

[17]

D. Poole. First-Order Probabilistic Inference. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pages 985-991, Acapulco, Mexico, 2003. Morgan Kaufmann.

Digital Library

[18]

S. Sarkhel, D. Venugopal, P. Singla, and V. Gogate. An Integer Polynomial Programming Based Framework for Lifted MAP Inference. In Advances in Neural Information Processing Systems, 2014.

[19]

S. Sarkhel, D. Venugopal, P. Singla, and V. Gogate. Lifted MAP inference for Markov Logic Networks. Proceedings of the 17th International Conference on Artificial Intelligence and Statistics, 2014.

[20]

B. Selman, H. Kautz, and B. Cohen. Local Search Strategies for Satisfiability Testing. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. 1996.

[21]

G. Van den Broeck and A. Darwiche. On the Complexity and Approximation of Binary Evidence in Lifted Inference. In Advances in Neural Information Processing Systems, 2013.

[22]

G. Van den Broeck, N. Taghipour, W. Meert, J. Davis, and L. De Raedt. Lifted Probabilistic Inference by First-Order Knowledge Compilation. In Proceedings of the Twenty Second International Joint Conference on Artificial Intelligence, pages 2178-2185, 2011.

Digital Library

[23]

D. Venugopal and V. Gogate. Evidence-based Clustering for Scalable Inference in Markov Logic. In Machine Learning and Knowledge Discovery in Databases. 2014.

Digital Library

Cited By

Habeeb HAnand AMausam MSingla P(2017)Coarse-to-fine lifted MAP inference in computer visionProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171930(4595-4602)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171930
Venugopal DSarkhel SCherry K(2016)Non-parametric domain approximation for scalable Gibbs sampling in MLNsProceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence10.5555/3020948.3021025(745-754)Online publication date: 25-Jun-2016
https://dl.acm.org/doi/10.5555/3020948.3021025

Index Terms

Fast lifted MAP inference via partitioning

Index terms have been assigned to the content through auto-classification.

Recommendations

Lifted symmetry detection and breaking for MAP inference
NIPS'15: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1

Symmetry breaking is a technique for speeding up propositional satisfiability testing by adding constraints to the theory that restrict the search space while preserving satisfiability. In this work, we extend symmetry breaking to the problem of model ...
Lifted tree-reweighted variational inference
UAI'14: Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence

We analyze variational inference for highly symmetric graphical models such as those arising from first-order probabilistic models. We first show that for these graphical models, the tree-reweighted variational objective lends itself to a compact lifted ...
Lifted relational variational inference
UAI'12: Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence

Hybrid continuous-discrete models naturally represent many real-world applications in robotics, finance, and environmental engineering. Inference with large-scale models is challenging because relational structures deteriorate rapidly during inference ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

NIPS'15: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2

December 2015

3626 pages

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 07 December 2015

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Habeeb HAnand AMausam MSingla P(2017)Coarse-to-fine lifted MAP inference in computer visionProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171930(4595-4602)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171930
Venugopal DSarkhel SCherry K(2016)Non-parametric domain approximation for scalable Gibbs sampling in MLNsProceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence10.5555/3020948.3021025(745-754)Online publication date: 25-Jun-2016
https://dl.acm.org/doi/10.5555/3020948.3021025

View Options

View options

Figures

Tables

Media

View Table of Conten