A Delayed Column Generation Strategy for Exact k-Bounded MAP Inference in Markov Logic Networks

Mathias Niepert
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:383-390, 2010.

Abstract

The paper introduces k-bounded MAP infer- ence, a parameterization of MAP inference in Markov logic networks. k-Bounded MAP states are MAP states with at most k ac- tive ground atoms of hidden (non-evidence) predicates. We present a novel delayed col- umn generation algorithm and provide em- pirical evidence that the algorithm efficiently computes k-bounded MAP states for mean- ingful real-world graph matching problems. The underlying idea is that, instead of solv- ing one large optimization problem, it is often more efficient to tackle several small ones.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-niepert10a, title = {A Delayed Column Generation Strategy for Exact k-Bounded {MAP} Inference in {M}arkov Logic Networks}, author = {Niepert, Mathias}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {383--390}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/niepert10a/niepert10a.pdf}, url = {https://proceedings.mlr.press/r8/niepert10a.html}, abstract = {The paper introduces k-bounded MAP infer- ence, a parameterization of MAP inference in Markov logic networks. k-Bounded MAP states are MAP states with at most k ac- tive ground atoms of hidden (non-evidence) predicates. We present a novel delayed col- umn generation algorithm and provide em- pirical evidence that the algorithm efficiently computes k-bounded MAP states for mean- ingful real-world graph matching problems. The underlying idea is that, instead of solv- ing one large optimization problem, it is often more efficient to tackle several small ones.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Delayed Column Generation Strategy for Exact k-Bounded MAP Inference in Markov Logic Networks %A Mathias Niepert %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-niepert10a %I PMLR %P 383--390 %U https://proceedings.mlr.press/r8/niepert10a.html %V R8 %X The paper introduces k-bounded MAP infer- ence, a parameterization of MAP inference in Markov logic networks. k-Bounded MAP states are MAP states with at most k ac- tive ground atoms of hidden (non-evidence) predicates. We present a novel delayed col- umn generation algorithm and provide em- pirical evidence that the algorithm efficiently computes k-bounded MAP states for mean- ingful real-world graph matching problems. The underlying idea is that, instead of solv- ing one large optimization problem, it is often more efficient to tackle several small ones. %Z Reissued by PMLR on 04 October 2026.
APA
Niepert, M.. (2010). A Delayed Column Generation Strategy for Exact k-Bounded MAP Inference in Markov Logic Networks. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:383-390 Available from https://proceedings.mlr.press/r8/niepert10a.html. Reissued by PMLR on 04 October 2026.

Related Material