Finding Optimal Bayesian Networks

David Maxwell Chickering, Christopher MeekUAI 2002

TL;DR

This paper proves that a common greedy search algorithm (GES) for learning Bayesian networks can reliably find "inclusion-optimal" models, which are models that perfectly represent the data's underlying distribution and have no simpler sub-models that do the same. This is a significant theoretical result because it relaxes previous, stricter assumptions about the data-generating distribution, making the algorithm applicable to a wider range of real-world scenarios, even with hidden variables or selection bias.

What Problem Does This Paper Address?

Learning the structure of Bayesian networks (directed graphical models) from data is a fundamental problem in machine learning and artificial intelligence. Bayesian networks are powerful tools for representing probabilistic relationships between variables. However, finding the "best" network structure is computationally challenging, often falling into NP-hard categories. Consequently, researchers frequently rely on heuristic search algorithms, with greedy approaches being particularly popular due to their simplicity and practical effectiveness.

Previous theoretical work showed that certain greedy search algorithms could find the "parameter-optimal" model (the most parsimonious model that perfectly represents the data's distribution) under the strong assumption that the true data-generating distribution was "DAG-perfect" with respect to the observable variables. This means the true distribution's independence constraints were exactly those implied by a Directed Acyclic Graph (DAG). This paper addresses the limitation of this strong assumption by exploring what happens when the generative distribution is more realistic and doesn't perfectly align with a DAG structure over observable variables. Specifically, it investigates whether greedy search can still find a useful model, even if it's not strictly parameter-optimal.

Methods

The paper focuses on a specific greedy search algorithm called Greedy Equivalence Search (GES). GES operates on equivalence classes of DAGs, which group DAGs that represent the same set of independence constraints. The algorithm iteratively adds or removes edges, guided by a scoring criterion, until it reaches a local optimum.

The core theoretical contribution is proving that GES, when paired with an "asymptotically consistent" scoring criterion (like the Bayesian scoring criterion or BIC), can find an "inclusion-optimal" model. An inclusion-optimal model is one that perfectly represents the generative distribution and has no simpler sub-model that also does. This is a weaker form of optimality than parameter-optimality.

The proof relies on the concept of "local consistency" of scoring criteria, which ensures that adding an edge that resolves an independence constraint not present in the true distribution increases the score, and removing an edge that doesn't violate a true constraint decreases it. The paper also introduces and utilizes the "composition property" of independence, a more relaxed assumption about the generative distribution. This property states that if a variable is dependent on a set of variables, it must be dependent on at least one singleton variable within that set. The authors show that this property holds if the generative distribution is perfect with respect to a graphical model with a "path property," even with hidden variables and selection bias.

Datasets

The paper does not use real-world datasets for evaluation. Instead, it generates synthetic data from two specific "gold-standard" models:

  1. w-structure model: A model with binary variables, except for one three-valued variable, and one hidden variable. This model highlights situations where no perfect DAG map exists over observables.
  2. Selection four-cycle model: A model with binary variables (except one four-valued variable) and a selection variable. This model demonstrates scenarios with selection bias and where the observable distribution is represented by an undirected cycle, not a DAG.

These synthetic datasets are used to empirically evaluate the theoretical findings.

Key Insights and Ideas

  • Relaxing DAG-perfect assumption: The most significant insight is that greedy search can still find valuable models (inclusion-optimal) even when the true data-generating distribution isn't perfectly representable by a DAG over observable variables. This broadens the applicability of these algorithms.
  • Inclusion-optimality as a practical goal: While parameter-optimality is ideal, inclusion-optimality is shown to be a more achievable and theoretically sound target for greedy search under more realistic assumptions.
  • Composition property is key: The paper establishes the importance of the "composition property" of independence for guaranteeing inclusion-optimality. This property is more likely to hold in real-world scenarios than the strict DAG-perfect assumption.
  • Path property of graphical models: The paper connects the composition property to the "path property" of graphical models, providing a theoretical basis for when the composition property can be expected to hold.
  • GES is robust to hidden variables and selection bias: The theoretical results hold even when the generative model includes hidden variables or when the observed data is subject to selection bias, making the findings highly relevant for practical data analysis.
  • Parameter-optimal vs. Inclusion-optimal: The experiments highlight that even with large sample sizes, GES might not always find the parameter-optimal model, but it reliably finds inclusion-optimal ones. This suggests a trade-off between strict parsimony and robust representation.

Key Results

  • Theorem 3: The Backward Equivalence Search (BES) phase of GES, when started with an equivalence class that includes the generative distribution, is guaranteed to find an inclusion-optimal model in the limit of large sample sizes, provided the scoring criterion is locally consistent.
  • Theorem 4: If the generative distribution satisfies the composition property, then GES (and Corollary 5 for UGES) is guaranteed to find an inclusion-optimal model in the limit of large sample sizes.
  • Experimental results: The experiments with synthetic data showed that as sample size increases, the percentage of models identified by GES that are inclusion-optimal increases. For the w-structure and selection four-cycle models, GES achieved high rates of identifying inclusion-optimal models, though it was less consistent in identifying the parameter-optimal model. For instance, GES identified the parameter-optimal model about three-fourths of the time for the w-structure model and about half the time for the selection four-cycle model, regardless of sample size.

Limitations and Future Work

  • Large sample size assumption: The theoretical guarantees are asymptotic, meaning they hold in the limit of infinitely many data points. The paper acknowledges that for real-world problems with finite data, an "unrealistic number of records" might be needed for these guarantees to fully manifest.
  • Identifying parameter-optimal models: The experiments suggest that GES may not reliably identify the parameter-optimal model, even in the large-sample limit. The authors suggest further investigation into general conditions under which greedy algorithms can identify parameter-optimal models.
  • Comparison with other algorithms: The paper calls for more work comparing GES to other algorithms (like UGES) across different sample sizes and exploring alternative search strategies that might perform better with smaller datasets.
  • Sample size for reliable identification: Further research is needed to empirically determine the number of samples required for algorithms like GES to reliably identify inclusion-optimal models.

Summary updated

BibTeX
@inproceedings{chickering2002finding,
  author = {David Maxwell Chickering and Christopher Meek},
  title = {{Finding Optimal Bayesian Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2002},
}
Figure