You are here

Home » Content

On Polyhedral Approximations of Polytopes for Learning Bayesian Networks

Journal Name:

  • Journal of Algebraic Statistics

Publication Year:

  • 2013

Keywords (Original Language):

Author NameUniversity of Author

AMS Codes:

Bookmark/Search this post with
Abstract (Original Language): 
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. [9] and also by Cussens [4], the other two use special integral vectors formerly introduced, called imsets [18, 20]. 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. [9] 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 [21] gives a tighter approximation than the (transformed) explicit polyhedral approximation from [9]. As a consequence, we confirm a conjecture from [21] 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.
FULL TEXT (PDF): 
PDF icon arastirmax-polyhedral-approximations-polytopes-learning-bayesian-networks.pdf
  • 1
59
92
  • English

REFERENCES

References: 

[1] SA Andersson, D Madigan and MD Perlman. A characterization of Markov equivalence
classes for acyclic digraphs. Annals of Statistics, 25:505–541, 1997.
[2] DM Chickering. Optimal structure identification with greedy search. Journal of Machine
Learning Research, 23:507–554, 2002.
[3] J Cussens. Maximum likelihood pedigree reconstruction using integer programming.
In Workshop on Constraint Based Methods for Bioinformatics, pages 9–19, 2010.
[4] J Cussens. Bayesian network learning with cutting planes. In 27th Conference on
Uncertainty in Artificial Intelligence, pages 153–160, 2011.
[5] C de Campos, Z Zeng and Q Ji. Structure learning Bayesian networks using constraints.
In 26th International Conference on Machine Learning, pages 113–120, 2009.
[6] C de Campos and Q Ji. Efficient structure learning Bayesian networks using constraints.
Journal of Machine Learning Research, 12:663–689, 2011.
[7] E Gawrilow and M Joswig. Polymake: framework for analyzing convex polytopes. In
Polytopes – Combinatorics and Computation (Oberwolfach, 1997), DMV Seminar 29,
Birkh¨auser, 2000.
[8] R Hemmecke, S Lindner and M Studen´y. Characteristic imsets for learning Bayesian
network structure. International Journal of Approximate Reasoning, 53:1336-1349,
2012.
[9] T Jaakkola, D Sontag, A Globerson and M Meila. Learning Bayesian network structure
using LP relaxations. In 13th International Conference on Artificial Intelligence
and Statistics, Chia Laguna Resort, Sardinia, Italy, pages 358–365, 2010.
[10] SL Lauritzen. Graphical Models. Clarendon Press, 1996.
[11] S Lindner. Discrete optimization in machine learning – learning Bayesian network
structures and conditional independence implication. PhD thesis, TU Munich, 2012.
[12] E Miller and B Sturmfels. Combinatorial Commutative Algebra. Springer Verlag, 2005.
[13] RE Neapolitan. Learning Bayesian Networks. Pearson Prentice Hall, 2004.
[14] J Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[15] A Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986.
[16] MStuden´y, RR Bouckaert and T Koˇcka. Extreme supermodular set functions over five
variables. Research report n. 1977, Institute of Information Theory and Automation,
Prague, 2000.
[17] RP Stanley. Enumerative Combinatorics, volume 1. Cambridge Studies in Advanced
Mathematics 49, 1997.
[18] M Studen´y. Probabilistic Conditional Independence Structures. Springer Verlag, 2005.
[19] M Studen´y, J Vomlel and R Hemmecke. A geometric view on learning Bayesian network
structures. International Journal of Approximate Reasoning, 51:578–586, 2010.
[20] M Studen´y, R Hemmecke and S Lindner. Characteristic imset: a simple algebraic
representative of a Bayesian network structure. In 5th European Workshop on Probabilistic
Graphical Models, pages 257–264, 2010.
[21] M Studen´y and J Vomlel. On open questions in the geometric approach to structural
learning Bayesian nets. International Journal of Approximate Reasoning, 52:627–640,
2011.
[22] M Studen´y. LP relaxations and pruning for characteristic imsets. Research report n.
2323, Institute of Information Theory and Automation, Prague, 2012.

Thank you for copying data from http://www.arastirmax.com