MaxSAT-Based Cutting Planes for Learning Graphical Models

详细信息    查看全文

• 作者：Paul Saikko (14)
  Brandon Malone (14)
  Matti J盲rvisalo (14)
  
  14. Helsinki Institute for Information Technology ; Department of Computer Science ; University of Helsinki ; Helsinki ; Finland
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9075
• 期：1
• 页码：347-356
• 全文大小：271 KB
• 参考文献：1. Achterberg, T.: Constrained Integer Programming. Ph.D. Thesis, TU Berlin (2007)
  2. Ansotegui, C, Bonet, ML, Levy, J (2013) SAT-based MaxSAT algorithms. Artificial Intelligence 196: pp. 77-105 i.org/10.1016/j.artint.2013.01.002" target="_blank" title="It opens in new window">CrossRef
  3. Bartlett, M., Cussens, J.: Advances in Bayesian network learning using integer programming. In: Proc. UAI, pp. 182鈥?91. AUAI Press (2013)
  4. de Campos, C.P., Zeng, Z., Ji, Q.: Structure learning of Bayesian networks using constraints. In: Proc. ICML, pp. 113鈥?20. ACM (2009)
  5. Corander, J., Janhunen, T., Rintanen, J., Nyman, H., Pensar, J.: Learning chordal Markov networks by constraint satisfaction. In: Proc. NIPS, pp. 1349鈥?357. Curran Associates, Inc. (2013)
  6. Cussens, J.: Bayesian network learning with cutting planes. In: Proc. UAI, pp. 153鈥?60. AUAI Press (2011)
  7. Cussens, J., Bartlett, M.: GOBNILP 1.4.1 user/developer manual (2013)
  8. Davies, J, Bacchus, F Exploiting the power of mip solvers in maxsat. In: itors">J盲rvisalo, M, Van Gelder, A eds. (2013) Theory and Applications of Satisfiability Testing 鈥?SAT 2013. Springer, Heidelberg, pp. 166-181 i.org/10.1007/978-3-642-39071-5_13" target="_blank" title="It opens in new window">CrossRef
  9. Heckerman, D, Geiger, D, Chickering, DM (1995) Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning 20: pp. 197-243
  10. Jaakkola, T., Sontag, D., Globerson, A., Meila, M.: Learning Bayesian network structure using LP relaxations. In: Proc. AISTATS, pp. 358鈥?65. JMLR.org (2010)
  11. Kangas, K., Niinim盲ki, T., Koivisto, M.: Learning chordal Markov networks by dynamic programming. In: Proc. NIPS, pp. 2357鈥?365. Curran Associates, Inc. (2014)
  12. Koivisto, M., Sood, K.: Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 549鈥?73 (2004)
  13. Li, C.M., Many脿, F.: MaxSAT, hard and soft constraints. In: Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185, chap. 19, pp. 613鈥?31. IOS Press (2009)
  14. Malone, B., Kangas, K., J盲rvisalo, M., Koivisto, M., Myllym盲ki, P.: Predicting the hardness of learning Bayesian networks. In: Proc. AAAI, pp. 1694鈥?700. AAAI Press (2014)
  15. Morgado, A, Heras, F, Liffiton, MH, Planes, J, Marques-Silva, J (2013) Iterative and core-guided MaxSAT solving: a survey and assessment. Constraints 18: pp. 478-534 i.org/10.1007/s10601-013-9146-2" target="_blank" title="It opens in new window">CrossRef
  16. Ott, S, Miyano, S (2003) Finding optimal gene networks using biological constraints. Genome Informatics 14: pp. 124-133
  17. Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc. (1988)
  18. Silander, T., Myllym盲ki, P.: A simple approach for finding the globally optimal Bayesian network structure. In: Proc. UAI, pp. 445鈥?52. AUAI Press (2006)
  19. Yuan, C, Malone, B (2013) Learning optimal Bayesian networks: a shortest path perspective. Journal of Artificial Intelligence Research 48: pp. 23-65
  
• 作者单位：Integration of AI and OR Techniques in Constraint Programming
• 丛书名：978-3-319-18007-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

A way of implementing domain-specific cutting planes in branch-and-cut based Mixed-Integer Programming (MIP) solvers is through solving so-called sub-IPs, solutions of which correspond to the actual cuts. We consider the suitability of using Maximum satisfiability solvers instead of MIP for solving sub-IPs. As a case study, we focus on the problem of learning optimal graphical models, namely, Bayesian and chordal Markov network structures.