J. Cussens, D. Haws, M. Studeny:
Polyhedral aspects of score equivalence in Bayesian network structure learning.
Mathematical Programming A
164 (2017), n. 1/2, pp. 285-324.
- Abstract
-
This paper deals with faces and facets of the family-variable polytope and
the characteristic-imset polytope, which are special polytopes used
in integer linear programming approaches to statistically learn Bayesian network structure.
A common form of linear objectives to be maximized in this area leads to
the concept of score equivalence (SE), both for linear objectives and for faces of the
family-variable polytope.
We characterize the linear space of SE objectives and establish a one-to-one
correspondence between SE faces of the family-variable polytope, the faces of
the characteristic-imset polytope, and standardized supermodular
functions. The characterization of SE facets in terms of extremality of the
corresponding supermodular function gives an elegant method to verify whether an inequality
is SE-facet-defining for the family-variable polytope.
We also show that when maximizing an SE objective one can eliminate
linear constraints of the family-variable polytope that correspond to non-SE facets.
However, we show that solely considering SE facets is not enough as a counter-example shows;
one has to consider the linear inequality constraints that correspond to facets of the
characteristic-imset polytope despite the fact that they may not define facets in the family-variable mode.
- AMS classification 52B12 90C27 68Q32
- Keywords
- family-variable polytope
- characteristic-imset polytope
- score equivalent face/facet
- supermodular set function
- A
pdf version of a preprint (415kB) is available. Besides that,
a full-text view-only version of the paper is also available.
The paper builds on results from the following publications:
- J. Cussens:
Bayesian network learning with cutting planes.
In Uncertainty in Artificial Intelligence. Proceedings of the
27th Conference (F. Cozman, A. Pfeffer eds.),
AUAI Press, Corvallis 2011, pp. 153-160.
- 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.
- R. Hemmecke, S. Lindner, M. Studeny:
Characteristic imsets for learning Bayesian network structure.
International Journal of Approximate Reasoning
53 (2012), n. 9, pp. 1336-1349.
- M. Studeny, D. Haws:
Learning Bayesian network structure: towards the essential graph by integer linear programming tools.
International Journal of Approximate Reasoning
55 (2014), pp. 1043-1071.
- G. Orlinskaya (2014)
Linear constraints on standard and characteristic imsets for learning Bayesian network structures.
Diploma thesis, TU Munich.
- T. Jaakkola, D. Sontag, A. Globerson, M. Meila.
Learning Bayesian network structure using LP relaxations.
In JMLR Workshops and Conference Proceedings
9 Proceedings of the 13th International Conference on Artificial Intelligence and Statistics [AISTATS 2010],
(Y.W. Teh, M. Titterington eds.), pp. 358-365.
Moreover, the paper is related to the results presented in the following papers: