Scaling Inference for Markov Logic via Dual Decomposition
Authors:
- Feng NiuFNFeng Niu
- Ce ZhangCZCe Zhang
- Christopher ReCRChristopher Re
- Jude ShavlikJSJude Shavlik
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 1032-1037
Abstract
Markov logic is a knowledge-representation language that allows one to specify large graphical models. However, the resulting large graphical models can make inference for Markov logic a computationally challenging problem. Recently, dual decomposition (DD) has become a popular approach for scalable inference on graphical models. We study how to apply DD to scale up inference in Markov logic. A standard approach for DD first partitions a graphical model into multiple tree-structured sub problems. We apply this approach to Markov logic and show that DD can outperform prior inference approaches. Nevertheless, we observe that the standard approach for DD is suboptimal as it does not exploit the rich structure often present in the Markov logic program. Thus, we describe a novel decomposition strategy that partitions a Markov logic program into parts based on its structure. A crucial advantage of our approach is that we can use specialized algorithms for portions of the input problem -- some of which have been studied for decades, e.g., coreference resolution. Empirically, we show that our program-level decomposition approach outperforms both non-decomposition and graphical model-based decomposition approaches to Markov logic inference on several data-mining tasks.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Scaling Inference for Markov Logic via Dual Decomposition2012
- TuffyProceedings of the VLDB Endowment, 2011
- Beyond pairwise energies: Efficient optimization for higher-order MRFs2009
- MRF Optimization via Dual Decomposition: Message-Passing Revisited2007
- Convergent Tree-Reweighted Message Passing for Energy MinimizationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
- Markov logic networksMachine Learning, 2006
- MAP Estimation Via Agreement on Trees: Message-Passing and Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001