Structure learning of Bayesian networks using constraints

ABSTRACT

This paper addresses exact learning of Bayesian network structure from data and expert's knowledge based on score functions that are decomposable. First, it describes useful properties that strongly reduce the time and memory costs of many known methods such as hill-climbing, dynamic programming and sampling variable orderings. Secondly, a branch and bound algorithm is presented that integrates parameter and structural constraints with data in a way to guarantee global optimality with respect to the score function. It is an any-time procedure because, if stopped, it provides the best current solution and an estimation about how far it is from the global solution. We show empirically the advantages of the properties and the constraints, and the applicability of the algorithm to large data sets (up to one hundred variables) that cannot be handled by other current methods (limited to around 30 variables).

REFERENCES

• 1: Asuncion, A., & Newman, D. (2007). UCI machine learning repository. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 2: Ernesto G. Birgin , José Mario Martínez , Marcos Raydan, Nonmonotone Spectral Projected Gradient Methods on Convex Sets, SIAM Journal on Optimization, v.10 n.4, p.1196-1211, 2000 [doi>10.1137/S1052623497330963]
• 3: Bouckaert, R. (1994). Properties of bayesian belief network learning algorithms. Conf. on Uncertainty in Artificial Intelligence (pp. 102--109). M. Kaufmann.
• 4: Chickering, D., Meek, C., & Heckerman, D. (2003). Large-sample learning of bayesian networks is np-hard. Conf. on Uncertainty in Artificial Intelligence (pp. 124--13). M. Kaufmann.
• 5: David Maxwell Chickering, Optimal structure identification with greedy search, The Journal of Machine Learning Research, 3, p.507-554, 3/1/2003 [doi>10.1162/153244303321897717]
• 6: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 7: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 8: Koivisto, M. (2006). Advances in exact bayesian structure discovery in bayesian networks. Conf. on Uncertainty in Artificial Intelligence (pp. 241--248) AUAI Press.
• 9: Mikko Koivisto , Kismat Sood, Exact Bayesian Structure Discovery in Bayesian Networks, The Journal of Machine Learning Research, 5, p.549-573, 12/1/2004
• 10: Silander, T., & Myllymaki, P. (2006). A simple approach for finding the globally optimal bayesian network structure. Conf. on Uncertainty in Artificial Intelligence. (pp. 445--452) AUAI Press.
• 11: Singh, A. P., & Moore, A. W. (2005). Finding optimal bayesian networks by dynamic programming (Technical Report). Carnegie Mellon Univ. CALD-05-106.
• 12: Suzuki, J. (1996). Learning bayesian belief networks based on the minimum description length principle: An efficient algorithm using the B&B technique. Int. Conf. on Machine Learning (pp. 462--470).
• 13: Teyssier, M., & Koller, D. (2005). Ordering-based search: A simple and effective algorithm for learning bayesian networks. Conf. on Uncertainty in Artificial Intelligence. (pp. 584--590) AUAI Press.
• 14: Ioannis Tsamardinos , Laura E. Brown , Constantin F. Aliferis, The max-min hill-climbing Bayesian network structure learning algorithm, Machine Learning, v.65 n.1, p.31-78, October 2006 [doi>10.1007/s10994-006-6889-7]
• 15: M. P. Wellman, Fundamental concepts of qualitative probabilistic networks, Artificial Intelligence, v.44 n.3, p.257-303, Aug. 1990 [doi>10.1016/0004-3702(90)90026-V]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory