×

Towards using the chordal graph polytope in learning decomposable models. (English) Zbl 1418.68180

Summary: The motivation for this paper is the integer linear programming approach to learning the structure of a decomposable graphical model. We have chosen to represent decomposable models by means of special zero-one vectors, named characteristic imsets. Our approach leads to the study of a special polytope, defined as the convex hull of all characteristic imsets for chordal graphs, named the chordal graph polytope. In this theoretical paper, we introduce a class of clutter inequalities (valid for the vectors in the polytope) and show that all of them are facet-defining for the polytope. We dare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, we propose a linear programming method to solve the separation problem with these inequalities for the use in a cutting plane approach.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
05C90 Applications of graph theory
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
62H99 Multivariate analysis
90C10 Integer programming

Software:

cdd
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bartlett, M.; Cussens, J., Advances in Bayesian network learning using integer programming, (Nicholson, A.; Smyth, P., Uncertainty in Artificial Intelligence, vol. 29 (2013), AUAI Press), 182-191
[2] Barvinok, A., A Course in Convexity (2002), American Mathematical Society: American Mathematical Society Providence · Zbl 1014.52001
[3] Bouckaert, R. R., Bayesian Belief Networks: From Construction to Evidence (1995), University of Utrecht, PhD thesis
[4] Chickering, D. M., Optimal structure identification with greedy search, J. Mach. Learn. Res., 3, 507-554 (2002) · Zbl 1084.68519
[5] Corander, J.; Janhunen, T.; Rintanen, J.; Nyman, H.; Pensar, J., Learning chordal Markov networks by constraint satisfaction, (Burges, C. J.C.; Bottou, L.; Welling, M.; Ghahramani, Z.; Weiberger, K. Q., Advances in Neural Information Processing Systems, vol. 26 (2013), Curran Associates), 1349-1357
[6] Cowell, R. G.; Dawid, A. P.; Lauritzen, S. L.; Spiegelhalter, D. J., Probabilistic Networks and Expert Systems (1999), Springer: Springer New York · Zbl 0937.68121
[7] Cussens, J., Bayesian network learning with cutting planes, (Cozman, F.; Pfeffer, A., Uncertainty in Artificial Intelligence, vol. 27 (2011), AUAI Press), 153-160
[8] Cussens, J.; Haws, D.; Studený, M., Polyhedral aspects of score equivalence in Bayesian network structure learning, Math. Program. Ser. A, 164, 1, 285-324 (2017) · Zbl 1387.90260
[9] Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J., Combinatorial Structures and Their Applications (1970), Gordon and Breach), 69-87 · Zbl 0268.05019
[10] Fukuda, K., cdd and ccdplus homepage (May 2015)
[11] Giudici, P.; Green, P. J., Decomposable graphical Gaussian model determination, Biometrika, 86, 785-801 (1999) · Zbl 0940.62019
[12] Heckerman, D.; Geiger, D.; Chickering, D. M., Learning Bayesian networks: the combination of knowledge and statistical data, Mach. Learn., 20, 194-243 (1995) · Zbl 0831.68096
[13] Hemmecke, R.; Lindner, S.; Studený, M., Characteristic imsets for learning Bayesian network structure, Int. J. Approx. Reason., 53, 1336-1349 (2012) · Zbl 1281.68183
[14] Jaakkola, T.; Sontag, D.; Globerson, A.; Meila, M., Learning Bayesian network structure using LP relaxations, (Teh, Y. W.; Titterington, M., AISTATS 2010. AISTATS 2010, JMLR Workshop and Conference Proceedings, vol. 9 (2010)), 358-365
[15] Kangas, K.; Niinimäki, T.; Koivisto, M., Learning chordal Markov networks by dynamic programming, (Ghahramani, Z.; Welling, M.; Cortes, C.; Lawrence, N. D.; Weinberger, K. Q., Advances in Neural Information Processing Systems, vol. 27 (2014), Curran Associates), 2357-2365
[16] Lauritzen, S. L., Graphical Models (1996), Clarendon Press: Clarendon Press Oxford · Zbl 0907.62001
[17] Lindner, S., Discrete Optimization in Machine Learning: Learning Bayesian Network Structures and Conditional Independence Implication (2012), TU Munich, PhD thesis
[18] Neapolitan, R. E., Learning Bayesian Networks (2004), Pearson Prentice Hall: Pearson Prentice Hall Upper Saddle River
[19] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufman: Morgan Kaufman San Mateo
[20] Pérez, A.; Blum, C.; Lozano, J. A., Learning maximum weighted \((k + 1)\)-order decomposable graphs by integer linear programming, (van der Gaag, L. C.; Feelders, A. J., PGM 2014. PGM 2014, Lecture Notes in AI, vol. 8754 (2014)), 396-408 · Zbl 1443.68152
[21] Schwarz, G. E., Estimation of the dimension of a model, Ann. Stat., 6, 461-464 (1978) · Zbl 0379.62005
[22] Sesh Kumar, K. S.; Bach, F., Convex relaxations for learning bounded-treewidth decomposable graphs, (Dasgupta, S.; McAlester, D., ICML 2013, vol. 1. ICML 2013, vol. 1, JMLR Workshop and Conference Proceedings, vol. 28 (2013)), 525-533
[23] Spirtes, P.; Glymour, C.; Scheines, R., Causality, Prediction and Search (1993), Springer: Springer New York · Zbl 0806.62001
[24] Studený, M., Probabilistic Conditional Independence Structures (2005), Springer: Springer London · Zbl 1070.62001
[25] Studený, M.; Cussens, J., The chordal graph polytope for learning decomposable models, (Antonucci, A.; Corani, G.; de Campos, C. P., PGM 2016. PGM 2016, JMLR Workshop and Conference Proceedings, vol. 52 (2016)), 499-510
[26] Studený, M.; Haws, D., Learning Bayesian network structure: towards the essential graph by integer linear programming tools, Int. J. Approx. Reason., 55, 1043-1071 (2014) · Zbl 1390.68678
[27] Studený, M.; Haws, D. C., On polyhedral approximations of polytopes for learning Bayesian networks, J. Algebraic Stat., 4, 59-92 (2013) · Zbl 1353.90091
[28] Wolsey, L. A., Integer Programming (1998), John Wiley: John Wiley New York · Zbl 0299.90012
[29] Xiang, Y.; Wong, S. K.M.; Cercone, N., A ‘microscopic’ study of minimum entropy search in learning decomposable Markov networks, Mach. Learn., 26, 1, 65-92 (1997) · Zbl 0866.68088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.