M. Studeny, D. C. Haws: On polyhedral approximations of polytopes for learning Bayesian networks. Journal of Algebraic Statistics 4 (2013), pp. 58-91.

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

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: