M. Studeny:
How matroids occur in the context of learning Bayesian network structure.
In Uncertainty in Artificial Intelligence.
Proceedings of the 31th Conference
(M. Meila, T. Heskes eds.), AUAI Press, Corvallis 2015, pp. 832-841.
- Abstract
-
It is shown 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 globally optimal BN structure learning.
The result applies to well-known k-cluster inequalities,
which play a crucial role in the ILP approach.
- AMS classification 68T30 52B40 68T05
- Keywords
- learning Bayesian network structure
- integer linear programming
- imset
- matroid
- extreme supermodular function
- A
pdf version (144kB) is available.
The contribution builds on the following papers:
- M. Bartlett, J. Cussens:
Advances in Bayesian network learning using integer programming.
In Uncertainty in Artificial Intelligence. Proceedings of the
29th Conference (A. Nicholson, P. Smyth eds.),
AUAI Press, Corvallis 2013, pp. 182-191.
- H. Q. Nguyen:
Semimodular functions and combinatorial geometries.
Transaction of the American Mathematical Society
238 (1978), pp. 355-383.
- J. Cussens, M. Studeny, D. Haws:
Polyhedral aspects of score equivalence in Bayesian network structure learning.
To appear in Mathematical Programming A (November 2016).