Bayesian structure learning using dynamic programming and MCMC

By Daniel Eaton, Kevin P. Murphy. 2007

140 citations recorded by the source corpus.

MCMC methods for sampling from the space of DAGs can mix poorly due to the local nature of the proposals that are commonly used. It has been shown that sampling from the space of node orders yields better results [FK03, EW06]. Recently, Koivisto and Sood showed how one can analytically marginalize over orders using dynamic programming (DP) [KS04, Koi06]. Their method computes the exact marginal posterior edge probabilities, thus avoiding the need for MCMC. Unfortunately, there are four drawbacks to the DP technique: it can only use modular priors, it can only compute posteriors over modular features, it is difficult to compute a predictive density, and it takes exponential time and space. We show how to overcome the first three of these problems by using the DP algorithm as a proposal distribution for MCMC in DAG space. We show that this hybrid technique converges to the posterior faster than other methods, resulting in more accurate structure learning and higher predictive likelihoods on test data.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Bayesian Structure Learning with Generative Flow Networks (2022, methodology): “Although a molecular intervention may be imperfect and affect multiple proteins (Eaton and Murphy, 2007b), we assume here that these interventions are perfect, and the intervention targets are known.”
Learning Neural Causal Models from Unknown Interventions (2019, methodology): “Eaton & Murphy (2007b) use dynamic programming techniques to accelerate Markov Chain Monte Carlo (MCMC) sampling in a Bayesian approach to structure learning for discrete variable DAGs.”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, neutral): “Many bootstrap (Friedman et al., 1999) and sampling-based structure learning algorithms (Madigan et al., 1995; Friedman & Koller, 2003; Eaton & Murphy, 2012; Grzegorczyk & Husmeier, 2008; Niinim¨aki & Koivisto, 2013; Niinimaki et al., 2012; He et al., 2016) are also proposed to tackle the expensive…”
Learning Bayesian networks: approaches and issues (2011, methodology): “More recently, Eaton and Murphy (2007a) demonstrate a method that utilizes MCMC and dynamic programming (as in Section 4.11) in model averaging.”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, background): “However, the potential for uncovering the mechanisms underlying scientiﬁc phenomena in disciplines ranging from the social sciences (Elwert, 2013) to biology (Friedman et al., 2000; Friedman, 2004; Kuipers et al., 2018) has driven interest in DAG inference.”
Structure Discovery in Bayesian Networks by Sampling Partial Orders (2016, methodology): “Also other refinements to Madigan and York’s sampler have been presented (Eaton and Murphy, 2007; Grzegorczyk and Husmeier, 2008; Corander et al., 2008), however with somewhat more limited advantages over orderMCMC.”
A survey of Bayesian Network structure learning (2021, methodology): “Eaton and Murphy (2007) therefore proposed a Hybrid MCMC algorithm that uses an exact score-based algorithm, Dynamic Programming (see subsection 3.3.1), to develop a global proposal distribution.”
Automatic model construction with Gaussian processes (2014, background): “For example, graphical model learning algorithms (Eaton and Murphy, 2007; Friedman and Koller, 2003) search over different connectivity graphs for a given set of nodes.”
Prediction for Traffic Accident Severity: Comparing the Bayesian Network and Regression Models (2013, methodology): “The structure of the severity prediction Bayesian network is learned by employing the K2 algorithm and the Full-BNT toolbox, which is an open-sourceMatlab package for directed graphical models [16].”
DiBS: Differentiable Bayesian Structure Learning (2021, background): “Attempts to correct for its unintended structural bias are themselves NP-hard to compute and/or limit the parent size [38, 41].”