A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
We address the problem of learning a sparse Bayesian network structure for continuous 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 lowdimensional 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 algorithm 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 efficiency of A* lasso without significantly compromising the quality of solutions. We demonstrate our approach on data simulated from benchmark Bayesian networks and real data.
This paper introduces a method for finding Bayesian 
      networks for continuous variables in high-dimensional spaces. The paper 
      assumes a Gaussian distribution of any particular random variable when 
      conditioned on its parent nodes. A LASSO objective function is used to 
      construct a sparse set of parent nodes for each random variable, subject 
      to an additional constraint that the resulting structure be an acyclic 
      graph. The network structure constraint is framed as an ordering problem, 
      and an A* search algorithm is proposed which finds a directed acyclic 
      graph which maximizes the LASSO objective function. The LASSO objective 
      function, minus the DAG constraint, is used as an admissible heuristic in 
      the A* search. This search is still not fast enough for graphs with large 
      numbers of nodes, so a method for further pruning the search space is 
      introduced. The paper is written clearly, with clear motivation 
      and sufficient detail for implementation by a third party. The use 
      of the LassoScore for optimization in the dynamic programming algorithm, 
      and using the unconstrained LassoScore as a heuristic function, is clever. 
      The simulation studies adequately show that the approximate version of 
      their algorithm still greatly outperforms conventional greedy approaches, 
      while exhibiting fast runtimes even on large networks of nodes. The 
      performance graphs indicate that even substantial pruning the search graph 
      represents only minimal losses relative to the optimal solution. 
      While the paper describes the process as learning network 
      structure for continuous variables, using a linear regression model with 
      fixed noise error (section 2.1) for the conditional distributions would 
      seem to suggest assuming a network in which each random variable is itself 
      linear Gaussian. Offhand this appears to be a fairly strong assumption; 
      however, as noted in the rebuttal, recovering structure is a difficult 
      problem even in Gaussian networks. The application described in 
      section 3.1 is not very clear, and it is not described how stock price 
      data is represented as a Bayesian network. This reviewer is not familiar 
      with the use of Bayesian networks for stock market analysis, and it is not 
      immediately clear to the uninitiated what sort of model is used, or why 
      stock market data would exhibit a particular network structure. This is 
      addressed by references in the rebuttal, which should be added to section 
      3.1.