Bayesian Structure Learning by Recursive Bootstrap
We address the problem of Bayesian structure learning for domains with hundreds of variables by employing non-parametric bootstrap, recursively. We propose a method that covers both model averaging and model selection in the same framework. The proposed method deals with the main weakness of constraint-based learning-sensitivity to errors in the independence tests-by a novel way of combining bootstrap with constraint-based learning. Essentially, we provide an algorithm for learning a tree, in which each node represents a scored CPDAG for a subset of variables and the level of the node corresponds to the maximal order of conditional independencies that are encoded in the graph. As higher order independencies are tested in deeper recursive calls, they benefit from more bootstrap samples, and therefore are more resistant to the curse-of-dimensionality. Moreover, the re-use of stable low order independencies allows greater computational efficiency. We also provide an algorithm for sampling CPDAGs efficiently from their posterior given the learned tree. That is, not from the full posterior, but from a reduced space of CPDAGs encoded in the learned tree. We empirically demonstrate that the proposed algorithm scales well to hundreds of variables, and learns better MAP models and more reliable causal relationships between variables, than other state-of-the-art-methods.
This manuscript proposes B-RAI, an extension of the Recursive Autonomy Identification (RAI) algorithm of Yehezkel & Lerner (JMLR, 2009), which is itself a constraint-based algorithm for Bayesian network structure learning. The idea of B-RAI is to use bootstrapping within each each RAI-substep in order to create a space of possible CDPAG (BN equivalence classes) solutions, for each of which a score is computed. So B-RAI belongs  actually to the class of hybrids between constraint-based and score-based structure learning. The proposed approach has the advantage to cover both model averaging and model selection in the same framework.  In summary, this is interesting work that could be useful to other researchers. The studied problem is important, and the results of benchmark studies look promising. The manuscript is generally written well.   I have a few comments/questions, though:  [1] The difference of B-RAI to RAI could be stated more explicitly early on (end of intro). Within Section 3, it is not easy to see where description of the old method ends and where the novel content starts. I had to look in the JMLR paper from 2009 to clarify some aspects.  [2] The article employs BDeu as scoring function, but does not fully specify the prior: What is the chosen equivalent sample size (ESS)? This information is essential for reproducing the results.  [3] If I understand correctly, the algorithm does not sample CPDAGs from the (full) posterior, but samples only CPDAGs that survive initial independence tests (and are thus included in the graph generating tree) according to their posterior probability. If this is so, it could be stated more explicitly, especially in the abstract.  [4] For the model selection part, I miss a comparison with the globally optimal (CP)-DAG according to BDeu (with same ESS, see comment [2]) for the problem sizes (Child, Insurance, Mildew, Alarm, perhaps also Barley) where it can be computed with modern solvers (e.g. GOBNILP, CPBayes, URLearn).   [5] For the model selection I also miss an evaluation of the solution's quality in terms of structural similarity to the ground-truth (measured by structural Hamming distance, for instance). It might be a more informative criterion than the log probability of MAP models, which is pretty hard to interpret (is a difference small or large?).  [6] Very minor stylistic comments regarding the reference list: Please be consistent in using either full conference names or abbreviations (one "IJCAI" appears), and use of initial caps in paper/journal/conference titles. "Bayesian" instead of "bayesian", etc.  [7] Another presentation issue: In Fig. 4, showing both the barplots and the numbers is a bit redundant. If the precise numbers are really important, a plain table might be a better way to present the results. Otherwise one could add a y-axis just to the leftmost plots (which then pertains to the entire row).  ################## After rebuttal:  Thank you for the detailed response, in particular clarifying [5]. Perhaps it's possible to add some result pertaining [4] to the final version [if completed until then], although it is not that critical, just a nice-to-have.