Exact Bayesian Structure Discovery in Bayesian Networks

By Mikko Koivisto, Kismat Sood. Journal of machine learning research, 2004

516 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/507c9b4917638d77b0bad5df47edff92f2ff229a

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

DiBS: Differentiable Bayesian Structure Learning (2021, methodology): “Exact methods A few notable exceptions use dynamic programming to achieve exact marginal inference in time O(d2), which is only feasible for d ≤ 20 nodes [43, 44].”
Learning Bayesian networks: approaches and issues (2011, methodology): “At around the same time, Koivisto and Sood (2004) came up with a very similar procedure, but with a somewhat more in-depth analysis of the problem.”
Bayesian structure learning using dynamic programming and MCMC (2007, methodology): “Recently a dynamic programming (DP) algorithm has been devised by Koivisto and Sood (11; 10) which can sum over all possible orderings analytically, and thus exactly compute p(Gij = 1|D) for all edges in O(d2) time.”
Partition MCMC for Inference on Acyclic Digraphs (2015, methodology): “For smaller systems, space and time complexity are such that an efficient option is given by dynamic programming (Koivisto and Sood, 2004), which can also be used to extend the proposals of standard structure MCMC in a hybrid method (Eaton and Murphy, 2007b).”
Advances in Exact Bayesian Structure Discovery in Bayesian Networks (2006, methodology): “Below we elaborate on some recent results on the so called truncated Möbius transforms (Koivisto and Sood, 2004).”
Learning linear cyclic causal models with latent variables (2012, methodology): “) For GH, we calculated the marginal edge probabilities over all DAG structures (with an in-degree bound of 3) using the dynamic programming algorithm of Koivisto and Sood (2004), thus obtaining a score for the confidence in each possible edge.”
Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networks (2019, result): “As opposed to the previous two works, Eaton and Murphy [19] assume that intervention targets are not known a priori, and propose to learn both targets and causal graph using the dynamic programming approach of Koivisto and Sood [20].”
A Simple Approach for Finding the Globally Optimal Bayesian Network Structure (2006, methodology): “Inspired by Koivisto & Sood (2004), we set ourselves to implement an exact Bayesian network structure discovery for complete discrete data.”
A survey of Bayesian Network structure learning (2021, methodology): “Dynamic programming was an early technique used in exact algorithms (Koivisto and Sood, 2004; Ott et al., 2004) searching in node-ordering space.”
Belief net structure learning from uncertain interventions (2007, methodology): “H I(H(i, j) = 1)p(H|D) (13) We can compute GCMAP 3 and p(Gij = 1|D, F = I, θ1 = δ) exactly4 using dynamic programming (DP) in O(d2d) time and space (Koivisto and Sood, 2004; Koivisto, 2006; Silander and Myllmaki, 2006; Singh and Moore, 2005).”
Towards Scalable Bayesian Learning of Causal DAGs (2020, background): “Hence, the currently existing and provably accurate algorithms are feasible only with up to around 25 variables [14, 39, 37, 31], and algorithms with somewhat looser accuracy guarantees to several dozens of variables [20].”
Joint Causal Inference from Multiple Contexts (2016, methodology): “, 1995; Zhang, 2008), score-based causal discovery methods (e.g., Heckerman et al., 1995; Chickering, 2002; Koivisto and Sood, 2004), and methods exploiting other statistical patterns in the joint distribution (e.”
On Structure Priors for Learning Bayesian Networks (2019, background): “When averaged over all orderings it results in a prior that is not modular but order-modular (Koivisto and Sood 2004). The prior stems from the idea of “fair” allocation of probability mass to different numbers of parents, whence the name. Apparently, Fair has rarely been included in empirical studi”
Learning the Structure of Deep Sparse Graphical Models (2009, background): “…[2006], Elidan et al. [2000], Friedman [1998], Ramachandran and Mooney [1998]), most previous work on learning the structure of belief networks has focused on the case where all units are observed [Buntine, 1991, Friedman and Koller, 2003, Heckerman et al., 1995, Koivisto and Sood, 2004].”
Structure Discovery in Bayesian Networks by Sampling Partial Orders (2016, methodology): “For comparison purposes, we also computed exact values of these quantities on the Flare, German, and Mushroom data sets using the algorithms of Koivisto and Sood (2004; 2006) and Tian and He (2009).”
The max-min hill-climbing Bayesian network structure learning algorithm (2006, methodology): “Recently an exact algorithm has been proposed that is guaranteed to identify the most probable a posteriori network (even for finite sample size) (Kovisto and Sood, 2004).”