jmlr jmlr2011 jmlr2011-30 jmlr2011-30-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Cassio P. de Campos, Qiang Ji
Abstract: This paper addresses the problem of learning Bayesian network structures from data based on score functions that are decomposable. It describes properties that strongly reduce the time and memory costs of many known methods without losing global optimality guarantees. These properties are derived for different score criteria such as Minimum Description Length (or Bayesian Information Criterion), Akaike Information Criterion and Bayesian Dirichlet Criterion. Then a branch-andbound algorithm is presented that integrates structural constraints with data in a way to guarantee global optimality. As an example, structural constraints are used to map the problem of structure learning in Dynamic Bayesian networks into a corresponding augmented Bayesian network. Finally, we show empirically the benefits of using the properties with state-of-the-art methods and with the new algorithm, which is able to handle larger data sets than before. Keywords: Bayesian networks, structure learning, properties of decomposable scores, structural constraints, branch-and-bound technique
H. Akaike. A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19(6):716–723, 1974. D. L. Applegate, R. E. Bixby, V. Chv´ tal, and W. J. Cook. The Traveling Salesman Problem: A a Computational Study. Princeton Univ. Press, 2006. A. Asuncion and D.J. Newman. UCI machine learning repository, 2007. URL http://www.ics. uci.edu/˜mlearn/MLRepository.html. R. Bouckaert. Properties of Bayesian belief network learning algorithms. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence, UAI’94, pages 102–109, San Francisco, CA, 1994. Morgan Kaufmann. 687 DE C AMPOS AND J I W. Buntine. Theory refinement on Bayesian networks. In Proceedings of the 8th Annual Conference on Uncertainty in Artificial Intelligence, UAI’92, pages 52–60, San Francisco, CA, 1991. Morgan Kaufmann. D. M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507–554, 2002. D. M. Chickering, C. Meek, and D. Heckerman. Large-sample learning of Bayesian networks is np-hard. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence, UAI’03, pages 124–13, San Francisco, CA, 2003. Morgan Kaufmann. G. F. Cooper and E. Herskovits. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309–347, 1992. C. P. de Campos, Z. Zeng, and Q. Ji. Structure learning of Bayesian networks using constraints. In Proceedings of the 26th International Conference on Machine Learning, ICML’09, pages 113– 120, Montreal, 2009. Omnipress. D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning, 20:197–243, 1995. T. Jaakkola, D. Sontag, A. Globerson, and M. Meila. Learning Bayesian Network Structure using LP Relaxations. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, AISTATS’10, pages 358–365, 2010. M. Koivisto. Advances in exact Bayesian structure discovery in Bayesian networks. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, UAI’06, pages 241–248. AUAI Press, 2006. M. Koivisto and K. Sood. Exact Bayesian Structure Discovery in Bayesian Networks. Journal of Machine Learning Research, 5:549–573, 2004. K. Kojima, E. Perrier, S. Imoto, and S. Miyano. Optimal search on clustered structural constraint for learning Bayesian network structure. Journal of Machine Learning Research, 11:285–310, 2010. S. Ott and S. Miyano. Finding optimal gene networks using biological constraints. Genome Informatics, 14:124–133, 2003. P. Parviainen and M. Koivisto. Exact structure discovery in Bayesian networks with less space. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI’09, pages 436–443, Arlington, Virginia, United States, 2009. AUAI Press. F. Pernkopf and J. Bilmes. Discriminative versus generative parameter and structure learning of Bayesian network classifiers. In Proceedings of the 22nd International Conference on Machine Learning, ICML’05, pages 657–664, New York, NY, USA, 2005. ACM. E. Perrier, S. Imoto, and S. Miyano. Finding optimal Bayesian network given a super-structure. Journal of Machine Learning Research, 9:2251–2286, 2008. 688 E FFICIENT S TRUCTURE L EARNING OF BAYESIAN N ETS G. Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6(2):461–464, 1978. T. Silander and P. Myllymaki. A simple approach for finding the globally optimal Bayesian network structure. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, UAI’06, pages 445–452, Arlington, Virginia, 2006. AUAI Press. A. P. Singh and A. W. Moore. Finding optimal Bayesian networks by dynamic programming. Technical report, Carnegie Mellon University, 2005. CMU-CALD-05-106. P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction and Search. Springer-Verlag, New York, 1993. J. Suzuki. Learning Bayesian belief networks based on the minimum description length principle: An efficient algorithm using the B&B; technique. In Proceedings of the 13th International Conference on Machine Learning, ICML’96, pages 462–470, 1996. M. Teyssier and D. Koller. Ordering-based search: A simple and effective algorithm for learning Bayesian networks. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, UAI’05, pages 584–590, 2005. I. Tsamardinos, L. E. Brown, and C. Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65(1):31–78, 2006. 689