How matroids occur in the context of learning Bayesian network structure

Milan Studeny Inst. Info. Theory and Autom.
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:318-327, 2015.

Abstract

In this paper we show that any connected matroid having a non-trivial cluster of BN variables as its ground set induces a facet-defining inequality for the polytope(s) used in the ILP approach to optimal BN structure learning. Our result applies to well-known k-cluster inequalities, which play a crucial role in the ILP approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-autom-15a, title = {How matroids occur in the context of learning {B}ayesian network structure}, author = {Autom., Milan Studeny Inst. Info. Theory and}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {318--327}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/autom-15a/autom-15a.pdf}, url = {https://proceedings.mlr.press/r13/autom-15a.html}, abstract = {In this paper we show that any connected matroid having a non-trivial cluster of BN variables as its ground set induces a facet-defining inequality for the polytope(s) used in the ILP approach to optimal BN structure learning. Our result applies to well-known k-cluster inequalities, which play a crucial role in the ILP approach.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T How matroids occur in the context of learning Bayesian network structure %A Milan Studeny Inst. Info. Theory and Autom. %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-autom-15a %I PMLR %P 318--327 %U https://proceedings.mlr.press/r13/autom-15a.html %V R13 %X In this paper we show that any connected matroid having a non-trivial cluster of BN variables as its ground set induces a facet-defining inequality for the polytope(s) used in the ILP approach to optimal BN structure learning. Our result applies to well-known k-cluster inequalities, which play a crucial role in the ILP approach. %Z Reissued by PMLR on 04 October 2026.
APA
Autom., M.S.I.I.T.a.. (2015). How matroids occur in the context of learning Bayesian network structure. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:318-327 Available from https://proceedings.mlr.press/r13/autom-15a.html. Reissued by PMLR on 04 October 2026.

Related Material