Finding Optimal Bayesian Networks

Abstract

In this paper, we derive optimality results for greedy Bayesian-network search algorithms that perform single-edge modifications at each step and use asymptotically consistent scoring criteria. Our results extend those of Meek (1997) and Chickering (2002), who demonstrate that in the limit of large datasets, if the generative distribution is perfect with respect to a DAG defined over the observable variables, such search algorithms will identify this optimal (i.e. generative) DAG model. We relax their assumption about the generative distribution, and assume only that this distribution satisfies the {em composition property} over the observable variables, which is a more realistic assumption for real domains. Under this assumption, we guarantee that the search algorithms identify an {em inclusion-optimal} model; that is, a model that (1) contains the generative distribution and (2) has no sub-model that contains this distribution. In addition, we show that the composition property is guaranteed to hold whenever the dependence relationships in the generative distribution can be characterized by paths between singleton elements in some generative graphical model (e.g. a DAG, a chain graph, or a Markov network) even when the generative model includes unobserved variables, and even when the observed data is subject to selection bias.

Appears in Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI2002)

References in corpus (2)

• A Transformational Characterization of Equivalent Bayesian Network Structures
• Finding a Path is Harder than Finding a Tree

Cited by in corpus (24)

• D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
• Bayesian structure learning using dynamic programming and MCMC
• Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
• On Local Optima in Learning Bayesian Networks
• Learning AMP Chain Graphs under Faithfulness
• Learning big Gaussian Bayesian networks: partition, estimation, and fusion
• Learning Factor Graphs in Polynomial Time & Sample Complexity
• Evaluating Causal Models by Comparing Interventional Distributions
• Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations
• Learning Inclusion-Optimal Chordal Graphs
• Estimating a Causal Order among Groups of Variables in Linear Models
• Identifiability Assumptions and Algorithm for Directed Graphical Models with Feedback
• Practically Perfect
• Detecting Data Errors with Statistical Constraints
• Efficient Bayesian network structure learning via local Markov boundary search
• Learning AMP Chain Graphs and some Marginal Models Thereof under Faithfulness: Extended Version
• Solving All Regression Models For Learning Gaussian Networks Using Givens Rotations
• Every LWF and AMP chain graph originates from a set of causal models
• Finding Consensus Bayesian Network Structures
• Finding links and initiators: a graph reconstruction problem
• Reading Dependencies from Polytree-Like Bayesian Networks
• A Note on the Estimation Method of Intervention Effects based on Statistical Decision Theory
• A Ladder of Causal Distances
• Learning Class-Level Bayes Nets for Relational Data