M. Studeny, D. C. Haws:
On polyhedral approximations of polytopes for learning Bayesian networks.
Journal of Algebraic Statistics
4 (2013), pp. 58-91.
- Abstract
-
The motivation for this paper is the geometric approach to
statistical learning Bayesian network (BN) structures.
We review three vector encodings of BN structures.
The first one has been used by Jaakkola et al. (2010)
and also by Cussens (2011), the other two use special integral
vectors formerly introduced, called imsets
(Studeny 2005, 2010). The topic is the comparison of outer polyhedral approximations
of the corresponding polytopes. We show how to transform the inequalities
suggested by Jaakkola et al. into the framework of imsets. The
result of our comparison is the observation that the implicit
polyhedral approximation of the standard imset polytope suggested
in (Studeny, Vomlel 2011) gives a tighter approximation than the (transformed)
explicit polyhedral approximation from (Jaakkola 2010). As a
consequence, we confirm a conjecture from (Studeny, Vomlel 2011) that the above-mentioned
implicit polyhedral approximation of the standard imset polytope is an LP
relaxation of that polytope. In the end, we review recent attempts
to apply the methods of integer programming to learning BN
structures and discuss the task of finding suitable explicit LP
relaxation in the imset-based approach.
- AMS classification 90C10, 68R10, 62H99, 15B36
- Keywords
- Bayesian network structure learning
- integer programming
- standard imset
- characteristic imset
- LP relaxation
- A
pdf version of the published paper (827kB) is available.
The paper builds on results from the following publications:
- J. Cussens (2011)
Bayesian network learning with cutting planes.
In 27th Conference on Uncertainty in Artificial
Intelligence, pages 153-160.
- T. Jaakkola, D. Sontag, A. Globerson, M. Meila (2010)
Learning Bayesian network structure using LP relaxations.
In 3th International Conference on Artificial
Intelligence and Statistics, Chia Laguna Resort, Sardinia,
Italy, pages 358-365.
- M. Studeny (2005). Probabilistic Conditional Independence
Structures. London: Springer-Verlag.
- M. Studeny, J. Vomlel, R. Hemmecke:
Geometric view on learning Bayesian network structures.
International Journal of Approximate Reasoning
51 (2010), n. 5, pp. 578-586.
- M. Studeny, J. Vomlel:
On open questions in the geometric approach to structural
learning Bayesian nets.
International Journal of Approximate Reasoning
52 (2011), n. 5, pp. 627-640.