Advances in Exact Bayesian Structure Discovery in Bayesian Networks

By Mikko Koivisto. 2006

96 citations recorded by the source corpus.

We consider a Bayesian method for learning the Bayesian network structure from complete data. Recently, Koivisto and Sood (2004) presented an algorithm that for any single edge computes its marginal posterior probability in O(n 2^n) time, where n is the number of attributes; the number of parents per attribute is bounded by a constant. In this paper we show that the posterior probabilities for all the n (n - 1) potential edges can be computed in O(n 2^n) total time. This result is achieved by a forward-backward technique and fast Moebius transform algorithms, which are of independent interest. The resulting speedup by a factor of about n^2 allows us to experimentally study the statistical power of learning moderate-size networks. We report results from a simulation study that covers data sets with 20 to 10,000 records over 5 to 25 discrete attributes

Subfields: Artificial Intelligence, Management Science and Operations Research, Causal Inference & Discovery

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

In Causal Inference & Discovery

Citations in the corpus

Bayesian Structure Learning with Generative Flow Networks (2022, background): “Except in limited settings (Koivisto, 2006; Meilă & Jaakkola, 2006), characterizing a whole distribution over DAGs remains intractable because of its combinatorially large sample space and the complex acyclicity constraint.”
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].”
Binary relevance for multi-label learning: an overview (2018, methodology): “(10) Thereafter, the Bayesian network structure G for all class labels (conditioned on x ) can be learned from e j (1 (cid:2) j (cid:2) q ) using o ﬀ -the-shelf packages [54–56].”
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.”
Efficient Structure Learning of Bayesian Networks using Constraints (2011, background): “…(where it is guaranteed to ﬁnd the global best scoring structure) are based on dynamic programming (Koivisto and Sood, 2004; Singh and Moore, 2005; Koivisto, 2006; Silander and Myllymaki, 2006; Parviainen and Koivisto, 2009), and they spend time and memory proportional to n · 2 n , where n is…”
Learning Bayesian networks: approaches and issues (2011, methodology): “As opposed to the methods of Koivisto and Sood, their algorithm is conceptually simpler and scales better. Perrier et al. (2008) describe a hybrid method that constrains”
Multi-label learning by exploiting label dependency (2010, methodology): “We used the BDAGL (Bayesian DAG learning) package(3), which implemented the dynamic programming-based algorithm for computing the marginal posterior probability of every edge in a Bayesian network [12].”
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).”
Structure Discovery in Bayesian Networks by Sampling Partial Orders (2016, methodology): “The algorithm extends the forward–backward algorithm of Koivisto (2006) to accommodate the partial order constraint.”