Being Bayesian about Network Structure

By Nir Friedman, Daphne Koller. Conference on Uncertainty in Artificial Intelligence, 2000

353 citations recorded by the source corpus.

In many domains, we are interested in analyzing the structure of the underlying distribution, e.g., whether one variable is a direct parent of the other. Bayesian model-selection attempts to find the MAP model and use its structure to answer these questions. However, when the amount of available data is modest, there might be many models that have non-negligible posterior. Thus, we want compute the Bayesian posterior of a feature, i.e., the total posterior probability of all models that contain it. In this paper, we propose a new approach for this task. We first show how to efficiently compute a sum over the exponential number of networks that are consistent with a fixed ordering over network variables. This allows us to compute, for a given ordering, both the marginal probability of the data and the posterior of a feature. We then use this result as the basis for an algorithm that approximates the Bayesian posterior of a feature. Our approach uses an Markov Chain Monte Carlo (MCMC) method, but over orderings rather than over network structures. The space of orderings is much smaller and more regular than the space of structures, and has a smoother posterior "landscape". We present empirical results on synthetic and real-life datasets that compare our approach to full model averaging (when possible), to MCMC over network structures, and to a non-Bayesian bootstrap approach.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/66c138148d9fa3ad9528e91d5924ee1d304257c6

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 Statistical and Nonlinear Physics

Citations in the corpus

Structure and strength in causal induction. (2005, neutral): “Bayesian structure learning proceeds by either searching the space of structures to find that with the highest posterior probability (Friedman, 1997; Heckerman, 1998), or evaluating particular causal relationships by integrating over the posterior distribution over graphs (Friedman & Koller, 2000).”
Bayesian models of cognition (2008, background): “For example, we could estimate how likely it is that one variable A causes variable B in a complex causal network of unknown structure, by computing the probability that a link A → B exists in a high-probability sample from the posterior over network structures (Friedman & Koller, 2000).”
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].”
Addendum on the scoring of Gaussian directed acyclic graphical models (2014, background): “Order MCMC [Friedman and Koller (2003), on the related space of triangular matrices] as well as the edge reversal move of Grzegorczyk and Husmeier (2008) would not be possible without it.”
On Inclusion-Driven Learning of Bayesian Networks (2003, background): “…some algorithms assume that a causal ordering between the variables is known (Cooper and Herskovits, 1992), or they search for a good causal ordering that may help in providing later a better result (Bouckaert, 1992, Singh and Valtorta, 1993, Larra˜naga et al., 1996, Friedman and Koller, 2000).”
Leveraging Domain Knowledge in Multitask Bayesian Network Structure Learning (2012, background): “The search space of Bayesian network structures is characterized by large basins of approximately equivalent solutions (Friedman and Koller 2003).”
BAYESIAN HIERARCHICAL MODELING FOR SIGNALING PATHWAY INFERENCE FROM SINGLE CELL INTERVENTIONAL DATA (2011, methodology): “More recently, Ellis and Wong (2008) proposed a method to reduce the bias in the fast mixing algorithm proposed by Friedman and Killer (2003) to sample the BN structures from the posterior distribution.”
Intuitive theories as grammars for causal inference (2007, background): “(11) The sum over all possible networks in Equation 11 may be computed exactly for very small systems, but in general requires some kind of stochastic sampling-based approximation scheme (e.g., Friedman & Koller, 2000).”
Using Bayesian Networks to Analyze Expression Data (2000, neutral): “In addition, simulation studies by Friedman and Koller (2000) show that the con dence values computed by the bootstrap, although not equal to the Bayesian posterior, correlate well with estimates of the Bayesian posterior for features.”
Gaussian Process Networks (2000, background): “We present empirical results on artificial data as well as on real-life domains with non-linear dependencies.”
Learning Bayesian networks: approaches and issues (2011, methodology): “To score an ordering they used the work of Friedman and Koller (2000, 2003) who showed how to efficiently score an ordering in closed form, where each node has a bounded number of parents.”