A Simple Approach for Finding the Globally Optimal Bayesian Network Structure

By Tomi Silander, Petri Myllymäki. Conference on Uncertainty in Artificial Intelligence, 2006

413 citations recorded by the source corpus.

We study the problem of learning the best Bayesian network structure with respect to a decomposable score such as BDe, BIC or AIC. This problem is known to be NP-hard, which means that solving it becomes quickly infeasible as the number of variables increases. Nevertheless, in this paper we show that it is possible to learn the best Bayesian network structure with over 30 variables, which covers many practically interesting cases. Our algorithm is less complicated and more efficient than the techniques presented earlier. It can be easily parallelized, and offers a possibility for efficient exploration of the best networks consistent with different variable orderings. In the experimental part of the paper we compare the performance of the algorithm to the previous state-of-the-art algorithm. Free source-code and an online-demo can be found at http://b-course.hiit.fi/bene.

Subfields: Artificial Intelligence

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

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

Citations in the corpus

Causal feature learning: an overview (2017, neutral): “These are either based on the independence structure of the generative distributions (Spirtes et al. 2000; Chickering 2002; Silander and Myllymäki 2006; Claassen and Heskes 2012; Hyttinen et al. 2014) or assumptions about the functional form of the structural equations that govern the system…”
$\ell_0$-penalized maximum likelihood for sparse directed acyclic graphs (2012, methodology): “…feasible algorithm for exact ℓ 0 - penalized maximum likelihood estimation for the Markov equivalence class of DAGs has been proposed by Silander and Myllym¨aki (2006); for larger graphs, with more than about 20 nodes, approximate algorithms can be used [Chickering (2002), Hauser and…”
Learning Bayesian networks: approaches and issues (2011, methodology): “This procedure is again approached in a different manner by Silander and Myllymäki (2006) who present a less complicated algorithm that is feasible for structures of”
Belief net structure learning from uncertain interventions (2007, methodology): “The exact method uses the dynamic programming algorithm of (Silander and Myllmaki, 2006); the 15”
MAXIMUM LIKELIHOOD FOR SPARSE DIRECTED ACYCLIC GRAPHS (2013, methodology): “For problems with up to about p ≈ 20 nodes, dynamic programming can be used [Silander and Myllymäki (2006)], while for large-scale applications, greedy equivalent search has been reported to perform well [Chickering (2002), Hauser and Bühlmann (2012)].”
A survey of Bayesian Network structure learning (2021, background): “Singh and Moore (2005) and Silander and Myllymaki (2006) applied this paradigm to structure learning using the insight that every DAG must have at least one sink node (a node with no children, also referred to as a leaf node).”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “Many exact and approximate algorithms for learning DAG from data have been developed, including score-based and constraint-based approaches (Spirtes et al., 2000a; Chicker-ing, 2002; Koivisto & Sood, 2004; Silander & Myllymaki, 2006; Jaakkola et al., 2010; Cussens, 2011; Yuan & Malone, 2013).”
Efficient Structure Learning of Bayesian Networks using Constraints (2011, methodology): “, 2006; Silander and Myllymaki, 2006; Parviainen and Koivisto, 2009; de Campos e t al., 2009; Jaakkola et al., 2010), mostly focused on complete data. In this case, best exact ide s (where it is guaranteed to find the global best scoring structure) are based on dynamic prog ramming (Koivisto and Soo”
Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, methodology): “Furthermore, for p ≤ 20, we compare with a dynamic programming (DP) approach proposed by Silander and Myllym¨aki (2006), an algorithm that ﬁnds a global optimum of any decomposable score function on the space of DAGs.”
Bayesian network learning with cutting planes (2011, methodology): “One approach is to use dynamic programming [10, 12, 5] which has successfully been used for exact learning up to around 30 vertices.”
Machine Learning of Bayesian Networks Using Constraint Programming (2015, methodology): “This insight is used by Silander and Myllymäki [5] in their dynamic programming approach and by Fan et al.”
Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs (2013, methodology): “Somewhat surprisingly, although the optimization problem in (14) is NP-hard (Chickering, 1996), dynamic programming can be used for exhaustive optimization (Silander and Myllym¨aki, 2006), roughly as long as p is less than say 20.”
High-dimensional learning of linear causal networks via inverse covariance estimation (2013, methodology): “Some methods include exhaustive search (Silander and Myllymaki, 2006), greedy methods (Chickering, 2002), and dynamic programming (Ordyniak and Szeider, 2012; Korhonen and Parviainen, 2013).”
Structure Learning in Graphical Modeling (2016, background): “Silander & Myllym¨aki (2006) propose an elegant dynamic programming approach.”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, methodology): “Notwithstanding, there are algorithms for solving (4) to global optimality for small problems (Ott and Miyano, 2003; Singh and Moore, 2005; Silander and Myllymaki, 2006; Xiang and Kim, 2013; Cussens, 2012; Cussens et al., 2017).”
Bayesian Networks for Variable Groups (2015, background): “Although the problem is NP-hard (Chickering, 1996), there exist plenty of exact algorithms (Jaakkola et al., 2010; Silander and Myllymäki, 2006) as well as theoretically sound heuristics (Aliferis et al., 2010; Chickering, 2002).”
Modeling Discrete Interventional Data using Directed Cyclic Graphical Models (2009, methodology): “We used the projected quasi-Newton method of Schmidt et al. (2009) to optimize the criteria for a given ordering, and used the dynamic programming algorithm of Silander and Myllymaki (2006) to minimize the regularized negative loglikelihood over all possible node orderings.”