nips nips2013 nips2013-151 nips2013-151-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jukka Corander, Tomi Janhunen, Jussi Rintanen, Henrik Nyman, Johan Pensar
Abstract: We investigate the problem of learning the structure of a Markov network from data. It is shown that the structure of such networks can be described in terms of constraints which enables the use of existing solver technology with optimization capabilities to compute optimal networks starting from initial scores computed from the data. To achieve efficient encodings, we develop a novel characterization of Markov network structure using a balancing condition on the separators between cliques forming the network. The resulting translations into propositional satisfiability and its extensions such as maximum satisfiability, satisfiability modulo theories, and answer set programming, enable us to prove optimal certain networks which have been previously found by stochastic search. 1
[1] J. N. Darroch, Steffen L. Lauritzen, and T. P. Speed. Markov fields and log-linear interaction models for contingency tables. The Annals of Statistics, 8:522–539, 1980.
[2] Steffen L. Lauritzen and Nanny Wermuth. Graphical models for associations between variables, some of which are qualitative and some quantitative. The Annals of Statistics, 17:31–57, 1989.
[3] Jukka Corander. Bayesian graphical model determination using decision theory. Journal of Multivariate Analysis, 85:253–266, 2003.
[4] Jukka Corander, Magnus Ekdahl, and Timo Koski. Parallel interacting MCMC for learning of topologies of graphical models. Data Mining and Knowledge Discovery, 17:431–456, 2008.
[5] Petros Dellaportas and Jonathan J. Forster. Markov chain Monte Carlo model determination for hierarchical and graphical log-linear models. Biometrika, 86:615–633, 1999.
[6] Paolo Giudici and Robert Castello. Improving Markov chain Monte Carlo model search for data mining. Machine Learning, 50:127–158, 2003.
[7] Paolo Giudici and Peter J. Green. Decomposable graphical Gaussian model determination. Biometrika, 86:785–801, 1999.
[8] Mikko Koivisto and Kismat Sood. Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 5:549–573, 2004.
[9] David Madigan and Adrian E. Raftery. Model selection and accounting for model uncertainty in graphical models using Occam’s window. Journal of the American Statistical Association, 89:1535–1546, 1994. 8
[10] Stephen Della Pietra, Vincent Della Pietra, and John Lafferty. Inducing features of random fields. IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(4):380–393, 1997.
[11] Su-In Lee, Varun Ganapathi, and Daphne Koller. Efficient structure learning of Markov networks using L1 -regularization. In Advances in Neural Information Processing Systems 19, pages 817–824. MIT Press, 2006.
[12] M. Schmidt, A. Niculescu-Mizil, and K. Murphy. Learning graphical model structure using L1 -regularization paths. In Proceedings of the National Conference on Artificial Intelligence, page 1278. AAAI Press / MIT Press, 2007.
[13] Holger H¨ fling and Robert Tibshirani. Estimation of sparse binary pairwise Markov networks o using pseudo-likelihoods. Journal of Machine Learning Research, 10:883–906, 2009.
[14] Armin Biere, Marijn J. H. Heule, Hans van Maaren, and Toby Walsh, editors. Handbook of Satisfiability. IOS Press, 2009.
[15] Chu Min Li and Felip Many` . MaxSAT, Hard and Soft Constraints, chapter 19, pages 613–631. a In Biere et al. [14], 2009.
[16] Clark Barrett, Roberto Sebastiani, Sanjit A. Seshia, and Cesare Tinelli. Satisfiability Modulo Theories, chapter 26, pages 825–885. In Biere et al. [14], 2009.
[17] Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. Answer set programming at a glance. Commun. ACM, 54(12):92–103, 2011.
[18] Joe Whittaker. Graphical Models in Applied Multivariate Statistics. Wiley Publishing, 1990.
[19] Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, 1980.
[20] Ronald L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43–57, 1985.
[21] Yukio Shibata. On the tree representation of chordal graphs. Journal of Graph Theory, 12(3):421–428, 1988.
[22] Finn V. Jensen and Frank Jensen. Optimal junction trees. In Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI-94), pages 360–366, 1994.
[23] Carsten Sinz. Towards an optimal CNF encoding of Boolean cardinality constraints. In Principles and Practice of Constraint Programming – CP 2005, number 3709 in Lecture Notes in Computer Science, pages 827–831. Springer-Verlag, 2005.
[24] Daniel Le Berre and Anne Parrain. The Sat4j library, release 2.2 system description. Journal on Satisfiability, Boolean Modeling and Computation, 7:59–64, 2010.
[25] Ruben Martins, Vasco Manquinho, and Inˆ s Lynce. Parallel search for maximum satisfiability. e AI Communications, 25:75–95, 2012.
[26] Roberto Sebastiani and Silvia Tomasi. Optimization in SMT with LA(Q) cost functions. In Automated Reasoning, volume 7364 of LNCS, pages 484–498. Springer-Verlag, 2012.
[27] Martin Gebser, Benjamin Kaufmann, and Torsten Schaub. Conflict-driven answer set solving: From theory to practice. Artif. Intell., 187:52–89, 2012.
[28] Martin Gebser, Benjamin Kaufmann, Ram´ n Otero, Javier Romero, Torsten. Schaub, and o Philipp Wanko. Domain-specific heuristics in answer set programming. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press, 2013.
[29] Tomi Janhunen and Ilkka Niemel¨ . Compact translations of non-disjunctive answer set proa grams to propositional clauses. In Gelfond Festschrift, Vol. 6565 of LNCS, pages 111–130. Springer-Verlag, 2011.
[30] James Cussens. Bayesian network learning by compiling to weighted MAX-SAT. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 105–112, 2008.
[31] James Cussens. Bayesian network learning with cutting planes. In Proceedings of the TwentySeventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11), pages 153–160. AUAI Press, 2011.
[32] Mark Bartlett and James Cussens. Advances in Bayesian network learning using integer programming. In Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013), pages 182–191. AUAI Press, 2013. 9