Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm

By Nir Friedman, Iftach Nachman, Dana Pe'er. 1999

Learning Bayesian networks is often cast as an optimization problem, where the computational task is to find a structure that maximizes a statistically motivated score. By and large, existing learning tools address this optimization problem using standard heuristic search techniques. Since the search space is extremely large, such search procedures can spend most of the time examining candidates that are extremely unreasonable. This problem becomes critical when we deal with data sets that are large either in the number of instances, or the number of attributes. In this paper. we introduce an algorithm that achieves faster learning by restricting the search space. This iterative algorithm restricts the parents of each variable to belong to a small subset of candidates. We then search for a network that satisfies these constraints. The learned network is then used for selecting better candidates for the next iteration. We evaluate this algorithm both on synthetic and real-life data. Our results show that it is significantly faster than alternative search procedures without loss of quality in the learned structures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

High-dimensional consistency in score-based and hybrid structure learning (2015, methodology): “Such methods often use a greedy search on a restricted search space in order to achieve computational efficiency, where the restricted space is estimated using conditional independence tests [Friedman et al., 1999; Tsamardinos et al., 2006; Schmidt et al., 2007; Schulte et al., 2010; Alonso-Barba et”
Causal Feature Selection (2007, methodology): “A causal discovery method is then run on the reduced set of potential causes to reflne the causal structure [ 10 ].”
Graphical models of protein–protein interaction specificity from correlated mutations and interaction data (2009, result): “This greedy procedure is analogous to the procedure we have previously developed to capture constraints on a single protein family12 and is similar in spirit to the ‘‘sparse candidate’’ algorithm of Friedman et al.31 This algorithm has the advantage of being applicable to both the table-count and pe”
Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part I: Algorithms and Empirical Evaluation (2010, methodology): “We note that SCA has greatly different inductive bias from the GLL variants and thus the comparison (provided that the causal generative model is a Bayesian network) is not unduly biased toward them, while still allowing induction of a credible causal graphical model.”
Learning Causal Bayesian Network Structures From Experimental Data (2008, methodology): “Our Bootstrap implementation follows as closely as possible (Friedman, Nachman and Pe´er 1999) though we employ the same eﬃcient scoring and database mechanisms as our Order-Graph sampler to ensure fair comparisons between running time and other performance metrics.”
Learning Bayesian networks: approaches and issues (2011, methodology): “Early confidence measuring research by Friedman et al. (1999a, 1999b) used the Bootstrap in order to find a degree of reliability of certain features in the learned DAG, for example, the existence of an edge, the Markov blanket of a node or the ordering of variables.”
Learning Probabilistic Relational Models (1999, background): “Following [Friedman et al., 1999], which examines a similar approach in the context of learning Bayesian networks, we propose an iterative approach that starts with some structure (possibly one where each attribute does not have any parents), and select the sets PotU !”
Temporal causal modeling with graphical granger methods (2007, methodology): “In this paper, we examine a host of related algorithms that, loosely speaking, fall under the category of graphical Granger methods, and characterize their relative performance from multiple viewpoints.”
Graphical Models of Residue Coupling in Protein Families (2008, methodology): “is zero, then it is easy to see that the removal of j and its incident edges must separate i and k in the unknown network N. This assessment is made in the context of a prior graph G = (V,E), where we assume V = V and E E. This approach is akin to the ‘sparse candidate’ algorithm [ 8 ] for learning ”
Sparse graphical Gaussian modeling of the isoprenoid gene network in Arabidopsis thaliana (2004, background): “Some of these problems may be circumvented by restricting the number of possible models or edges [10,13] or by exploiting prior knowledge on the network structure.”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “For continuous multivariate Gaussian data, the inverse Wishart prior leads to the BGe score (Geiger and Heckerman, 2002; corrected in Kuipers et al., 2014).”
The max-min hill-climbing Bayesian network structure learning algorithm (2006, background): “Keywords Bayesian networks · Graphical models · Structure learning”
Scaling-Up Bayesian Network Learning to Thousands of Variables Using Local Learning Techniques (2003, methodology): “The orientation phase of the PC algorithm or a constrained hill-climbing searchand-score in the fashion of the Sparse Candidate [3] can then be used for edge orientation.”