《The Max Min Hill Climbing Bayesian Network Structure Learning Algorithm》.pdf

Mach Learn (2006) 65:31–78 DOI 10.1007/s10994-006-6889-7 The max-min hill-climbing Bayesian network structure learning algorithm Ioannis Tsamardinos · Laura E. Brown · Constantin F. Aliferis Received: January 07, 2005 / Revised: December 21, 2005 / Accepted: December 22, 2005 / Published online: 28 March 2006 Springer Science + Business Media, LLC 2006 Abstract We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC out- performs on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical re- sults simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at /supplements/mmhc paper/mmhc index.html. Keywords Bayesian networks · Graphical models · Structure learning 1. Introduction A Bayesian network is a mathematical construct that compactly represents a joint probability distribution P among a set variables V . Bayesian networks are frequently employed for modeling domain knowledge in Decision Support Systems, particularly in medicine (Beinlich et al., 1989; Cowell et al., 1999; Andreassen et al., 1989). Editor: Andrew W. Moore I. Tsamardinos · L. E. Brown ()· C. F. Aliferis Discovery Systems Laboratory, D