A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
Jing Xiang, Se Young Kim · 2013
We address the problem of learning a sparse Bayesian network structure for con-tinuous variables in a high-dimensional space. The constraint that the estimated Bayesian network structure must be a directed acyclic graph (DAG) makes the problem challenging because of the huge search space of network structures. Most previous methods were based on a two-stage approach that prunes the search space in the first stage and then searches for a network structure satisfying the DAG constraint in the second stage. Although this approach is effective in a low-dimensional setting, it is difficult to ensure that the correct network structure is not pruned in the first stage in a high-dimensional setting. In this paper, we propose a single-stage method, called A * lasso, that recovers the optimal sparse Bayesian network structure by solving a single optimization problem with A * search algo-rithm that uses lasso in its scoring system. Our approach substantially improves the computational efficiency of the well-known exact methods based on dynamic programming. We also present a heuristic scheme that further improves the ef-ficiency of A * lasso without significantly compromising the quality of solutions. We demonstrate our approach on data simulated from benchmark Bayesian net-works and real data. 1