Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks

By Marc Teyssier, Daphne Koller. Conference on Uncertainty in Artificial Intelligence, 2005

402 citations recorded by the source corpus.

One of the basic tasks for Bayesian networks (BNs) is that of learning a network structure from data. The BN-learning problem is NP-hard, so the standard solution is heuristic search. Many approaches have been proposed for this task, but only a very small number outperform the baseline of greedy hill-climbing with tabu lists; moreover, many of the proposed algorithms are quite complex and hard to implement. In this paper, we propose a very simple and easy-to-implement method for addressing this task. Our approach is based on the well-known fact that the best network (of bounded in-degree) consistent with a given node ordering can be found very efficiently. We therefore propose a search not over the space of structures, but over the space of orderings, selecting for each ordering the best network consistent with it. This search space is much smaller, makes more global search steps, has a lower branching factor, and avoids costly acyclicity checks. We present results for this algorithm on both synthetic and real data sets, evaluating both the score of the network found and in the running time. We show that ordering-based search outperforms the standard baseline, and is competitive with recent algorithms that are much harder to implement.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/f2cb020146cfa7a49c9eec63db8ac47d7fc8645f

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, background): “There is also a wide literature on approximate algorithms based on order search (Teyssier and Koller, 2005; Schmidt et al., 2007; Scanagatta et al., 2015, 2016), greedy search (Heckerman et al., 1995; Chickering, 2003; Ramsey et al., 2016), and coordinate descent (Fu and Zhou, 2013; Aragam and…”
CAM: Causal Additive Models, high-dimensional order search and penalized regression (2013, methodology): “Our proposed approach for estimation and selection of additive structural equation models is based on the following simple idea which is briefly mentioned and discussed in [35] and [31].”
Learning Bayesian Network Structure using LP Relaxations (2010, methodology): “Significant improvements to these methods were obtained by either searching over equivalence classes of network structures [Chickering, 2002] or casting the search over different orderings of the variables [Friedman & Koller, 2003; Teyssier & Koller, 2005].”
Structure learning in random fields for heart motion abnormality detection (2008, background): “[4] (G ,U ,N) Greedily add features Thin [9] (G ,U/D,Y) MinSpanTree Tree struct [12] (G ,D ,Y) Semi definite program Fan-in [35] (G ,D ,N) Greedy order search Fan-in [14] (G ,D ,N) Greedy DAG search Fan-in [8] (G ,D ,Y) Greedy Equiv Search Fan-in [18] (G ,D ,Y) Dynamic program Exp time/space”
Structured Priors for Structure Learning (2006, methodology): “For very large problems, obtaining even approximate posteriors is beyond our current computational capabilities, but search techniques like those in [Teyssier and Koller, 2005] would no doubt be very useful for approximate MAP estimation.”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “To this end (and analogously to Teyssier and Koller, 2005) we replace the score of each order by the score of the highest scoring DAG in that order To compute the terms on the right we again follow the steps detailed in Appendix A using the Hasse power set representation of the permissible parent…”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, neutral): “PC [223] 1993 constraint yes yes yes no CPDAG CCD [196] 1996 constraint yes yes both no PAG FCI [223] 2000 constraint no yes yes no PAG TPDA [31] 2002 constraint yes yes yes no CPDAG CPC [190] 2006 constraint yes relaxed yes no CPDAG KCL [227] 2007 constraint yes yes yes no CPDAG ION [234] 2008 cons”
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression (2015, methodology): “It follows that for each π ∈ S p , supp( β j ( π )) ⊂ S j ( π ) for each j = 1 , . . . , p . e Recall the objective function deﬁned in (1.3) and the associated estimator (1.5). e The spaces D p [ π ] help give us some intuition into what is going on with the estimator B : Suppose we had oracle knowl”
Machine Learning of Bayesian Networks Using Constraint Programming (2015, methodology): “Larranaga et al. [22] were the first to propose the search space of all permutations and Teyssier and Koller [23] successfully applied it within a local search algorithm.”
BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery (2021, methodology): “approaches sampling over orderings instead of over DAGs [53].”
A survey of Bayesian Network structure learning (2021, methodology): “Searching over a node ordering space offers some potential benefits (Teyssier and Koller, 2005): • ordering-based space has complexity ( log )2 n n which is considerably smaller than 2( ) 2 n for DAG space; • each change to the ordering represents a larger change to the current hypothesis…”
Learning Bayesian networks: approaches and issues (2011, neutral): “Teyssier and Koller (2005) reported results using a true local search algorithm that proceeded by swapping the position of two adjacent variables in an ordering and performing a GS.”
UvA-DARE ( Digital Academic Repository ) Causal Discovery with Continuous Additive Noise Models (2014, neutral): “(The methods do not propose any particular DAG, they treat all DAGs within the class equally.)”
Exploiting compositionality to explore a large space of model structures (2012, background): “There has been much work on structure learning in particular model classes, such as undirected (Lee et al., 2006) and directed (Teyssier and Koller, 2005) graphical models.”
Masked Gradient-Based Causal Structure Learning (2019, background): “Such an idea has been exploited in many ordering based methods where fully-connected DAGs are ﬁrst learned (see, e.g., Teyssier and Koller [34], Peters et al. [25]).”
Sandwiching the marginal likelihood using bidirectional Monte Carlo (2015, background): “It is widely used to compare Gaussian process models (Rasmussen and Williams, 2006) and Bayesian network structures (Teyssier and Koller, 2005), where either closed-form solutions or accurate, tractable approximations are available.”