Improving High-Dimensional Bayesian Network Structure Learning by Exploiting Search Space Information

Bayesian networks are frequently used to model statistical dependencies in data. Without prior knowledge of dependencies in the data, the structure of a Bayesian network is learned from the data. Bayesian network structure learning is commonly posed as an optimization problem where search is used to find structures that maximize a scoring function. Since the structure search space is superexponential in the number of variables in a network, heuristics are applied to constrain the search space of high-dimensional networks. Greedy hill climbing is then applied in the reduced search space. The constrained search space of high-dimensional networks contains many local maxima that greedy hill climbing cannot overcome. This issue has only been addressed by augmenting greedy search with TABU lists or random moves. This is not a holistic solution to the problem. By using a search algorithm that is global in nature, we are not confined to results in a particular region of the search space, like previous approaches. We present Model-Based Search (MBS) [1] applied to Bayesian network structure learning. MBS uses information gained during search to explore promising search space regions. Maintaining this search space information keeps a global view of the search task and helps find structures at higher maxima than greedy hill climbing. We show that MBS performs better than hill climbing in the Max-Min Parents and Children (MMPC) [30] search space and can find better high-dimensional network structures than other leading structure learning algorithms.